Paper: A Descriptive Characterization of Tree-Adjoining Languages (Project Note)

ACL ID C98-2178
Title A Descriptive Characterization of Tree-Adjoining Languages (Project Note)
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1998
Authors

Since the early Sixties and Seventies it has been known that the regular and context-free lan- guages arc 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, t)y the lack of descrip- tive characterizations of language (:lasses be- yond the context-h'ee. Recently, we have shown I;hat tree-adjoining languages (in a mildly gener- alized form) can be characterized by recognition by automata operating on t...