On determinism versus nondeterminism for restarting automata

DOI10.1016/J.IC.2008.03.021MaRDI QIDQ948093zbMATH OpenOpenAlexFDO

Authors Hartmut Messerschmidt, Friedrich Otto

Publication date 8 October 2008

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2008.03.021

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata
• Restarting automata
• ON DETERMINISTIC CD-SYSTEMS OF RESTARTING AUTOMATA
• On Nonforgetting Restarting Automata That Are Deterministic and/or Monotone
• On the effects of nondeterminism on ordered restarting automata

Cites work

• scientific article; zbMATH DE number 3839323 (Why is no real title available?)
• scientific article; zbMATH DE number 3612465 (Why is no real title available?)
• scientific article; zbMATH DE number 2040896 (Why is no real title available?)
• scientific article; zbMATH DE number 2080930 (Why is no real title available?)
• scientific article; zbMATH DE number 2245557 (Why is no real title available?)
• A general theory of translation
• Correctness Preservation and Complexity of Simple RL-Automata
• Developments in Language Theory
• Growing context-sensitive languages and Church-Rosser languages
• On the complexity of 2-monotone restarting automata
• Recent advances in formal languages and applications.
• Restarting automata
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages

Cited in

(5)

• Hierarchical Relaxations of the Correctness Preserving Property for Restarting Automata
• On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata
• On special forms of restarting automata
• scientific article; zbMATH DE number 2040896 (Why is no real title available?)
• On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata

This page was built for publication: On determinism versus nondeterminism for restarting automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q948093)