Theory of one-tape linear-time Turing machines

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

zbMATH Keywords

regular languageadviceone-way functionfinite state automatonmany-one reducibilitycrossing sequencelow setone-tape Turing machine

Mathematics Subject Classification ID

Related Items (18)

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

This page was built for publication: Theory of one-tape linear-time Turing machines