Deterministic Consistency Checking of LP Constraints

Deterministic Consistency Checking of LP Constraints Suresh Manandhar Language Technology Group Human Communication Research Centre University of Edinburgh, Scotland email : Sure sh.Manandhar~ed, ac.uk Abstract We provide a constraint based compu- tational model of linear precedence as employed in the HPSG grammar formal- ism. An extended feature logic which adds a wide range of constraints involv- ing precedence is described. A sound, complete and terminating deterministic constraint solving procedure is given. Deterministic computational model is achieved by weakening the logic such that it is sufficient for linguistic appli- cations involving word-order. Subject areas: feature logic, constraint based grammars 1 Introduction Within HPSG (Pollard and Sag, 1987) (Pollard and Sag, 1994) the constituent ordering princi- ple given in (1) is intended to express the rela- tion between the value of the PHON attribute and the DTRS attribute which contains the hierarchical structure of the derivation. [DTRS rPHON ] (1) phrasal_sign = ~der_constituent([~) (2) Linear Precedence Constraint 1 (LP1): HEAD[LEX+] < [] However, it is not entirely clear how or- der_constituent is supposed to interpret various linear precedence statements such as LP1. 1.1 Reape's approach The idea taken in Reape's approach (Reape, 1993) is to suggest that word-order is enforced between locally definable word order domains which are or- dered sequences of constituents. Word order do- mains in Reape's approach are totally ordered se- quences. A domain union operation as given in (3) is then employed to construct word order domains locally within a HPSG derivation step. (3) 0(,1, ,1, ,7). 0(o~,= o,~,= o oD ~ O(,,,,,,~,,,~). If A is the string < a,b > and B is the string < c,d >, their domain union C given by O(A,B,C) will produce all the sequences in which a precedes b and c precedes d i.e. the fol- lowing sequences: <a,b,c,d> <a,c,b,d> < a,c,d,b > < c,d,a,b > < c,d,a,b > < c,a,b,d > However in this system to encode the property that {x, y, z} is a domain in which the ordering is arbitrary (i.e. free) then one needs the following disjunctive statements: < x,y,z > U < x,z,y > H < y,x,z > U < y,z,x > H < z,x,y > U < z,y,x > It is simply not possible to be agnostic about the relative ordering of sequence elements within Reape's system. We identify two deficiencies in Reape's ap- proach namely: • System is non-deterministic (generate and test paradigm) • Not possible to be agnostic about order This is so since domain union is a non- deterministic operation and secondly underspec- ification of ordering within elements of a domain is not permitted. In the following sections we describe a con- straint language for specifying LP constraints that overcomes both these deficiencies. Additionally our constraint language provides a broad range of constraints for specifying linear precedence that go well beyond what is available within current typed feature formalisms. Our approach is in the spirit of Reape's approach but improves upon it. Furthermore, a sound, complete and terminat- ing consistency checking procedure …

Content truncated to 500 words