A hierarchy of monotone deterministic non-forgetting restarting automata

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

zbMATH Keywords

hierarchy of language classesnonforgettingrestarting automataRRWW-model

Mathematics Subject Classification ID

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