|
Frank Morawietz and Uwe MönnichA Model-Theoretic Description of Tree Adjoining Grammars23pp., PS (1027kb), PDF (336kb). AbstractIn this paper we show that non-context-free phenomena can be captured using only limited logical means. In particular, we show how to encode a Tree Adjoining Grammar (Joshi and Schabes 1997) into a weakly equivalent monadic context-free tree grammar (MCFTG). By viewing MCFTG-rules as terms in a free Lawvere theory, we can translate a given MCFTG into a regular tree grammar. The latter is characterizable by both a tree automaton and a corresponding formula in monadic second-order (MSO) logic. The trees of the resulting regular tree language are then unpacked into the intended ``linguistic'' trees through a model-theoretic interpretation in the form of an MSO transduction based upon tree-walking automata. This two-step approach gives a logical as well as an operational description of the tree sets involved.
|
|
In case of problems or for comments, please contact: frank@sfs.uni-tuebingen.de Last updated: 02-Oct-2001 |