A Characterization of the Context-Free Languages by Stateless Ordered Restart-Delete Automata

DOI10.1007/978-3-030-38919-2_4zbMath1440.68160OpenAlexW2999787701MaRDI QIDQ3297753

Friedrich Otto

Publication date: 20 July 2020

Published in: SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-38919-2_4

zbMATH Keywords

context-free languagerestarting automatonordered rewriting

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

On the expressive power of stateless ordered restart-delete automata

Cites Work

• Unnamed Item
• Unnamed Item
• Membership for growing context-sensitive grammars is polynomial
• Growing context-sensitive languages and Church-Rosser languages
• Recent advances in formal languages and applications.
• On the Effects of Nondeterminism on Ordered Restarting Automata
• Ordered Restarting Automata for Picture Languages
• Clearing Restarting Automata
• Church-Rosser Thue systems and formal languages
• On the Descriptional Complexity of Deterministic Ordered Restarting Automata
• Matrix Equations and Normal Forms for Context-Free Grammars
• On deterministic ordered restart-delete automata
• On deterministic ordered restart-delete automata

This page was built for publication: A Characterization of the Context-Free Languages by Stateless Ordered Restart-Delete Automata