Infinite Hierarchy of Permutation Languages

Article type: Research Article

Authors: Madejski, Grzegorz

Affiliations: Institute of Informatics, University of Gdańsk, Wita Stwosza 57, 80-952 Gdańsk, Poland. [email protected]

Note: [] Address for correspondence: Institute of Informatics, University of Gdańsk, Wita Stwosza 57, 80-952 Gdańsk, Poland.

Abstract: Permutation grammars are an extension of context-free grammars with rules having the same symbols on both sides but possibly in a different order. An example of a permutation rule of length 3 is ABC → CBA. If these non-context-free rules are of length at most n, then we say that permutation grammar is of order n and all such grammars generate a family of permutation languages Permn. In 2010 Nagy showed that there exists a language such that it cannot be generated by a grammar of order 2, but rules of length 3 are enough. In other words, a strict inclusion $Perm_2 \subsetneq Perm_3$ was obtained. We extend this result proving that $Perm_{4n \minus 2} \subsetneq Perm_{4n \minus 1}$ for n ≥ 1.

Keywords: Permutation grammar, interchange rule, infinite hierarchy, context-free grammars

DOI: 10.3233/FI-2014-992

Journal: Fundamenta Informaticae, vol. 130, no. 3, pp. 263-274, 2014