Infinite Hierarchy of Permutation Languages

• Autorzy: Madejski G.

Identyfikatory

DOI

10.3233/FI-2014-992

• Języki publikacji: EN

Abstrakty

EN

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 Perm_n. 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₂ \subsetneq Perm₃ was obtained. We extend this result proving that Perm_{4n \minus 2} \subsetneq Perm_{4n \minus 1} for n ≥ 1.

Słowa kluczowe

EN

permutation grammar; interchange rule; infinite hierarchy; context-free grammars

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 130, nr 3
• Strony: 263--274
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Madejski G.

• Institute of Informatics, University of Gdańsk, Wita Stwosza 57, 80-952 Gdańsk, Poland

Bibliografia

• [1] Berglund M., Björklund H., Högberg J.: Recognizing Shuffled Languages, LATA 2011, Lecture Notes in Computer Science 6638, 2011, 142–154.
• [2] Book R. V.: On the structure of context-sensitive grammars, Int. Journal of Computer and Information Sciences 2, 1973, 129–139.
• [3] Czerwiński W., Lasota S.: Partially-commutative context-free languages, DCM 89, 2012, 35–48.
• [4] Esparza J.: Petri Nets, Commutative Context-Free Languages, and Basic Parallel Processes, Fundamenta Informaticae 30, 1997, 23–41.
• [5] Hopcroft J. E., Ullmann J. D.: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
• [6] Jędrzejowicz J., Szepietowski A.: Shuffle languages are in P, Theoretical Computer Science 250/1-2, 2001, 31–53.
• [7] Mäkinen E.: On permutative grammars generating context-free languages, BIT 25, 1968, 604–610.
• [8] Mateescu A., Rozenberg G., Salomaa A.: Shuffle on trajectories: Syntactic constraints, Theoretical Computer Science 197/1-2, 1998, 1–56.
• [9] Nagy B.: On a Hierarchy of Permutation Languages, Automata, Formal Languages and Algebraic Systems, 2010, 163–178.
• [10] Nagy B.: Permutation languages in formal linguistics, IWANN 2009, Lecture Notes in Computer Science 5517, 2009, 504–511.
• [11] Nagy B.: Languages Generated by Context-Free and Type AB → BA Rules, Journal of Automata, Languages and Combinatorics 14/2, 2009, 175–186.
• [12] Sillars W. A.: Formal properties of essentially context-dependent families of languages, Phd Dissertation, Pennsylvania State University, 1968.