Computer Science – Computation and Language
Scientific paper
1998-05-21
Computer Science
Computation and Language
7 pages, uses colacl.sty
Scientific paper
Since the early Sixties and Seventies it has been known that the regular and context-free languages are characterized by definability in the monadic second-order theory of certain structures. More recently, these descriptive characterizations have been used to obtain complexity results for constraint- and principle-based theories of syntax and to provide a uniform model-theoretic framework for exploring the relationship between theories expressed in disparate formal terms. These results have been limited, to an extent, by the lack of descriptive characterizations of language classes beyond the context-free. Recently, we have shown that tree-adjoining languages (in a mildly generalized form) can be characterized by recognition by automata operating on three-dimensional tree manifolds, a three-dimensional analog of trees. In this paper, we exploit these automata-theoretic results to obtain a characterization of the tree-adjoining languages by definability in the monadic second-order theory of these three-dimensional tree manifolds. This not only opens the way to extending the tools of model-theoretic syntax to the level of TALs, but provides a highly flexible mechanism for defining TAGs in terms of logical constraints. This is the full version of a paper to appear in the proceedings of COLING-ACL'98 as a project note.
No associations
LandOfFree
A Descriptive Characterization of Tree-Adjoining Languages (Full Version) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Descriptive Characterization of Tree-Adjoining Languages (Full Version), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Descriptive Characterization of Tree-Adjoining Languages (Full Version) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-86054