Some Results on Tape-Bounded Turing Machines

Cited In (45)

Reversibility of computations in graph-walking automata
A space lower bound for acceptance by one-way \(\Pi_2\)-alternating machines
A note on alternating on-line Turing machines
On tape bounds for single letter alphabet language processing
Bridging across the \(\log(n)\) space frontier
Relating refined space complexity classes
Techniques for separating space complexity classes
A very hard log-space counting class
Computing with graph rewriting systems with priorities
Two-Way Automata versus Logarithmic Space
Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
An optimal lower bound for nonregular languages
Remarks on the complexity of nondeterministic counter languages
The recursion-theoretic structure of complexity classes
Nonexistence of program optimizers in several abstract settings
For completeness, sublogarithmic space is no space.
Tight lower bounds for query processing on streaming and external memory data
Three-dimensional alternating Turing machines with only universal states
Amplification of slight probabilistic advantage at absolutely no cost in space
Complexity of algorithms and computations
Halting space-bounded computations
Multiple equality sets and Post machines
Time- and tape-bounded Turing acceptors and AFLs
Minimal Size of Counters for (Real-Time) Multicounter Automata
A remark on middle space bounded alternating Turing machines
TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
On store languages of language acceptors
Two-way automata versus logarithmic space
Some properties of one-pebble Turing machines with sublogarithmic space
A combinatorial characterization of smooth LTCs and applications
On the computational power of pushdown automata
Space bounds for processing contentless inputs
Two-way non-uniform finite automata
Diagonalization, uniformity, and fixed-point theorems
Two-Way Non-Uniform Finite Automata
A survey of space complexity
A hierarchy result for 2-dimensional TM's operating in small space
A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
Minimum-complexity pairing functions
Bandwidth constraints on problems complete for polynomial time
Some observations concerning alternating Turing machines using small space
Push complexity: optimal bounds and unary inputs
On languages accepted with simultaneous complexity bounds and their ranking problem
Space hierarchy theorem revised.
Infinite games with finite knowledge gaps

This page was built for publication: Some Results on Tape-Bounded Turing Machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5582355)