Computational Complexity of One-Tape Turing Machine Computations
From MaRDI portal
Publication:5545959
DOI10.1145/321450.321464zbMath0162.31703OpenAlexW2087008115MaRDI 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
A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems, On the bit complexity of distributed computations in a ring with a leader, Unnamed Item, Unnamed Item, Computational complexity of random access stored program machines, Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*, On restricted turing computability, Reversible Limited Automata, New time hierarchy results for deterministic TMS, Weight-reducing Turing machines, Deterministic multitape automata computations, Complexity of algorithms and computations, Descriptional complexity of limited automata, An NP-complete language accepted in linear time by a one-tape Turing machine, Verifying time complexity of Turing machines, Iterated uniform finite-state transducers on unary languages, Verifying whether one-tape Turing machines run in linear time, Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences, Relations between diagonalization, proof systems, and complexity gaps, Descriptional complexity of iterated uniform finite-state transducers, A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes, On Simulation Cost of Unary Limited Automata, A note on context free languages, complexity classes, and diagonalization, Deterministic Turing machines in the range between real-time and 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, Fast parallel language recognition by cellular automata
