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.
Universiteit Twente
A. Nijholt , G. Scollo , R. Steetskamp
Algebraic Methods in Language Processing
Logic and language

Groenink, A. (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.