A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*

DOI10.3233/FI-2021-2035OpenAlexW3161875012MaRDI QIDQ5164869

Friedrich Otto

Publication date: 15 November 2021

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2021-2035

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Membership for growing context-sensitive grammars is polynomial
• Degrees of non-monotonicity for restarting automata
• On the complexity of 2-monotone restarting automata
• Growing context-sensitive languages and Church-Rosser languages
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Lower bound technique for length-reducing automata
• Recent advances in formal languages and applications.
• LR-regular grammars - an extension of LR(k) grammars
• Hierarchies of weakly monotone restarting automata
• SHRINKING RESTARTING AUTOMATA
• Church-Rosser Thue systems and formal languages
• Restarting automata
• On growing context-sensitive languages
• Left-to-right regular languages and two-way restarting automata
• Developments in Language Theory

This page was built for publication: A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*