Relationships between nondeterministic and deterministic tape complexities

Cites work

scientific article; zbMATH DE number 3311755 (Why is no real title available?)
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)
Relations Between Time and Tape Complexities

Cited in

(only showing first 100 items - show all)

Procedural languages for database queries and updates
On the computational complexity of membrane systems
Approximation in (poly-) logarithmic space
The complexity of rerouting shortest paths
The tape-complexity of context-independent developmental languages
Bandwidth contrained NP-complete problems
Reconfiguration of Steiner trees in an unweighted graph
\(\mathcal{ALCQPI}_{R^+}\): rational grading in an expressive description logic with inverse and transitive roles and counting
A space lower bound for acceptance by one-way \(\Pi_2\)-alternating machines
Constrained synchronization and commutativity
Rewriting of regular expressions and regular path queries
Computational complexity of motion planning of a robot through simple gadgets
Reconfiguration of List Edge-Colorings in a Graph
Push-pull block puzzles are hard
Polynomial size \(\Omega\)-branching programs and their computational power
Playing Savitch and cooking games
A multiprocess network logic with temporal and spatial modalities
A note on three-dimensional finite automata
Matching Trace Patterns with Regular Policies
\textsc{Pull} and \textsc{PushPull} are PSPACE-complete
Symmetric space-bounded computation
Converting nondeterministic two-way automata into small deterministic linear-time machines
The complexity of finding minimum-length generator sequences
Space bounded computations: Review and new separation results
Complete problems for space bounded subclasses of NP
On two problems related to cancellativity
Integrally closed residuated lattices
Runtime monitors for Markov decision processes
Initial-state detectability of stochastic discrete-event systems with probabilistic sensor failures
\(\mathrm P \overset {?} {=} \mathrm{NP}\)
On eliminating nondeterminism from Turing machines which use less than logarithm worktape space
A multiparameter analysis of the boundedness problem for vector addition systems
Generalized Pete's Pike is PSPACE-complete
Relating the power of cellular arrays to their closure properties
The complexity of intersecting finite automata having few final states
On a complexity hierarchy between L and NL
[[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
On inverse deterministic pushdown transductions
Classes of formal grammars
Stack languages and log n space
The computational complexity of scenario-based agent verification and design
On composition and lookahead delegation of \(e\)-services modeled by automata
HyperATL*: A Logic for Hyperproperties in Multi-Agent Systems
On tape-bounded probabilistic Turing machine acceptors
Hardness of deriving invertible sequences from finite state machines
Lower bounds for the modular communication complexity of various graph accessibility problems
Bridging across the \(\log(n)\) space frontier
Characterizations and computational complexity of systolic trellis automata
On the Complexity of Deciding Avoidability of Sets of Partial Words
Subexponentials in non-commutative linear logic
Dynamic logics of the region-based theory of discrete spaces
Evaluation of permanents in rings and semirings
Relating refined space complexity classes
Techniques for separating space complexity classes
Treewidth governs the complexity of target set selection
Verification complexity of a class of observational properties for modular discrete events systems
On regular temporal logics with past
On the contribution of backward jumps to instruction sequence expressiveness
Reset complexity and completely reachable automata with simple idempotents
Towards efficient universal planning: A randomized approach
Temporal reachability minimization: delaying vs. deleting
On the complexity of the word problem for automaton semigroups and automaton groups
The complexity of Grigorchuk groups with application to cryptography
Tape bounds for time-bounded Turing machines
The complexity of N-body simulation
Two-way automata characterizations of L/poly versus NL
Digraph redicolouring
Alternating and empty alternating auxiliary stack automata.
Approximate pattern matching and transitive closure logics.
The complexity of temporal logic over the reals
Some remarks on two-dimensional finite automata
The problem of space invariance for sequential machines
scientific article; zbMATH DE number 7577569 (Why is no real title available?)
Improved witnessing and local improvement principles for second-order bounded arithmetic
Finite-model theory -- A personal perspective
Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems
Model-checking hierarchical structures
On the finite-valuedness problem for sequential machines
On the coalgebraic theory of Kleene algebra with tests
Non deterministic polynomial optimization problems and their approximations
Bisimilarity of Diagrams
The shortest path reconfiguration problem based on relaxation of reconfiguration rules
New problems complete for nondeterministic log space
Separation logics and modalities: a survey
Comparing complexity classes
The propositional dynamic logic of deterministic, well-structured programs
Two-Way Automata versus Logarithmic Space
Complexity of some problems in Petri nets
Computational complexity of reversible reaction systems
Reversible Kleene lattices
Extending the description logic \(\mathcal{EL}\) with threshold concepts induced by concept measures
Quasi-interpretations. A way to control resources
Dynamic point labeling is strongly PSPACE-complete
scientific article; zbMATH DE number 7754308 (Why is no real title available?)
Compaction and separation algorithms for non-convex polygons and their applications
White pebbles help
Games with Opacity Condition
Universal traversal sequences for expander graphs
Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)

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)