On Determining the Consistency of Partial Descriptions of Trees

ON DETERMINING THE CONSISTENCY OF PARTIAL DESCRIPTIONS OF TREES Thomas L. Cornell Cognitive Science Program University of Arizona Tucson, AZ 85721 cornell@ccit.arizona.edu Abstract 1 We examine the consistency problem for descriptions of trees based on remote dominance, and present a consistency-checking algorithm which is polynomial in the number of nodes in the description, despite disjunctions inherent in the theory of trees. The resulting algorithm allows for descriptions which go beyond sets of atomic formulas to allow certain types of disjunction and negation. INTRODUCTION In Marcus, Hindle & Fleck (1983), the authors proposed an approach to syntactic tree structures which took the primary structural relation to be remote dominance rather than immediate dominance. Recently, researchers have shown a revived interest in variants of Marcus et al.'s D- Theory, most likely due to the availability of approaches and techniques developed in the study of feature structures and their underlying logics. For example, both Rogers & Vijay- Shanker (1992) and Cornell (1992) present formal treatments of many notions which Marcus et al. (1983) treated only informally and incompletely. Furthermore, work on the psycholinguistic implications of this approach has continued apace (Weinberg 1988; Gorrell 1991; Marcus & Hindle 1990), making all the more necessary sustained foundational work in the theory of description-based tree-building applications (parsers, generators, etc.) This paper addresses one particular problem that arises in this approach to tree building. As with feature-structures, the essential operation here is the combination of two collections of partial information about the syntactic structure of an expression. It may happen that the two 1 Many thanks to Dick Oehrle, Ed Stabler, Drew Moshier and Mark 3ohnson for comments, discussion and encouragement. Theirs the gratitude, mine the fault. collections to be combined contain contradictory information. For example one might contain the assertion that "node 7 dominates node 12" while the other claims that "node 12 precedes node 7". No tree structure can satisfy both these constraints. The operation of description combination is thus not simple set union, but, like unification, involves taking a least upper bound in a semi-lattice where lub's are not everywhere defined. Both Rogers & Vijay-Shanker (1992) and Cornell (1992) propose to solve the D-Theoretic consistency problem by using essentially Tableau-based approaches. This can lead to combinatorial explosion in the face of disjunctions inherent in the theory of trees. But as it happens, proof techniques designed to handle general disjunctions are more powerful than we need; the disjunctions that arise from the theory of trees are of a restricted kind which can be handled by strictly polynomial means. We will see that we can efficiently handle richer notions of description than those in the "classical" D-Theory of Marcus, et al. (1983). D-THEORYANDTREETHEORY DESCRIPTION LANGUAGE We will make use of the following description language ,,~. Define the set of basic relation names, R, as: b --"below" (i.e., dominated-by) d -- "dominates" e -- "equals" f --"follows" (i.e., preceded-by) p -- "precedes" We define an algebra on relation names as follows. ($1 V $2)(x,y) =def the collection …

Content truncated to 500 words