Affiliations: Institute of Computer Science, University of Wrocław, Joliot-Curie 15, PL-50-383 Wrocław, Poland. tju@ii.uni.wroc.pl
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.
