1998/05/20 by James Rogers, Rogers, James, James E. Thorold Rogers
Computer Science · #Advanced Algebra and Logic #Computation and Language (cs.CL) #FOS: Computer and information sciences #Logic, programming, and type systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cmp-lg/9805008
openalex publication_date 1998/05/20 · openalex created_date 2022/09/03 · openalex updated_date 2026/07/28
Since the early Sixties and Seventies it has been known that the regular and\ncontext-free languages are characterized by definability in the monadic\nsecond-order theory of certain structures. More recently, these descriptive\ncharacterizations have been used to obtain complexity results for constraint-\nand principle-based theories of syntax and to provide a uniform model-theoretic\nframework for exploring the relationship between theories expressed in\ndisparate formal terms. These results have been limited, to an extent, by the\nlack of descriptive characterizations of language classes beyond the\ncontext-free. Recently, we have shown that tree-adjoining languages (in a\nmildly generalized form) can be characterized by recognition by automata\noperating on three-dimensional tree manifolds, a three-dimensional analog of\ntrees. In this paper, we exploit these automata-theoretic results to obtain a\ncharacterization of the tree-adjoining languages by definability in the monadic\nsecond-order theory of these three-dimensional tree manifolds. This not only\nopens the way to extending the tools of model-theoretic syntax to the level of\nTALs, but provides a highly flexible mechanism for defining TAGs in terms of\nlogical constraints.\n This is the full version of a paper to appear in the proceedings of\nCOLING-ACL'98 as a project note.\n