Multi-tape and multi-head pushdown automata

DOI10.1016/S0019-9958(68)90901-7zbMath0174.02701MaRDI QIDQ5561967

Michael A. Harrison, Oscar H. Ibarra

Publication date: 1968

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

languages, automata, networks

Related Items (39)

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 ⋮ k\(+1\) heads are better than k for PDAs ⋮ Alternating multihead finite automata ⋮ Characterizations of transductions defined by abstract families of transducers ⋮ \( 5^\prime \to 3^\prime\) Watson-Crick pushdown automata ⋮ Asynchronous Parallel Communicating Systems of Pushdown Automata ⋮ Controlled pushdown automata ⋮ Input-Driven Double-Head Pushdown Automata ⋮ Unnamed Item ⋮ 2DST mappings of languages and related problems ⋮ On the Computational Capacity of Parallel Communicating Finite Automata ⋮ Unnamed Item ⋮ Alternation in simple devices ⋮ Relationships between pushdown automata with counters and complexity classes ⋮ On 3-head versus 2-head finite automata ⋮ A note on semilinear sets and bounded-reversal multihead pushdown automata ⋮ On tape-bounded complexity classes and multihead finite automata ⋮ On partially blind multihead finite automata. ⋮ Two-way nested stack automata are equivalent to two-way stack automata ⋮ A useful device for showing the solvability of some decision problems ⋮ Finite automata with multiplication ⋮ Using acceptors as transducers ⋮ Three write heads are as good ask ⋮ New results concerning synchronized finite automata ⋮ One-way simple multihead finite automata ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ Reasoning about strings in databases ⋮ Synchronized finite automata and 2DFA reductions ⋮ Some classes of languages in \(NC^ 1\) ⋮ Pushdown automata with counters ⋮ On two-way multihead automata ⋮ Remarks on multihead pushdown automata and multihead stack automata ⋮ Alternating simple multihead finite automata ⋮ Two-dimensional automata with rotated inputs (projection-type) ⋮ On Computational Power of Partially Blind Automata ⋮ A note on Parikh maps, abstract languages, and decision problems

This page was built for publication: Multi-tape and multi-head pushdown automata