Regular and linear permutation languages

DOI10.1051/ITA/2018016MaRDI QIDQ5223617zbMATH OpenOpenAlexWikidataFDO

Authors Grzegorz Madejski

Publication date 18 July 2019

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ita/2018016

zbMATH Keywords

context-free grammarsdecidabilityclosure propertiesgenerative powerregular grammarslinear grammarspermutation languagesinterchange rules

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Recommendations

• ON A HIERARCHY OF PERMUTATION LANGUAGES
• Infinite hierarchy of permutation languages
• The membership problem for linear and regular permutation languages
• On permutative grammars generating context-free languages
• On the membership problem of permutation grammars -- a direct proof of NP-completeness

Cites work

• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Characterization and complexity results on jumping finite automata
• Infinite hierarchy of permutation languages
• Jumping finite automata
• Jumping grammars
• Languages generated by context-free grammars extended by type \(AB\to BA\) rules
• ON A HIERARCHY OF PERMUTATION LANGUAGES
• Partially-commutative context-free languages
• Pumping lemmas for linear and nonlinear context-free languages
• Reversal-bounded multipushdown machines
• The membership problem for linear and regular permutation languages

Cited in

(8)

• Permutation rewriting and algorithmic verification
• On the membership problem of permutation grammars -- a direct proof of NP-completeness
• Languages generated by context-free grammars extended by type \(AB\to BA\) rules
• Infinite hierarchy of permutation languages
• Combinatorial generation via permutation languages
• On permutative grammars generating context-free languages
• The membership problem for linear and regular permutation languages
• ON A HIERARCHY OF PERMUTATION LANGUAGES

This page was built for publication: Regular and linear permutation languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5223617)