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

DOI10.25596/JALC-2009-175zbMATH Open1206.68178MaRDI QIDQ3589634FDOQ3589634

Authors: Benedek Nagy 

Publication date: 20 September 2010

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

zbMATH Keywords

Chomsky hierarchyformal languagessemilinear languages

Mathematics Subject Classification ID

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

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)