On tape-bounded complexity classes and multihead finite automata

DOI10.1016/S0022-0000(75)80014-6zbMath0299.68031OpenAlexW1989382950MaRDI QIDQ1215271

Ivan Hal Sudborough

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: On tape-bounded complexity classes and multihead finite automata