k + 1 Heads Are Better than k

DOI10.1145/322063.322076zbMath0372.68017OpenAlexW2048052050MaRDI QIDQ4148951

Andrew Chi-Chih Yao, Ronald L. Rivest

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322063.322076

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (56)

String-matching cannot be done by a two-head one-way deterministic finite automaton ⋮ One-way reversible multi-head finite automata ⋮ Deterministic versus nondeterministic space in terms of synchronized alternating machines ⋮ One-Way Reversible Multi-head Finite Automata ⋮ On stateless multihead automata: hierarchies and the emptiness problem ⋮ Algebraic languages and polyominoes enumeration ⋮ UNDECIDABILITY AND HIERARCHY RESULTS FOR PARALLEL COMMUNICATING FINITE AUTOMATA ⋮ ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATA ⋮ Hierarchies of one-way multihead automata languages ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ Alternating multihead finite automata ⋮ Tradeoffs for language recognition on alternating machines ⋮ Reversible Watson-Crick automata ⋮ A new complete language for DSPACE(log n) ⋮ Complexity of multi-head finite automata: origins and directions ⋮ On store languages and applications ⋮ Unnamed Item ⋮ Tight hierarchy of data-independent multi-head automata ⋮ Independent finite automata on Cayley graphs ⋮ Remarks on sorting and one-way multihead finite automata ⋮ Fooling a two way automaton or one pushdown store is better than one counter for two way machines ⋮ On the Computational Capacity of Parallel Communicating Finite Automata ⋮ Head and state hierarchies for unary multi-head finite automata ⋮ Multihead one-way finite automata ⋮ QRT FIFO automata, breadth-first grammars and their relations ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ Multihead two-way probabilistic finite automata ⋮ Alternation in simple devices ⋮ On space-bounded synchronized alternating Turing machines ⋮ On problems for which no oracle can help ⋮ PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES ⋮ Stack versus sensitivity for one-way automata ⋮ Binding-blocking automata ⋮ The complexity of ranking simple languages ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ One-way multihead finite automata and 2-bounded languages ⋮ Watson-Crick quantum finite automata ⋮ Three write heads are as good ask ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ Multihead two-way probabilistic finite automata ⋮ One-way simple multihead finite automata ⋮ Synchronized finite automata and 2DFA reductions ⋮ Set Automata ⋮ Unnamed Item ⋮ On Stateless Multihead Finite Automata and Multihead Pushdown Automata ⋮ From Nondeterministic to Multi-Head Deterministic Finite-State Transducers ⋮ One way multihead deterministic finite automata ⋮ STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES ⋮ Remarks on multihead pushdown automata and multihead stack automata ⋮ On the power of real-time two-way multihead finite automata with jumps ⋮ Deterministic two-way one-head pushdown automata are very powerful ⋮ On Computational Power of Partially Blind Automata ⋮ Unnamed Item ⋮ On the power of alternation in automata theory ⋮ Separation of deterministic, nondeterministic and alternating complexity classes ⋮ On the power of synchronization in parallel computations

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