Nondeterministic ordered restarting automata

DOI10.1142/S0129054118410101MaRDI QIDQ3177341zbMATH OpenOpenAlexFDO

Authors Kent Kwee, Friedrich Otto

Publication date 24 July 2018

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054118410101

zbMATH Keywords

abstract family of languagesrestarting automatonemptiness problemordered rewriting

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Recommendations

• On the effects of nondeterminism on ordered restarting automata
• On Ordered RRWW-Automata
• On deterministic ordered restart-delete automata
• On the descriptional complexity of stateless deterministic ordered restarting automata
• Reversible Ordered Restarting Automata

Cites work

• scientific article; zbMATH DE number 3664335 (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?)
• Church-Rosser Thue systems and formal languages
• Membership for growing context-sensitive grammars is polynomial
• Multiply-recursive upper bounds with Higman's lemma
• On some decision problems for stateless deterministic ordered restarting automata
• On the descriptional complexity of deterministic ordered restarting automata
• On the effects of nondeterminism on ordered restarting automata
• Ordered restarting automata for picture languages
• Ordering by Divisibility in Abstract Algebras
• Ordinal recursive bounds for Higman's theorem
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages

Cited in

(8)

• On the expressive power of stateless ordered restart-delete automata
• Deterministic ordered restarting automata for picture languages
• Reversibility for stateless ordered RRWW-automata
• On restarting automata with auxiliary symbols and small window size
• A pumping lemma for ordered restarting automata
• On deterministic ordered restart-delete automata
• On deterministic ordered restart-delete automata
• On the effects of nondeterminism on ordered restarting automata

This page was built for publication: Nondeterministic ordered restarting automata

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