Growing Grammars and Length-reducing Automata

Issue title: Non-Classical Models of Automata and Applications II

Article type: Research Article

Authors: Jurdziński, Tomasz

Affiliations: Institute of Computer Science, University of Wrocław, Joliot-Curie 15, PL-50-383 Wrocław, Poland. [email protected]

Note: [] Address for correspondence: Institute of Computer Science, University of Wrocław, Joliot-Curie 15, PL-50-383 Wrocław, Poland Supported by MNiSW grant number N206 492638, 2010-2012.

Abstract: Growing context-sensitive grammars were introduced in 1986 as a restricted variant of context-sensitive grammars, where all productions are length increasing. Several interesting properties of these grammars have been shown since then, including polynomial time complexity of the membership problem and machine model characterizations. Various characterizations of the model, efficient recognition algorithm and the properties of its deterministic variant (possessing a characterization by string-rewriting systems) justify the practical value. Moreover, as pointed out by McNaughton in 1999, growing context-sensitive grammars complement the Chomsky hierarchy in a very natural way. This article reviews results on this topic and proposes some open problems.

Keywords: Chomsky hierarchy, growing grammars, length-reducing automata

DOI: 10.3233/FI-2011-587

Journal: Fundamenta Informaticae, vol. 112, no. 2-3, pp. 193-217, 2011