We define a more formal version of literal movement grammar (LMG) as outlined in [Gro95c], in such a way that it provides a simple framework that incorporates a large family of grammar formalisms (Head Grammar [Pol84], LCFRS, [Wei88]), PMCFG, [KNSK92] and String Attributed Grammars [Eng86]). The semantics is (both in rewriting and least fixed point definitions) simple and elegant, and sheds some new light on shared properties of the mentioned formalisms. We then define a restricted version called simple LMG and show that it generates languages that are not mildly context sensitive, yet preserves the polynomial time recognition property of LCFRS.
Additional Metadata
Publisher Universiteit Twente
Editor A. Nijholt , G. Scollo , R. Steetskamp
Conference Algebraic Methods in Language Processing
Groenink, A.V. (1995). A Simple Uniform Semantics for Concatenation-based Grammar. In A Nijholt, G Scollo, & R Steetskamp (Eds.), Algebraic Methods in Language Processing: Proceedings of TWLT / AMAST (pp. 149–159). Universiteit Twente.