On the Degree of Extension of Some Models Defining Non-Regular Languages

DOI10.4204/eptcs.386.3arXiv2309.02749OpenAlexW4386400103MaRDI QIDQ6204122

Mihaela Păun, Victor Mitrana

Publication date: 9 April 2024

Published in: Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2309.02749

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sequential grammars and automata with valences
• On the degrees of non-regularity and non-context-freeness
• On the group memory complexity of extended finite automata over groups
• Word problems recognisable by deterministic blind monoid automata
• Substitution and bounded languages
• FINITE AUTOMATA OVER FREE GROUPS
• The Rational Index: A Complexity Measure for Languages
• Non-context-free grammars generating context-free languages
• JUMPING FINITE AUTOMATA
• EXTENDED FINITE AUTOMATA AND WORD PROBLEMS
• A note on asymmetry in phrase structure grammars
• Mappings which preserve context sensitive languages
• Two-way languages
• An analog of a theorem about context-free languages
• Terminal Context in Context-Sensitive Grammars
• Discontinuity and asymmetry in phrase structure grammars
• Extended finite automata over groups