Deterministic Turing machines in the range between real-time and linear-time.

DOI10.1016/S0304-3975(01)00272-9zbMath1061.68053MaRDI QIDQ1853527

Martin Kutrib, Andreas G. Klein

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Turing machinesClosure propertiesAutomataComputational complexityTime hierarchiesFast computationsSpeed-up

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

IN MEMORIAM CHANDRA KINTALA ⋮ A Hierarchy of Fast Reversible Turing Machines

Cites Work

• On proving time constructibility of functions
• On time hierarchies
• On the Computational Complexity of Algorithms
• Real-Time Definable Languages
• Computational Complexity of One-Tape Turing Machine Computations
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Quasi-realtime languages
• One-tape, off-line Turing machine computations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deterministic Turing machines in the range between real-time and linear-time.