tailieunhanh - Báo cáo khoa học: "Syntactic Graphs and Constraint Satisfaction"

In this paper I will consider parsing as a discrete combinatorial problem which consists in constructing a labeled graph that satisfies a set of linguistic constraints. I will identify some properties of linguistic constraints which allow this problem to be solved efficiently using constraint satisfaction algorithms. I then describe briefly a modular parsing algorithm which constructs a syntactic graph using a set of generative operations and applies a filtering algorithm to eliminate inconsistent nodes and edges. . | Syntactic Graphs and Constraint Satisfaction Jeff Martin Department of Linguistics University of Maryland College Park MD 20742 jeffmar@ In this paper I will consider parsing as a discrete combinatorial problem which consists in constructing a labeled graph that satisfies a set of linguistic constraints. I will identify some properties of linguistic constraints which allow this problem to be solved efficiently using constraint satisfaction algorithms. I then describe briefly a modular parsing algorithm which constructs a syntactic graph using a set of generative operations and applies a filtering algorithm to eliminate inconsistent nodes and edges. The model of grammar I will assume is not a monolithic rule system but instead decomposes grammatical problems into multiple constraints each describing a certain dimension of linguistic knowledge. The grammar is partitioned into operations and constraints. Some of these are given in 1 note that many constraints including linear precedence are not discussed here. I assume also that the grammar specifies a lexicon which is a list of complex categories or attribute-value structures 0ohnson 1988 along with a set of partial functions which define the possible categories of the grammar. 1 Operations PROJECT-X ADJOIN-X MOVE-X INDEX-X Constraints CASEMARK X Y THETAMARK AGREE X Y ANTECEDE X Y This cluster of modules incorporates operations and constraints from both GB theory Chomsky 1981 and TAG Johsi 1985 . PROJECT-X is a category-neutral X-bar grammar consisting of three context-free metarules which yield a small set of unordered elementary trees. ADJOIN-X which consists of a single adjunction schema is a restricted type of tree adjunction which takes two trees and adjoins one to a projection of the head of the other. The combined schema are given in 2 2 X2 XI Y2 specifier axiom XI XO Y2 complement axiom Xn 0 a lexical category labeling axiom Xn Xn Yn adjunction axiom MOVE-X constructs chains which link gaps