k + 1 Heads Are Better than k

Cited in

(56)

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

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)