On some decision problems for stateless deterministic ordered restarting automata

DOI10.1007/978-3-319-19225-3_14MaRDI QIDQ5500690zbMATH OpenOpenAlexFDO

Authors Kent Kwee, Friedrich Otto

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 complexityordered rewritingrestarting automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the descriptional complexity of stateless deterministic ordered restarting automata
• On the effects of nondeterminism on ordered restarting automata
• On stateless deterministic restarting automata
• On Stateless Deterministic Restarting Automata
• Reversible Ordered Restarting Automata

Cites work

• Algebraic decision procedures for local testability
• Characterizing the regular languages by nonforgetting restarting automata
• Descriptional and computational complexity of finite automata -- a survey
• Determination of finite automata accepting subregular languages
• Families of locally testable languages
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Locally testable languages
• On the descriptional complexity of deterministic ordered restarting automata
• Ordered restarting automata for picture languages
• Relationships between nondeterministic and deterministic tape complexities
• Succinct description of regular languages by weak restarting automata
• Weight-reducing Hennie machines and their descriptional complexity

Cited in

(15)

• On the descriptional complexity of stateless deterministic ordered restarting automata
• Reversibility for stateless ordered RRWW-automata
• Regulated variants of limited context restarting automata
• A pumping lemma for ordered restarting automata
• On the effects of nondeterminism on ordered restarting automata
• On Ordered RRWW-Automata
• Reversible Ordered Restarting Automata
• Some classes of rational functions for pictures
• On stateless two-pushdown automata and restarting automata
• Nondeterministic ordered restarting automata
• Deterministic ordered restarting automata that compute functions
• On Stateless Deterministic Restarting Automata
• On the descriptional complexity of deterministic ordered restarting automata
• On deterministic ordered restart-delete automata
• On stateless deterministic restarting automata

This page was built for publication: On some decision problems for stateless deterministic ordered restarting automata

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