Computational Complexity of One-Tape Turing Machine Computations
From MaRDI portal
Publication:5545959
DOI10.1145/321450.321464zbMath0162.31703MaRDI QIDQ5545959
Publication date: 1968
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/5880
Related Items
Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*, New time hierarchy results for deterministic TMS, Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences, On Simulation Cost of Unary Limited Automata, Computational complexity of random access stored program machines, On restricted turing computability, Descriptional complexity of iterated uniform finite-state transducers, Iterated uniform finite-state transducers on unary languages, Weight-reducing Turing machines, Verifying time complexity of Turing machines, A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes, A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems, Fast parallel language recognition by cellular automata, On the bit complexity of distributed computations in a ring with a leader, Complexity of algorithms and computations, An NP-complete language accepted in linear time by a one-tape Turing machine, Relations between diagonalization, proof systems, and complexity gaps, Deterministic multitape automata computations, Descriptional complexity of limited automata, Deterministic Turing machines in the range between real-time and linear-time., Verifying whether one-tape Turing machines run in linear time, Converting nondeterministic two-way automata into small deterministic linear-time machines, Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power, Reversible Limited Automata, Unnamed Item, A note on context free languages, complexity classes, and diagonalization, Unnamed Item
