tailieunhanh - Báo cáo khoa học: "A Descriptive Characterization of Tree-Adjoining Languages (Project Note)"

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. . | A Descriptive Characterization of Tree-Adjoining Languages Project Note James Rogers Dept of Computer Science Univ of Central Florida Orlando FL USA Abstract 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. 1 Introduction In the early Sixties Biichi 1960 and El-got 1961 established that a set of strings was regular iff it was definable in the weak monadic second-order theory of the natural numbers with successor wSlS . In the early Seventies an extension to the context-free languages was obtained by Thatcher and Wright 1968 and Doner 1970 who established that the CFLs were all and only the sets of strings forming the yield of sets of finite trees definable in the weak monadic second-order theory of multiple successors wSnS . These descriptive characterizations have natural application to constraint- and .