On tape-bounded complexity classes and multihead finite automata
From MaRDI portal
Publication:1215271
DOI10.1016/S0022-0000(75)80014-6zbMath0299.68031OpenAlexW1989382950MaRDI QIDQ1215271
Publication date: 1975
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(75)80014-6
Related Items (37)
Alternating on-line Turing machines with only universal states and small space bounds ⋮ On nondeterminism in parallel computation ⋮ Unnamed Item ⋮ k\(+1\) heads are better than k for PDAs ⋮ Alternating multihead finite automata ⋮ Three-dimensional alternating Turing machines with only universal states ⋮ On the parallel complexity of loops ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Tight hierarchy of data-independent multi-head automata ⋮ The complexity of regular DNLC graph languages ⋮ On multi-head automata with restricted nondeterminism ⋮ Two-way deterministic multi-weak-counter machines ⋮ On deciding some equivalences for concurrent processes ⋮ Multihead one-way finite automata ⋮ The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems ⋮ Knapsack problems for NL ⋮ Multihead two-way probabilistic finite automata ⋮ Relativization of questions about log space computability ⋮ Communication for alternating machines ⋮ Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages ⋮ Space-bounded reducibility among combinatorial problems ⋮ First-order logics: some characterizations and closure properties ⋮ Properties of probabilistic pushdown automata ⋮ Bracket-languages are recognizable in logarithmic space ⋮ The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet ⋮ Stack languages and log n space ⋮ Unnamed Item ⋮ Multihead two-way probabilistic finite automata ⋮ One-way simple multihead finite automata ⋮ Some classes of languages in \(NC^ 1\) ⋮ Prediction-preserving reducibility ⋮ Boundedness, empty channel detection, and synchronization for communicating finite automata ⋮ Properties of probabilistic pushdown automata ⋮ From Nondeterministic to Multi-Head Deterministic Finite-State Transducers ⋮ Bandwidth constraints on problems complete for polynomial time ⋮ Alternating simple multihead finite automata ⋮ Multi-head finite automata: Data-independent versus data-dependent computations
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- On non-determinacy in simple computing devices
- A note on multihead automata and context-sensitive languages
- On two-way multihead automata
- One-way multihead writing finite automata
- Bounded-reversal multihead finite automata languages
- On Multi-Head Finite Automata
- Multi-tape and multi-head pushdown automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On tape-bounded complexity classes and multihead finite automata
