Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
From MaRDI portal
Recommendations
Cites work
- Explicit constructions of linear-sized superconcentrators
- Fooling a two way automaton or one pushdown store is better than one counter for two way machines
- scientific article; zbMATH DE number 3121911 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- On the Computational Complexity of Algorithms
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- One-tape, off-line Turing machine computations
- Real time computation
- Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
- Time- and tape-bounded Turing acceptors and AFLs
- Two-Tape Simulation of Multitape Turing Machines
Cited in
(21)- Expanders obtained from affine transformations
- Tape versus queue and stacks: The lower bounds
- k\(+1\) heads are better than k for PDAs
- A separator theorem for one-dimensional graphs under linear mapping
- Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
- On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
- The complexity of matrix transposition on one-tape off-line Turing machines with output tape
- Three one-way heads cannot do string matching
- Two tapes versus one for off-line Turing machines
- On the relationship between the diameter and the size of a boundary of a directed graph
- A note on square rooting of time functions of Turing machines
- The speed of copying on one-tape off-line turing machines
- On 3-pushdown graphs with large separators
- Bounding lemmata for non-deterministic halting times of transfinite Turing machines
- A Nontrivial Lower Bound for an NP Problem on Automata
- scientific article; zbMATH DE number 3988711 (Why is no real title available?)
- scientific article; zbMATH DE number 3997169 (Why is no real title available?)
- scientific article; zbMATH DE number 4117867 (Why is no real title available?)
- On the power of several queues
- Nondeterminism and the clique problem
- The complexity of matrix transposition on one-tape off-line Turing machines
This page was built for publication: Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3748273)
