Theory of one-tape linear-time Turing machines
From MaRDI portal
Publication:1041220
DOI10.1016/j.tcs.2009.08.031zbMath1189.68065OpenAlexW2168431435MaRDI QIDQ1041220
Jack C. H. Lin, Tomoyuki Yamakami, Kohtaro Tadaki
Publication date: 1 December 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.031
regular languageadviceone-way functionfinite state automatonmany-one reducibilitycrossing sequencelow setone-tape Turing machine
Related Items
Two-way non-uniform finite automata, A linear-time simulation of deterministic \(d\)-limited automata, Multiple Usage of Random Bits in Finite Automata, Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata, Weight-reducing Turing machines, Expressing power of elementary quantum recursion schemes for quantum logarithmic-time computability, Determinism and Nondeterminism in Finite Automata with Advice, Two-Way Non-Uniform Finite Automata, Immunity and pseudorandomness of context-free languages, Verifying time complexity of Turing machines, Linear-time limited automata, Verifying whether one-tape Turing machines run in linear time, Unnamed Item, How does adiabatic quantum computation fit into quantum automata theory?, Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice, Advice hierarchies among finite automata, FINITE AUTOMATA WITH ADVICE TAPES, Converting nondeterministic two-way automata into small deterministic linear-time machines
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Turing machines that take advice
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- The complexity of optimization problems
- On alternation
- An NP-complete language accepted in linear time by a one-tape Turing machine
- A taxonomy of complexity classes of functions
- \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
- Two Tapes are Better than One for Nondeterministic Machines
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- Automata that take advice
- Alternation
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Computational Complexity of Probabilistic Turing Machines
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Finite state verifiers I
- Quantum Computability
- Quantum Complexity Theory
- Space-Efficient Deterministic Simulation of Probabilistic Automata
- Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines
- Probabilistic automata
- Generalized Automata and Stochastic Languages
- On stochastic languages
- A context-free language which is not acceptable by a probabilistic automaton
- One-tape, off-line Turing machine computations
- On a Class of Stochastic Languages
- Logical Reversibility of Computation
- The complexity theory companion
