Theory of one-tape linear-time Turing machines
type: Item
instance of: scholarly article
title: Theory of one-tape linear-time Turing machines
zbMATH Open document ID: 1189.68065
author: Kohtaro Tadaki
author: Tomoyuki Yamakami
author: Jack C. H. Lin
published in: Theoretical Computer Science
publication date: 2009-12-01T00:00:00Z
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 5641349
zbMATH Keywords: one-tape Turing machine
zbMATH Keywords: crossing sequence
zbMATH Keywords: finite state automaton
zbMATH Keywords: regular language
zbMATH Keywords: one-way function
zbMATH Keywords: low set
zbMATH Keywords: advice
zbMATH Keywords: many-one reducibility
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.08.031
OpenAlex ID: W2168431435
cites work: Quantum Computability
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Q3996675
cites work: Logical Reversibility of Computation
cites work: Quantum Complexity Theory
cites work: Alternation
cites work: Q4788608
cites work: Automata that take advice
cites work: Quantum theory, the Church–Turing principle and the universal quantum computer
cites work: On a Class of Stochastic Languages
cites work: Q4942157
cites work: Two Tapes are Better than One for Nondeterministic Machines
cites work: A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
cites work: Finite state verifiers I
cites work: Q4258585
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: The complexity theory companion
cites work: One-tape, off-line Turing machine computations
cites work: Q5592246
cites work: Q3976039
cites work: Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines
cites work: Turing machines that take advice
cites work: On the structure of one-tape nondeterministic Turing machine time hierarchy
cites work: The complexity of optimization problems
cites work: Space-Efficient Deterministic Simulation of Probabilistic Automata
cites work: An NP-complete language accepted in linear time by a one-tape Turing machine
cites work: A context-free language which is not acceptable by a probabilistic automaton
cites work: On alternation
cites work: Probabilistic automata
cites work: A taxonomy of complexity classes of functions
cites work: On stochastic languages
cites work: Q5562601
cites work: Generalized Automata and Stochastic Languages
cites work: The complexity of computing the permanent
cites work: Q4941921
cites work: Q4501686
cites work: \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
DOI: 10.1016/J.TCS.2009.08.031
description: scientific article; zbMATH DE number 5641349