Time- and tape-bounded Turing acceptors and AFLs
From MaRDI portal
Publication:2542726
DOI10.1016/S0022-0000(70)80031-9zbMath0206.28702OpenAlexW1987331423MaRDI QIDQ2542726
Ronald V. Book, Ben Wegbreit, Sheila A. Greibach
Publication date: 1970
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(70)80031-9
Related Items (23)
Unnamed Item ⋮ Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time ⋮ Characterizations of reduction classes modulo oracle conditions ⋮ On alternation ⋮ A model for ergodic automorphisms on groups ⋮ Effective guessing has unlikely consequences ⋮ Bounded query machines: on NP and PSPACE ⋮ Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem ⋮ Unnamed Item ⋮ Comparing complexity classes ⋮ Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines ⋮ Degree-languages: A new concept of acceptance ⋮ Time-space tradeoffs for SAT on nonuniform machines ⋮ Complete sets and the polynomial-time hierarchy ⋮ A note on classes of complements and the LBA-problem ⋮ Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences ⋮ Classes of formal grammars ⋮ Computational complexity of multitape Turing machines and random access machines ⋮ On languages specified by relative acceptance ⋮ Almost-everywhere complexity hierarchies for nondeterministic time ⋮ Alternating time versus deterministic time: A separation ⋮ Tape-bounded Turing acceptors and principal AFLs ⋮ Time-bounded grammars and their languages
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- A generator of context-sensitive languages
- Tape-bounded Turing acceptors and principal AFLs
- On the Computational Complexity of Algorithms
- Variations on pushdown machines (Detailed Abstract)
- Real-Time Definable Languages
- An Approach to a Unified Theory of Automata
- Quasi-realtime languages
- Some Results on Tape-Bounded Turing Machines
- Toward a Theory of Enumerations
- Studies in abstract families of languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Time- and tape-bounded Turing acceptors and AFLs
