On tape-bounded complexity classes and multihead finite automata
From MaRDI portal
Publication:1215271
DOI10.1016/S0022-0000(75)80014-6zbMath0299.68031MaRDI QIDQ1215271
Publication date: 1975
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items
On deciding some equivalences for concurrent processes, Unnamed Item, On multi-head automata with restricted nondeterminism, Complexity of multi-head finite automata: origins and directions, Knapsack problems for NL, Multihead two-way probabilistic finite automata, First-order logics: some characterizations and closure properties, Some classes of languages in \(NC^ 1\), Prediction-preserving reducibility, Bandwidth constraints on problems complete for polynomial time, The complexity of regular DNLC graph languages, Alternating simple multihead finite automata, Alternating on-line Turing machines with only universal states and small space bounds, On nondeterminism in parallel computation, k\(+1\) heads are better than k for PDAs, Alternating multihead finite automata, Three-dimensional alternating Turing machines with only universal states, Two-way deterministic multi-weak-counter machines, Multihead one-way finite automata, The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, Communication for alternating machines, Space-bounded reducibility among combinatorial problems, 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, One-way simple multihead finite automata, Properties of probabilistic pushdown automata, On the parallel complexity of loops, Multi-head finite automata: Data-independent versus data-dependent computations, Boundedness, empty channel detection, and synchronization for communicating finite automata, Tight hierarchy of data-independent multi-head automata, Unnamed Item, Relativization of questions about log space computability, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
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
