Generalized Tree Descriptions for LFG

This paper proposes a novel description format for c-structure. The explicit phrase structure rewrite rules are replaced by more general constraints in a tree description language: (weak) monadic second order logic (MSOL). Exploiting the fact that the MSOL-definable tree languages correspond to the parse trees of context-free string languages, it can be shown that the generative capacity of the LFG formalism is not altered. Applying the MSOL-based formulation of c-structure descriptions to Optimality-Theoretic LFG results in a significant clarification of the prerequisites for a computationally well-behaved Optimality-Theoretic LFG system.