Jens Michaelis, Uwe Mönnich and Frank Morawietz

On Minimalist Attribute Grammars and Macro Tree Transducers

Abstract

In this paper we extend the work by Michaelis (1999) which shows how to encode an arbitrary Minimalist Grammar in the sense of Stabler (1997) into a weakly equivalent multiple context-free grammar (MCFG). By viewing MCFG-rules as terms in a free Lawvere theory we can translate a given MCFG 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 both through an MSO transduction based upon tree-walking automata and through a macro tree transduction. This two-step approach gives an operational as well as a logical description of the tree sets involved. As an interlude we show that MCFGs can be regarded as a particularly simple attribute grammar.