Relationships between nondeterministic and deterministic tape complexities

Cites work

A Machine-Independent Theory of the Complexity of Recursive Functions
Classes of computable functions defined by bounds on computation
Deterministic simulation of non-deterministic Turing machines (detailed abstract)
scientific article; zbMATH DE number 3311755 (Why is no real title available?)
Relations Between Time and Tape Complexities

Cited in

(only showing first 100 items - show all)

A Rice-style theorem for parallel automata
State complexity of unique rational operations
Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts
Detecting palindromes, patterns and borders in regular languages
The complexity of finding minimum-length generator sequences
A multiprocess network logic with temporal and spatial modalities
Consistency in nondeterministic storage
Complete problems for space bounded subclasses of NP
On some natural complete operators
On two problems related to cancellativity
Inclusion dependencies and their interaction with functional dependencies
Complexity results on the conjugacy problem for monoids
On bounded query machines
Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n) NSPACE( \,n)
The problem of space invariance for sequential machines
Relating the power of cellular arrays to their closure properties
Relativized alternation and space-bounded computation
White pebbles help
On a complexity hierarchy between L and NL
A measure of relativized space which is faithful with respect to depth
The power of nondeterminism in polynomial-size bounded-width branching programs
Complexity theory of parallel time and hardware
[[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
A note on the best-case complexity
On iterative and cellular tree arrays
Compaction and separation algorithms for non-convex polygons and their applications
A communication hierarchy of parallel computations
Uniform data encodings
A simulation result for the auxiliary pushdown automata
Tree-size bounded alternation
Lower bounds on the size of sweeping automata
An extension of Savitch's theorem to small space bounds
Non deterministic polynomial optimization problems and their approximations
Complexity of algorithms and computations
Bounded query machines: on NP and PSPACE
On tape-bounded probabilistic Turing machine acceptors
A note on three-dimensional finite automata
Symmetric space-bounded computation
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
On the computational complexity of satisfiability in propositional logics of programs
On the finite-valuedness problem for sequential machines
Space bounded computations: Review and new separation results
Datalog extensions for database queries and updates
The complexity of Grigorchuk groups with application to cryptography
On the power of white pebbles
The complexity of problems involving structurally bounded and conservative Petri nets
Oracle branching programs and Logspace versus \(P^*\)
Expected parallel time and sequential space complexity of graph and digraph problems
A survey of space complexity
Some remarks on two-dimensional finite automata
On tape-bounded complexity classes and multihead finite automata
Splitting a context-sensitive set
The tape-complexity of context-independent developmental languages
Space-bounded reducibility among combinatorial problems
Translational lemmas, polynomial time, and \((\log n)^j\)-space
Comparing complexity classes
Remarks on the complexity of nondeterministic counter languages
On the equivalence, containment, and covering problems for the regular and context-free languages
A characterization of the power of vector machines
Van Wijngaarden grammars and space complexity class EXSPACE
The covering problem for linear context-free grammars
Some clarifications of the concept of a Garden-of-Eden configuration
Techniques for separating space complexity classes
Relating refined space complexity classes
The polynomial-time hierarchy
Degree-languages: A new concept of acceptance
Complexity of some problems in Petri nets
The covering and boundedness problems for vector addition systems
Log space machines with multiple oracle tapes
On inverse deterministic pushdown transductions
Nondeterminism and Boolean operations in pda's
Classes of formal grammars
Stack languages and log n space
Bridging across the (n) space frontier
\(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
The relative power of logspace and polynomial time reductions
Context-sensitive transitive closure operators
Logical and schematic characterization of complexity classes
Computability and complexity of ray tracing
\(\text{RL}\subseteq \text{SC}\)
Some descriptive-set-theoretical problems in complexity theory
Census techniques collapse space classes
The complexity of connectivity problems on context-free graph languages
Space-efficient recognition of sparse self-reducible languages
The computational complexity of propositional STRIPS planning
A remark on middle space bounded alternating Turing machines
A hierarchy for nondeterministic time complexity
The complexity of the temporal logic with ``until over general linear time
Space hierarchy theorem revised.
Mathematical modal logic: A view of its evolution
A space lower bound for \(st\)-connectivity on node-named JAGs
A variant of inductive counting
Time-space tradeoffs for satisfiability
Voronoi-like nondeterministic partition of a lattice by collectives of finite automata
Decision algorithms for multiplayer noncooperative games of incomplete information
Computing observers from observation policies in discrete-event systems
LARS: a logic-based framework for analytic reasoning over streams
Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
Verification complexity of a class of observational properties for modular discrete events systems

This page was built for publication: Relationships between nondeterministic and deterministic tape complexities

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