Computational Complexity of One-Tape Turing Machine Computations
From MaRDI portal
Cited in
(28)- Deterministic Turing machines in the range between real-time and linear-time.
- Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
- Converting nondeterministic two-way automata into small deterministic linear-time machines
- Deterministic multitape automata computations
- Relations between diagonalization, proof systems, and complexity gaps
- New time hierarchy results for deterministic TMS
- Reversible limited automata
- A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems
- Descriptional complexity of iterated uniform finite-state transducers
- Complexity of nondeterministic multitape computations based on crossing sequences
- Verifying whether one-tape Turing machines run in linear time
- Weight-reducing Turing machines
- On restricted turing computability
- Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power
- Nondeterminism and the clique problem
- Descriptional complexity of limited automata
- Complexity of algorithms and computations
- Iterated uniform finite-state transducers on unary languages
- Computational complexity of random access stored program machines
- scientific article; zbMATH DE number 3655354 (Why is no real title available?)
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes
- A note on context free languages, complexity classes, and diagonalization
- Fast parallel language recognition by cellular automata
- Verifying time complexity of Turing machines
- An NP-complete language accepted in linear time by a one-tape Turing machine
- On simulation cost of unary limited automata
- On the bit complexity of distributed computations in a ring with a leader
- scientific article; zbMATH DE number 3574987 (Why is no real title available?)
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)
