A hierarchy of monotone deterministic non-forgetting restarting automata
From MaRDI portal
Publication:633765
DOI10.1007/S00224-009-9247-XzbMath1209.68303OpenAlexW2146469177MaRDI QIDQ633765
Friedrich Otto, Hartmut Messerschmidt
Publication date: 30 March 2011
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-009-9247-x
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
A hierarchy of jumping restarting automata ⋮ Restarting transducers, regular languages, and rational relations ⋮ Transductions Computed by PC-Systems of Monotone Deterministic Restarting Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Membership for growing context-sensitive grammars is polynomial
- Restarting automata with restricted utilization of auxiliary symbols
- Degrees of non-monotonicity for restarting automata
- Growing context-sensitive languages and Church-Rosser languages
- The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
- LR-regular grammars - an extension of LR(k) grammars
- COOPERATING DISTRIBUTED SYSTEMS OF RESTARTING AUTOMATA
- SHRINKING RESTARTING AUTOMATA
- On Nonforgetting Restarting Automata That Are Deterministic and/or Monotone
- ON DETERMINISTIC CD-SYSTEMS OF RESTARTING AUTOMATA
- The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
- Church-Rosser Thue systems and formal languages
- Left-to-right regular languages and two-way restarting automata
- Developments in Language Theory
This page was built for publication: A hierarchy of monotone deterministic non-forgetting restarting automata