Computational Complexity of One-Tape Turing Machine Computations
From MaRDI portal
Cited in
(28)- 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
- scientific article; zbMATH DE number 3655354 (Why is no real title available?)
- A note on context free languages, complexity classes, and diagonalization
- scientific article; zbMATH DE number 3574987 (Why is no real title available?)
- Verifying time complexity of Turing machines
- 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
- Weight-reducing Turing machines
- Iterated uniform finite-state transducers on unary languages
- Nondeterminism and the clique problem
- 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
This page was built for publication: Computational Complexity of One-Tape Turing Machine Computations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5545959)
