On the expressive power of stateless ordered restart-delete automata

DOI10.1007/s00224-020-10028-3OpenAlexW3139299110MaRDI QIDQ2230720

Friedrich Otto

Publication date: 28 September 2021

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-020-10028-3

zbMATH Keywords

context-free languagedescriptional complexityrestarting automatonordered rewritinglimited context restarting automaton

Mathematics Subject Classification ID

Theory of computing (68Qxx) Computer science (68-XX) Computability and recursion theory (03Dxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Membership for growing context-sensitive grammars is polynomial
• Growing context-sensitive languages and Church-Rosser languages
• On the descriptional complexity of stateless deterministic ordered restarting automata
• Recent advances in formal languages and applications.
• On the Effects of Nondeterminism on Ordered Restarting Automata
• On the classes of languages accepted by limited context restarting automata
• Ordered Restarting Automata for Picture Languages
• Clearing Restarting Automata
• Nondeterministic Ordered Restarting Automata
• A Characterization of the Context-Free Languages by Stateless Ordered Restart-Delete Automata
• Church-Rosser Thue systems and formal languages
• Δ-Clearing Restarting Automata and $\makebox{\sf CFL} $
• 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: On the expressive power of stateless ordered restart-delete automata