Some Results on Tape-Bounded Turing Machines

Cited in

(47)

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

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)