On the expressive power of stateless ordered restart-delete automata
From MaRDI portal
Publication:2230720
DOI10.1007/s00224-020-10028-3OpenAlexW3139299110MaRDI QIDQ2230720
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
context-free languagedescriptional complexityrestarting automatonordered rewritinglimited context restarting automaton
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