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

Full work available at URL https://doi.org/10.25596/JALC-2009-175

zbMATH Keywords

Chomsky hierarchyformal languagessemilinear languages

Mathematics Subject Classification ID

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

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

(8)

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

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)