Time- and tape-bounded Turing acceptors and AFLs

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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