On the descriptional power of heads, counters, and pebbles

DOI10.1016/j.tcs.2004.04.013zbMath1078.68090OpenAlexW2082543289MaRDI QIDQ1763719

Martin Kutrib

Publication date: 22 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.04.013

zbMATH Keywords

Finite automataState complexityDescriptional complexityNon-recursive trade-offs

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (5)

The chop of languages ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Queue Automata: Foundations and Developments ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ Diving into the queue

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite automata and unary languages
• Halting space-bounded computations
• Lower bounds on the size of sweeping automata
• A note on rebound automata
• Transformational methods and their application to complexity problems
• Relating refined space complexity classes
• Transformational methods and their application to complexity problems. Corrigenda
• Tight lower bounds on the size of sweeping automata
• On non-determinacy in simple computing devices
• A note on multihead automata and context-sensitive languages
• Optimal Simulations between Unary Automata
• On the Succinctness of Different Representations of Languages
• A note on the succinctness of descriptions of deterministic languages
• Succinctness of Descriptions of Unambiguous Context-Free Languages
• State-complexity of finite-state devices, state compressibility and incompressibility
• Nondeterminism and the size of two way finite automata
• Language recognition by marking automata

This page was built for publication: On the descriptional power of heads, counters, and pebbles