A hierarchy of monotone deterministic non-forgetting restarting automata
From MaRDI portal
Publication:633765
DOI10.1007/S00224-009-9247-XzbMATH Open1209.68303OpenAlexW2146469177MaRDI QIDQ633765FDOQ633765
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Growing context-sensitive languages and Church-Rosser languages
- Membership for growing context-sensitive grammars is polynomial
- COOPERATING DISTRIBUTED SYSTEMS OF RESTARTING AUTOMATA
- SHRINKING RESTARTING AUTOMATA
- ON DETERMINISTIC CD-SYSTEMS OF RESTARTING AUTOMATA
- Church-Rosser Thue systems and formal languages
- LR-regular grammars - an extension of LR(k) grammars
- The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
- On Nonforgetting Restarting Automata That Are Deterministic and/or Monotone
- The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
- Left-to-right regular languages and two-way restarting automata
- Developments in Language Theory
- Restarting automata with restricted utilization of auxiliary symbols
- Degrees of non-monotonicity for restarting automata
Cited In (8)
- Title not available (Why is that?)
- Transductions Computed by PC-Systems of Monotone Deterministic Restarting Automata
- A hierarchy of jumping restarting automata
- A Taxonomy of Deterministic Forgetting Automata
- Degrees of non-monotonicity for restarting automata
- Restarting transducers, regular languages, and rational relations
- Developments in Language Theory
- Title not available (Why is that?)
This page was built for publication: A hierarchy of monotone deterministic non-forgetting restarting automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633765)
