On Multi-Head Finite Automata
From MaRDI portal
Publication:5553286
DOI10.1147/rd.105.0388zbMath0168.01303OpenAlexW4237168914MaRDI QIDQ5553286
Publication date: 1966
Published in: IBM Journal of Research and Development (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1147/rd.105.0388
Related Items (46)
One-way reversible multi-head finite automata ⋮ Logarithmic space and permutations ⋮ Finite dP Automata versus 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 ⋮ k\(+1\) heads are better than k for PDAs ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ Tradeoffs for language recognition on alternating machines ⋮ A new complete language for DSPACE(log n) ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Exact Affine Counter Automata ⋮ Tight hierarchy of data-independent multi-head automata ⋮ Jump complexity of finite automata with translucent letters ⋮ On multi-head automata with restricted nondeterminism ⋮ Possibilities of various types of alternating automata ⋮ Unnamed Item ⋮ Remarks on sorting and one-way multihead finite automata ⋮ On the Computational Capacity of Parallel Communicating Finite Automata ⋮ Unnamed Item ⋮ Head and state hierarchies for unary multi-head finite automata ⋮ Linear automata with translucent letters and linear context-free trace languages ⋮ Multihead one-way finite automata ⋮ Alternation in simple devices ⋮ Stack versus sensitivity for one-way automata ⋮ On 3-head versus 2-head finite automata ⋮ Characterizingco-NLby a group action ⋮ On tape-bounded complexity classes and multihead finite automata ⋮ Real-time, constant-space, constant-randomness verifiers ⋮ One-way multihead finite automata and 2-bounded languages ⋮ On the descriptional complexity of Watson-Crick automata ⋮ One-reversal counter machines and multihead automata: revisited ⋮ A useful device for showing the solvability of some decision problems ⋮ Three write heads are as good ask ⋮ Reversible parallel communicating finite automata systems ⋮ One-Reversal Counter Machines and Multihead Automata: Revisited ⋮ One-way simple multihead finite automata ⋮ On the power of two-way multihead quantum finite automata ⋮ On Stateless Multihead Finite Automata and Multihead Pushdown Automata ⋮ One way multihead deterministic finite automata ⋮ STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES ⋮ Remarks on multihead pushdown automata and multihead stack automata
This page was built for publication: On Multi-Head Finite Automata
