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

Jens Michaelis, Uwe Mönnich and Frank Morawietz

Derivational Minimalism in Two Regular and Logical Steps


8pp., PS (204kb).

Abstract

Based upon the work by Michaelis (1999) which shows how to encode an arbitrary Minimalist Grammar in the sense of Stabler (1997) into a weakly equivalent linear context-free rewriting system (LCFRS), we present in this paper a translation from the formalism of multiple context-free grammars (which are weakly equivalent to LCFRS) into regular tree grammars (which are characterizable by both tree automata and a corresponding formula in monadic second-order (MSO) logic) by viewing them as terms in a free Lawvere theory. These are then unpacked with an MSO transduction based upon tree-walking automata, thereby giving an operational and a logical description of the tree sets involved.


In case of problems or for comments, please contact: frank@sfs.uni-tuebingen.de
Last updated: 14-Apr-2000