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 complexity; restarting automaton; window size; non-recursive trade-off

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

03D10: Turing machines and related notions

Related Items

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

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