Tape-reversal bounded Turing machine computations

DOI10.1016/S0022-0000(68)80027-3zbMath0259.68020MaRDI QIDQ2560051

Juris Hartmanis

Publication date: 1968

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Turing machines and related notions (03D10)

Related Items

Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs, On reversal bounded alternating Turing machines, Complexity theory of parallel time and hardware, Computational complexity of random access stored program machines, Complexity of algorithms and computations, On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals, The difference between one tape and two tapes: With respect to reversal complexity, On the relationship between deterministic time and deterministic reversal, Reversal-bounded multipushdown machines, One way finite visit automata, Improved average complexity for comparison-based sorting, Multitape one-way nonwriting automata, Complexity problems in real time languages, A characterization of reversal-bounded multipushdown machine languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Real time computation
• Nonerasing stack automata
• The reduction of tape reversals for off-line one-tape Turing machines
• Classes of Predictably Computable Functions
• On the Computational Complexity of Algorithms
• Recognition and parsing of context-free languages in time n3
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On the Recognition of Primes by Automata
• Unrecognizable Sets of Numbers
• On the Complexity of Undecidable Problems in Automata Theory