k + 1 Heads Are Better than k

Cited In (56)

Stateless one-way multi-head finite automata with pebbles
Binding-blocking automata
Independent finite automata on Cayley graphs
Tradeoffs for language recognition on alternating machines
PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
Stack versus sensitivity for one-way automata
The complexity of ranking simple languages
Alternation in simple devices
String-matching cannot be done by a two-head one-way deterministic finite automaton
One-way reversible multi-head finite automata
Synchronized finite automata and 2DFA reductions
On the Computational Capacity of Parallel Communicating Finite Automata
Title not available (Why is that?)
Set automata
One-reversal counter machines and multihead automata: revisited
A new complete language for DSPACE(log n)
On Stateless Multihead Finite Automata and Multihead Pushdown Automata
One way multihead deterministic finite automata
Tight hierarchy of data-independent multi-head automata
Algebraic languages and polyominoes enumeration
On the power of synchronization in parallel computations
Complexity of multi-head finite automata: origins and directions
Title not available (Why is that?)
On the computational capacity of parallel communicating finite automata
Undecidability and hierarchy results for parallel communicating finite automata
Deterministic versus nondeterministic space in terms of synchronized alternating machines
Deterministic two-way one-head pushdown automata are very powerful
Watson-Crick quantum finite automata
QRT FIFO automata, breadth-first grammars and their relations
Alternating multihead finite automata
From Nondeterministic to Multi-Head Deterministic Finite-State Transducers
Reversible Watson-Crick automata
Title not available (Why is that?)
Head and state hierarchies for unary multi-head finite automata
One-way multihead finite automata and 2-bounded languages
Multihead two-way probabilistic finite automata (extended abstract)
Three write heads are as good ask
One-way simple multihead finite automata
On stateless multihead automata: hierarchies and the emptiness problem
On store languages and applications
Remarks on sorting and one-way multihead finite automata
Hierarchies of one-way multihead automata languages
Remarks on multihead pushdown automata and multihead stack automata
Multihead two-way probabilistic finite automata
Multihead one-way finite automata
On the power of real-time two-way multihead finite automata with jumps
On space-bounded synchronized alternating Turing machines
One-way reversible multi-head finite automata
THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
Separation of deterministic, nondeterministic and alternating complexity classes
On problems for which no oracle can help
On computational power of partially blind automata
Fooling a two way automaton or one pushdown store is better than one counter for two way machines
Real-time, constant-space, constant-randomness verifiers
Real-time, constant-space, constant-randomness verifiers
On the power of alternation in automata theory

This page was built for publication: k + 1 Heads Are Better than k

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4148951)