A Two-Step Approach to Non-Contextfreeness

Jens Michaelis, Uwe Mönnich and Frank Morawietz

A Two-Step Approach to Non-Contextfreeness

12pp., PS (255kb).

Abstract

Extending 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), we present in this paper a translation from MCFGs 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 (which can be implemented as a Macro Tree Transducer) 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: 17-Mar-2000