Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
From MaRDI portal
Publication:3748273
DOI10.2307/2000238zbMath0608.03013OpenAlexW4251801053MaRDI QIDQ3748273
Publication date: 1985
Full work available at URL: https://doi.org/10.2307/2000238
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Related Items
On the relationship between the diameter and the size of a boundary of a directed graph, 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, On the power of several queues, The complexity of matrix transposition on one-tape off-line Turing machines with output tape, On 3-pushdown graphs with large separators, The speed of copying on one-tape off-line turing machines, The complexity of matrix transposition on one-tape off-line Turing machines, Three one-way heads cannot do string matching, Two tapes versus one for off-line Turing machines
Cites Work
- Unnamed Item
- Unnamed Item
- Fooling a two way automaton or one pushdown store is better than one counter for two way machines
- Explicit constructions of linear-sized superconcentrators
- Real time computation
- Time- and tape-bounded Turing acceptors and AFLs
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- Speed-Up of Turing Machines with One Work Tape and a Two-Way Input Tape
- On the Computational Complexity of Algorithms
- Two-Tape Simulation of Multitape Turing Machines
- One-tape, off-line Turing machine computations
