Frank Morawietz
Seminar für Sprachwissenschaft
Theoretische Computerlinguistik
Neuphilologische Fakultät
Universität Tübingen

Frank Morawietz and Uwe Mönnich

A Model-Theoretic Description of Tree Adjoining Grammars

23pp., PS (1027kb), PDF (336kb).


In 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:
Last updated: 02-Oct-2001