OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA

DOI10.1142/S0129054108005966MaRDI QIDQ3526536zbMATH OpenFDO

Authors Martin Kutrib, Jens Reimann

Publication date 25 September 2008

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

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

zbMATH Keywords

alternating finite automatafinite automata simulationsstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Succinct description of regular languages by weak restarting automata
• On the descriptional complexity of deterministic ordered restarting automata
• scientific article; zbMATH DE number 1836418
• On special forms of restarting automata
• On the descriptional complexity of stateless deterministic ordered restarting automata

Cites work

• State-complexity of finite-state devices, state compressibility and incompressibility
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS

Cited in

(6)

• Descriptional complexity of regular languages
• Optimal simulations between unary automata
• On the Descriptional Complexity of the Window Size for Deterministic Restarting Automata
• On restarting automata with window size one
• On the descriptional complexity of the window size for deleting restarting automata
• Succinct description of regular languages by weak restarting automata

This page was built for publication: OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA

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