This paper classifies a family of grammar formalisms that extendcontext-free grammar by talking about tuples of terminal strings, ratherthan independently combining single terminal words into larger singlephrases. These include a number of well-known formalisms, such as headgrammar and linear context-free rewriting systems, but also a new formalism,(simple) literal movement grammar, which strictly extends the previouslyknown formalisms, while preserving polynomial time recognizability.The descriptive capacity of simple literal movement grammars isillustrated both formally through a weak generative capacity argument and ina more practical (...) sense by the description of conjunctive cross-serialrelative clauses in Dutch. After sketching a complexity result and drawing anumber of conclusions from the illustrations, it is then suggested that thenotion of mild context-sensitivity currently in use, that depends on therather loosely defined concept of constant growth, needs a modification toapply sensibly to the illustrated facts; an attempt at such a revision isproposed. (shrink)

In his oft-cited, if rarely read book, Noam Chomsky ventured to propose a hierarchy of formal grammars. He defined them as rules for rewriting strings of terminal and nonterminal symbols into different strings of terminal and nonterminal symbols, thus giving birth to what is today known as the Chomsky hierarchy. The author himself claimed the theory applied exclusively to formal languages, but in his considerations he also happened to formulate a problem relating to natural languages, namely, to which formal grammar (...) category descriptive grammars of natural languages belong? While restraining from siding with any answer to the problem, Chomsky sparked a long philosophical and linguistic discussion revolving around complex structures in natural languages. (shrink)