On two-way multihead automata

DOI10.1016/S0022-0000(73)80048-0zbMath0256.68028OpenAlexW1968302689MaRDI QIDQ2559145

Oscar H. Ibarra

Publication date: 1973

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(73)80048-0

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (47)

Gradually intractable problems and nondeterministic log-space lower bounds ⋮ PARALLEL COMMUNICATING PUSHDOWN AUTOMATA SYSTEMS ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ k\(+1\) heads are better than k for PDAs ⋮ Alternating multihead finite automata ⋮ Tradeoffs for language recognition on alternating machines ⋮ A new complete language for DSPACE(log n) ⋮ \( 5^\prime \to 3^\prime\) Watson-Crick pushdown automata ⋮ Halting space-bounded computations ⋮ Unnamed Item ⋮ Subclasses of \textsc{Ptime} interpreted by programming languages ⋮ Generalizations of Checking Stack Automata: Characterizations and Hierarchies ⋮ Time complexity of languages recognized by one-way multihead pushdown 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 ⋮ Unnamed Item ⋮ NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES ⋮ Multihead two-way probabilistic finite automata ⋮ PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES ⋮ Binding-blocking automata ⋮ Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages ⋮ Some results concerning automata on two-dimensional tapes ⋮ On tape-bounded complexity classes and multihead finite automata ⋮ Remarks on the complexity of nondeterministic counter languages ⋮ Two-dimensional finite automata and unacceptable functions ⋮ Returning and non-returning parallel communicating finite automata are equivalent ⋮ Techniques for separating space complexity classes ⋮ Relating refined space complexity classes ⋮ Classes of formal grammars ⋮ Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities ⋮ New results concerning synchronized finite automata ⋮ Stack languages and log n space ⋮ A Polynomial Time Match Test for Large Classes of Extended Regular Expressions ⋮ Multihead two-way probabilistic finite automata ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ On the power of two-way multihead quantum finite automata ⋮ On Stateless Multihead Finite Automata and Multihead Pushdown Automata ⋮ Remarks on multihead pushdown automata and multihead stack automata ⋮ Alternating simple multihead finite automata ⋮ Deterministic two-way one-head pushdown automata are very powerful ⋮ On efficient recognition of transductions and relations ⋮ Some undecidable problems for parallel communicating finite automata systems ⋮ Multi-head finite automata: Data-independent versus data-dependent computations

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Two-Tape Simulation of Multitape Turing Machines
• Multi-tape and multi-head pushdown automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• A Note Concerning Nondeterministic Tape Complexities
• Time and tape complexity of pushdown automaton languages

This page was built for publication: On two-way multihead automata