Paper: A Descriptive Characterization of Tree-Adjoining Languages

ACL ID P98-2183
Title A Descriptive Characterization of Tree-Adjoining Languages
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1998

Since the early Sixties and Seventies it has been known that the regular and context-free lan- guages are characterized by definability in the monadic second-order theory of certain struc- tures. More recently, these descriptive charac- terizations have been used to obtain complex- ity results for constraint- and principle-based theories of syntax and to provide a uniform model-theoretic framework for exploring the re- lationship between theories expressed in dis- parate formal terms. These results have been limited, to an extent, by the lack of descrip- tive characterizations of language classes be- yond the context-free. Recently, we have shown that tree-adjoining languages (in a mildly gener- alized form) can be characterized by recognition by automata operating on three-dimensional tre...