Languages generated by context-free grammars extended by type AB BA rules

DOI10.25596/JALC-2009-175MaRDI QIDQ3589634zbMATH OpenFDO

Authors Benedek Nagy

Publication date 20 September 2010

zbMATH Keywords

Chomsky hierarchyformal languagessemilinear languages

Mathematics Subject Classification ID

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

Recommendations

• ON A HIERARCHY OF PERMUTATION LANGUAGES
• On permutative grammars generating context-free languages
• scientific article; zbMATH DE number 4062631
• Regular and linear permutation languages
• The interchange or pump (di)lemmas for context-free languages

Cited in

(7)

• On the membership problem of permutation grammars -- a direct proof of NP-completeness
• \( 5^\prime \to 3^\prime\) Watson-Crick pushdown automata
• State-deterministic Finite Automata with Translucent Letters and Finite Automata with Nondeterministically Translucent Letters
• Characterization and complexity results on jumping finite automata
• Regular and linear permutation languages
• Counter machines, Petri nets, and consensual computation
• Shuffled languages -- representation and recognition

This page was built for publication: Languages generated by context-free grammars extended by type \(AB\to BA\) rules

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