SHRINKING RESTARTING AUTOMATA

DOI10.1142/S0129054107004723MaRDI QIDQ3434280zbMATH OpenOpenAlexFDO

Authors 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

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Mathematical Foundations of Computer Science 2005
• Restarting automata with restricted utilization of auxiliary symbols
• scientific article; zbMATH DE number 2040896
• On the complexity of 2-monotone restarting automata
• Restarting Tree Automata

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Church-Rosser Thue systems and formal languages
• Growing context-sensitive languages and Church-Rosser languages
• Membership for growing context-sensitive grammars is polynomial
• Quasi-realtime languages
• Time-bounded grammars and their languages

Cited in

(22)

• COOPERATING DISTRIBUTED SYSTEMS OF RESTARTING AUTOMATA
• Restarting tiling automata
• ON THE POWER OF RRWW-AUTOMATA
• A Complete Taxonomy of Restarting Automata without Auxiliary Symbols*
• A hierarchy of transducing observer systems
• scientific article; zbMATH DE number 7444013 (Why is no real title available?)
• On the complexity of 2-monotone restarting automata
• On CD-systems of stateless deterministic R-automata with window size one
• Shrinking timed automata
• Power of S-kR-RRWW-automata
• On restarting automata with auxiliary symbols and small window size
• Left-to-right regular languages and two-way restarting automata
• Mathematical Foundations of Computer Science 2005
• On restarting automata with window size one
• On h-lexicalized restarting list automata
• Two-dimensional hierarchies of proper languages of lexicalized FRR-automata
• Fundamentals of Computation Theory
• On Ordered RRWW-Automata
• scientific article; zbMATH DE number 1836418 (Why is no real title available?)
• A hierarchy of monotone deterministic non-forgetting restarting automata
• On deterministic ordered restart-delete automata
• Regulated variants of limited context restarting automata

This page was built for publication: SHRINKING RESTARTING AUTOMATA

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