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

closure propertieslanguage classesrestarting automatonsimulation

Mathematics Subject Classification ID

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

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

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

Cited in

(23)

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