ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA

DOI10.1142/S0129054113400212zbMath1309.68121MaRDI QIDQ5401559

Friedrich Otto, Martin Kutrib

Publication date: 10 March 2014

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

zbMATH Keywords

descriptional complexityrestarting automatonwindow sizenon-recursive trade-off

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Turing machines and related notions (03D10)

Related Items (3)

Non-recursive trade-offs between two-dimensional automata and grammars ⋮ Decidability Questions for Insertion Systems and Related Models ⋮ On restarting automata with auxiliary symbols and small window size

Cites Work

• On Goedel speed-up and succinctness of language representations
• On stateless deterministic restarting automata
• Succinct description of regular languages by weak restarting automata
• Complexity of certain decision problems about congruential languages
• ON STATELESS TWO-PUSHDOWN AUTOMATA AND RESTARTING AUTOMATA
• WHEN CHURCH-ROSSER BECOMES CONTEXT FREE
• OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA
• Regularity and Related Problems for Deterministic Pushdown Automata
• Recursive Unsolvability of a problem of Thue
• A regularity test for pushdown machines
• THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS

This page was built for publication: ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA