Complexity of multi-head finite automata: origins and directions
From MaRDI portal
Publication:616495
DOI10.1016/j.tcs.2010.08.024zbMath1207.68188MaRDI 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
68Q45: Formal languages and automata
Related Items
Queue Automata: Foundations and Developments, 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, STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES, Unnamed Item, P AND dP AUTOMATA: UNCONVENTIONAL VERSUS CLASSICAL AUTOMATA, INSIDE THE CLASS OF REGEX LANGUAGES, On multi-head automata with restricted nondeterminism, Descriptional complexity of two-way pushdown automata with restricted head reversals, Head and state hierarchies for unary multi-head finite automata, Iterated uniform finite-state transducers on unary languages, Prediction of infinite words with automata, Tight hierarchy of data-independent multi-head automata, Reversibility of computations in graph-walking automata, Oblivious two-way finite automata: decidability and complexity, Finite dP Automata versus Multi-head Finite Automata, Automata with Modulo Counters and Nondeterministic Counter Bounds, 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
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
