ON A HIERARCHY OF PERMUTATION LANGUAGES

DOI10.1142/9789814317610_0012zbMath1264.68100OpenAlexW2322982615MaRDI QIDQ4922680

Benedek Nagy

Publication date: 3 June 2013

Published in: Automata, Formal Languages and Algebraic Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/9789814317610_0012

zbMATH Keywords

Chomsky hierarchyinterchange (permutation) rulemildly context-sensitivitypermutation languagessemi-linear languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (4)

Shuffled languages -- representation and recognition ⋮ Regular and linear permutation languages ⋮ On the Membership Problem of Permutation Grammars — A Direct Proof of NP-Completeness ⋮ Characterization and complexity results on jumping finite automata

This page was built for publication: ON A HIERARCHY OF PERMUTATION LANGUAGES