Complexity of multi-head finite automata: origins and directions
From MaRDI portal
Publication:616495
DOI10.1016/J.TCS.2010.08.024zbMATH Open1207.68188OpenAlexW2032744775MaRDI QIDQ616495FDOQ616495
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
Recommendations
- Multi-head finite automata: characterizations, concepts and open problems
- scientific article; zbMATH DE number 3383997
- Some characterizations of multihead finite automata
- A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
- On multi-head automata with restricted nondeterminism
- scientific article; zbMATH DE number 1015106
- Multi-head finite automata: Data-independent versus data-dependent computations
- scientific article; zbMATH DE number 1361488
- scientific article
- Finite dP Automata versus Multi-head Finite Automata
Cites Work
- Title not available (Why is that?)
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- Relations Among Complexity Measures
- On Context-Free Languages
- On non-determinacy in simple computing devices
- On Communicating Finite-State Machines
- On Multi-Head Finite Automata
- Growing context-sensitive languages and Church-Rosser languages
- Title not available (Why is that?)
- On the Succinctness of Different Representations of Languages
- A note on the succinctness of descriptions of deterministic languages
- A regularity test for pushdown machines
- Title not available (Why is that?)
- Finite automata and unary languages
- Descriptional complexity of machines with limited resources
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
- On Goedel speed-up and succinctness of language representations
- Descriptional complexity of bounded context-free languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- State-complexity of finite-state devices, state compressibility and incompressibility
- Title not available (Why is that?)
- Lower bounds on the size of sweeping automata
- Nondeterminism and the size of two way finite automata
- On tape-bounded complexity classes and multihead finite automata
- Church-Rosser Thue systems and formal languages
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- Converting two-way nondeterministic unary automata into simpler automata.
- Mathematical Foundations of Computer Science 2005
- Title not available (Why is that?)
- k + 1 Heads Are Better than k
- Title not available (Why is that?)
- Bounded-reversal multihead finite automata languages
- Classes of languages and linear-bounded automata
- Succinctness of Descriptions of Unambiguous Context-Free Languages
- Fooling a two-way nondeterministic multihead automaton with reversal number restriction
- Multiprocessor automata
- On 3-head versus 2-head finite automata
- The network complexity and the Turing machine complexity of finite functions
- A useful device for showing the solvability of some decision problems
- 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.
- PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
- On the Computational Capacity of Parallel Communicating Finite Automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Returning and non-returning parallel communicating finite automata are equivalent
- Language recognition by marking automata
- NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES
Cited In (29)
- Reversibility of computations in graph-walking automata
- Finite dP Automata versus Multi-head Finite Automata
- A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
- Iterated uniform finite-state transducers on unary languages
- Frugal Encoding in Reversible $\mathcal{MOQA}$ : A Case Study for Quicksort
- Some characterizations of multihead finite automata
- Title not available (Why is that?)
- Automata with Modulo Counters and Nondeterministic Counter Bounds
- Diving into the queue
- A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads
- Tight hierarchy of data-independent multi-head automata
- On multi-head automata with restricted nondeterminism
- Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals
- Prediction of infinite words with automata
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- P AND dP AUTOMATA: UNCONVENTIONAL VERSUS CLASSICAL AUTOMATA
- Title not available (Why is that?)
- Oblivious two-way finite automata: decidability and complexity
- Iterated uniform finite-state transducers on unary languages
- INSIDE THE CLASS OF REGEX LANGUAGES
- From Nondeterministic to Multi-Head Deterministic Finite-State Transducers
- Head and state hierarchies for unary multi-head finite automata
- On the power of two-way multihead quantum finite automata
- Multi-head finite automata: Data-independent versus data-dependent computations
- STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES
- Queue Automata: Foundations and Developments
- Constant-space, constant-randomness verifiers with arbitrarily small error
- Real-time, constant-space, constant-randomness verifiers
- Real-time, constant-space, constant-randomness verifiers
This page was built for publication: Complexity of multi-head finite automata: origins and directions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616495)
