Speeding-up nondeterministic single-tape off-line computations by one alternation (extended abstract)
From MaRDI portal
Recommendations
- Speeding-up single-tape nondeterministic computations by single alternation, with separation results
- scientific article; zbMATH DE number 5593330
- Fast Simulations of Time-Bounded One-Tape Turing Machines by Space-Bounded Ones
- Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
- scientific article; zbMATH DE number 3984575
- On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals
- scientific article; zbMATH DE number 88942
- Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
- The speed of copying on one-tape off-line turing machines
Cited in
(6)- scientific article; zbMATH DE number 4213433 (Why is no real title available?)
- Alternating time versus deterministic time: A separation
- Speeding-up single-tape nondeterministic computations by single alternation, with separation results
- scientific article; zbMATH DE number 5593330 (Why is no real title available?)
- Complexity of nondeterministic multitape computations based on crossing sequences
- Separation of deterministic, nondeterministic and alternating complexity classes
This page was built for publication: Speeding-up nondeterministic single-tape off-line computations by one alternation (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218136)