SHRINKING RESTARTING AUTOMATA

DOI10.1142/S0129054107004723zbMath1112.68087OpenAlexW2067373940MaRDI QIDQ3434280

Tomasz Jurdziński, Friedrich Otto

Publication date: 25 April 2007

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

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

zbMATH Keywords

simulationclosure propertiesrestarting automatonlanguage classes

Mathematics Subject Classification ID

Related Items (16)

Regulated variants of limited context restarting automata ⋮ Left-to-right regular languages and two-way restarting automata ⋮ Unnamed Item ⋮ A hierarchy of monotone deterministic non-forgetting restarting automata ⋮ On CD-systems of stateless deterministic R-automata with window size one ⋮ Unnamed Item ⋮ On the complexity of 2-monotone restarting automata ⋮ RESTARTING TILING AUTOMATA ⋮ A Complete Taxonomy of Restarting Automata without Auxiliary Symbols* ⋮ On deterministic ordered restart-delete automata ⋮ On Restarting Automata with Window Size One ⋮ A Hierarchy of Transducing Observer Systems ⋮ On Ordered RRWW-Automata ⋮ COOPERATING DISTRIBUTED SYSTEMS OF RESTARTING AUTOMATA ⋮ Two-dimensional hierarchies of proper languages of lexicalized FRR-automata ⋮ On restarting automata with auxiliary symbols and small window size

Cites Work

• Membership for growing context-sensitive grammars is polynomial
• Growing context-sensitive languages and Church-Rosser languages
• Time-bounded grammars and their languages
• Church-Rosser Thue systems and formal languages
• Quasi-realtime languages
• Unnamed Item

This page was built for publication: SHRINKING RESTARTING AUTOMATA