wMSO theories as grammar formalisms

摘要

We explore the use of weak monadic second-order languages over structures of varying dimension as specification languages for grammars and automata, focusing, in particular, on the extension of the longstanding results characterizing the regular and context-free languages in terms of definability in wS1S (one-dimensional) and wSnS (two-dimensional), respectively, to a characterization of the Tree-Adjoining Languages in terms of definability in the weak monadic second-order theory of certain three-dimensional tree-like structures. We then explore the application of these results to aspects of an existing large-scale Tree-Adjoining Grammar for English and close with some speculation on the feasibility of this approach as a means of building and maintaining such grammars.