Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: interchange rule

Sortuj według:

Ogranicz wyniki do:

Infinite Hierarchy of Permutation Languages

Madejski G.

Fundamenta Informaticae

2014

Vol. 130, nr 3

263--274

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 Perm2 \subsetneq Perm3 was obtained. We extend this result proving that Perm4n \minus 2 \subsetneq Perm4n \minus 1 for n ≥ 1.