On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata

DOI10.1007/978-3-319-19225-3_14zbMath1390.68406OpenAlexW1171547469MaRDI QIDQ5500690

Friedrich Otto, Kent Kwee

Publication date: 7 August 2015

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19225-3_14

zbMATH Keywords

decision problemdescriptional complexityrestarting automatonordered rewriting

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (9)

Regulated variants of limited context restarting automata ⋮ Deterministic Ordered Restarting Automata that Compute Functions ⋮ Nondeterministic Ordered Restarting Automata ⋮ Some classes of rational functions for pictures ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ On deterministic ordered restart-delete automata ⋮ Reversibility for stateless ordered RRWW-automata ⋮ On Ordered RRWW-Automata ⋮ Reversible Ordered Restarting Automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Succinct description of regular languages by weak restarting automata
• Families of locally testable languages
• Determination of finite automata accepting subregular languages
• Relationships between nondeterministic and deterministic tape complexities
• Locally testable languages
• Ordered Restarting Automata for Picture Languages
• Algebraic decision procedures for local testability
• Characterizing the Regular Languages by Nonforgetting Restarting Automata
• Weight-Reducing Hennie Machines and Their Descriptional Complexity
• On the Descriptional Complexity of Deterministic Ordered Restarting Automata

This page was built for publication: On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata