Complexity of multi-head finite automata: origins and directions
From MaRDI portal
Publication:616495
DOI10.1016/j.tcs.2010.08.024zbMath1207.68188OpenAlexW2032744775MaRDI QIDQ616495
Markus Holzer, Martin Kutrib, Andreas Malcher
Publication date: 10 January 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.024
Related Items (25)
Finite dP Automata versus Multi-head Finite Automata ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Prediction of infinite words with automata ⋮ A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads ⋮ Frugal Encoding in Reversible $\mathcal{MOQA}$ : A Case Study for Quicksort ⋮ Automata with Modulo Counters and Nondeterministic Counter Bounds ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ Tight hierarchy of data-independent multi-head automata ⋮ Queue Automata: Foundations and Developments ⋮ On multi-head automata with restricted nondeterminism ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ Reversibility of computations in graph-walking automata ⋮ Head and state hierarchies for unary multi-head finite automata ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals ⋮ Diving into the queue ⋮ On the power of two-way multihead quantum finite automata ⋮ From Nondeterministic to Multi-Head Deterministic Finite-State Transducers ⋮ P AND dP AUTOMATA: UNCONVENTIONAL VERSUS CLASSICAL AUTOMATA ⋮ INSIDE THE CLASS OF REGEX LANGUAGES ⋮ Constant-space, constant-randomness verifiers with arbitrarily small error ⋮ STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Descriptional complexity of bounded context-free languages
- On Goedel speed-up and succinctness of language representations
- Fooling a two-way nondeterministic multihead automaton with reversal number restriction
- Finite automata and unary languages
- Multiprocessor automata
- Lower bounds on the size of sweeping automata
- On 3-head versus 2-head finite automata
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- On tape-bounded complexity classes and multihead finite automata
- The network complexity and the Turing machine complexity of finite functions
- A useful device for showing the solvability of some decision problems
- Growing context-sensitive languages and Church-Rosser languages
- Converting two-way nondeterministic unary automata into simpler automata.
- Tight lower bounds on the size of sweeping automata
- Multi-head finite automata: Data-independent versus data-dependent computations
- On the descriptional power of heads, counters, and pebbles
- On partially blind multihead finite automata.
- On non-determinacy in simple computing devices
- PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
- On the Computational Capacity of Parallel Communicating Finite Automata
- On Communicating Finite-State Machines
- Church-Rosser Thue systems and formal languages
- 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
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- k + 1 Heads Are Better than k
- Relations Among Complexity Measures
- Bounded-reversal multihead finite automata languages
- State-complexity of finite-state devices, state compressibility and incompressibility
- Nondeterminism and the size of two way finite automata
- Returning and non-returning parallel communicating finite automata are equivalent
- Mathematical Foundations of Computer Science 2005
- On Context-Free Languages
- A regularity test for pushdown machines
- On Multi-Head Finite Automata
- Classes of languages and linear-bounded automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Language recognition by marking automata
- NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
This page was built for publication: Complexity of multi-head finite automata: origins and directions
