Nondeterministic Ordered Restarting Automata

DOI10.1142/S0129054118410101zbMath1397.68117OpenAlexW2811303545MaRDI QIDQ3177341

Friedrich Otto, Kent Kwee

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)

Related Items (3)

On the expressive power of stateless ordered restart-delete automata ⋮ On deterministic ordered restart-delete automata ⋮ On restarting automata with auxiliary symbols and small window size

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Membership for growing context-sensitive grammars is polynomial
• Ordinal recursive bounds for Higman's theorem
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• On the Effects of Nondeterminism on Ordered Restarting Automata
• Ordered Restarting Automata for Picture Languages
• Multiply-Recursive Upper Bounds with Higman’s Lemma
• Church-Rosser Thue systems and formal languages
• On the Descriptional Complexity of Deterministic Ordered Restarting Automata
• On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata
• Ordering by Divisibility in Abstract Algebras

This page was built for publication: Nondeterministic Ordered Restarting Automata