Pages that link to "Item:Q5545959"
From MaRDI portal
The following pages link to Computational Complexity of One-Tape Turing Machine Computations (Q5545959):
Displayed 27 items.
- Verifying time complexity of Turing machines (Q496007) (← links)
- A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes (Q756423) (← links)
- A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems (Q844899) (← links)
- Fast parallel language recognition by cellular automata (Q1075053) (← links)
- On the bit complexity of distributed computations in a ring with a leader (Q1098291) (← links)
- Complexity of algorithms and computations (Q1153141) (← links)
- An NP-complete language accepted in linear time by a one-tape Turing machine (Q1183577) (← links)
- Relations between diagonalization, proof systems, and complexity gaps (Q1254105) (← links)
- Deterministic multitape automata computations (Q1393939) (← links)
- Descriptional complexity of limited automata (Q1706157) (← links)
- Deterministic Turing machines in the range between real-time and linear-time. (Q1853527) (← links)
- Verifying whether one-tape Turing machines run in linear time (Q2009635) (← links)
- Converting nondeterministic two-way automata into small deterministic linear-time machines (Q2105419) (← links)
- Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power (Q2106594) (← links)
- Reversible Limited Automata (Q2945882) (← links)
- (Q3854627) (← links)
- A note on context free languages, complexity classes, and diagonalization (Q3928245) (← links)
- (Q4144800) (← links)
- Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers* (Q5089680) (← links)
- New time hierarchy results for deterministic TMS (Q5096792) (← links)
- Complexity of Nondeterministic Multitape Computations Based on Crossing Sequences (Q5200101) (← links)
- On Simulation Cost of Unary Limited Automata (Q5500689) (← links)
- Computational complexity of random access stored program machines (Q5627619) (← links)
- On restricted turing computability (Q5632561) (← links)
- Descriptional complexity of iterated uniform finite-state transducers (Q5918615) (← links)
- Weight-reducing Turing machines (Q6040666) (← links)
- Iterated uniform finite-state transducers on unary languages (Q6165558) (← links)