Relationships between nondeterministic and deterministic tape complexities

Related Items

Equivalence classes and conditional hardness in massively parallel computations, Decidability of order-based modal logics, Quantum alternation, On the complexity of the word problem for automaton semigroups and automaton groups, Turing Machines for Dummies, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, Collapsing degrees via strong computation, On lower bounds for read-$k$-times branching programs, The computational complexity of scenario-based agent verification and design, Deciding unifiability and computing local unifiers in the description logic $\mathcal{EL}$ without top constructor, Proof compression and NP versus PSPACE, Unnamed Item, Multi-agent conformant planning with distributed knowledge, Reconfiguration of List Edge-Colorings in a Graph, A survey of two-dimensional automata theory, Positive relativizations for log space computability, On efficient deterministic simulation of turing machine computations below logaspace, Longest common subsequence in sublinear space, Initial-state detectability of stochastic discrete-event systems with probabilistic sensor failures, The Computational Complexity of Portal and Other 3D Video Games, Space-Efficient Algorithms for Longest Increasing Subsequence, Reachability is harder for directed than for undirected finite graphs, On the Complexity of Reconfiguration in Systems with Legacy Components, Computational Complexity Via Finite Types, PSPACE-Completeness of Bloxorz and of Games with 2-Buttons, Regular matching and inclusion on compressed tree patterns with constrained context variables, Characterizations of reduction classes modulo oracle conditions, RelativizedNC, Complexity of Planning in Action Formalisms Based on Description Logics, Efficient verification of concurrent systems using local-analysis-based approximations and SAT solving, The complexity of searching implicit graphs, Computational complexity of the word problem in modal and Heyting algebras with a small number of generators, COMPUTATIONALLY AND ALGEBRAICALLY COMPLEX FINITE ALGEBRA MEMBERSHIP PROBLEMS, Verifying chemical reaction network implementations: a bisimulation approach, Complexity of planning for connected agents in a partially known environment, Reconfiguring (non-spanning) arborescences, Model checking and synthesis for branching multi-weighted logics, Ordering regular languages and automata: complexity, Discriminative Model Checking, Classifying the computational complexity of problems, Sublinear-space approximation algorithms for Max $r$-SAT, Hardness of Deriving Invertible Sequences from Finite State Machines, To satisfy impatient web surfers is hard, On groups presented by inverse-closed finite confluent length-reducing rewriting systems, TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE, $\mathcal{ALCQPI}_{R^+}$: rational grading in an expressive description logic with inverse and transitive roles and counting, DEL-based epistemic planning: decidability and complexity, The Complexity of (List) Edge-Coloring Reconfiguration Problem, Computing with cells: membrane systems – some complexity issues, A framework for linear authorization logics, Finite Automata, Palindromes, Powers, and Patterns, A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines, On the Coalgebraic Theory of Kleene Algebra with Tests, Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties, Constrained synchronization and commutativity, Two-Way Automata versus Logarithmic Space, Safety in grammatical protection systems, Two-way automata versus logarithmic space, COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE, Maze recognizing automata and nondeterministic tape complexity, A note on the fast computation of transitive closure of graphs and the multiplication of integer matrices, Hierarchies of recursive computations†, Approximation in (Poly-) logarithmic space, Matching Trace Patterns with Regular Policies, On Bounded Symport/Antiport P Systems, Model checking for hybrid branching-time logics, Determinizing monitors for HML with recursion, Knowledge-based programs as succinct policies for partially observable domains, Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster, The Computational Complexity of Estimating MCMC Convergence Time, Reconfiguration of Steiner Trees in an Unweighted Graph, Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs, Algebraic Complexity Classes, On the Complexity of Deciding Avoidability of Sets of Partial Words, Hard problems that quickly become very easy, Time- and tape-bounded Turing acceptors and AFLs, $$P\mathop{ =}\limits^{?}NP$$, Complexity of intuitionistic propositional logic and its fragments, What's decidable about weighted automata?, Games with Opacity Condition, Dynamic logics of the region-based theory of discrete spaces, Tape bounds for time-bounded Turing machines, Verifying Chemical Reaction Network Implementations: A Bisimulation Approach, Writing stack acceptors, Varieties, Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata, A note on multihead automata and context-sensitive languages, On composition and lookahead delegation of $e$-services modeled by automata, PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation, The size-change principle and dependency pairs for termination of term rewriting, On determinism versus nondeterminism in P systems, Primitive Sets of Nonnegative Matrices and Synchronizing Automata, Compressing BMC Encodings with QBF, A modal logic of epistemic games, Soft Linear Logic and Polynomial Complexity Classes, Converting nondeterministic two-way automata into small deterministic linear-time machines, Non-deterministic cellular automata and languages, Reset complexity and completely reachable automata with simple idempotents, Two-way automata characterizations of L/poly versus NL, On the computational complexity of reaction systems, revisited, Computability and complexity of ray tracing, $\text{RL}\subseteq \text{SC}$, Alternating and empty alternating auxiliary stack automata., Approximate pattern matching and transitive closure logics., 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, Model checking mobile ambients, Computing observers from observation policies in discrete-event systems, The complexity of planarity testing, Bounded self-stabilizing Petri nets, A remark on middle space bounded alternating Turing machines, LARS: a logic-based framework for analytic reasoning over streams, A communication hierarchy of parallel computations, 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, Uniform data encodings, On relationships between complexity classes of Turing machines, A simulation result for the auxiliary pushdown automata, Reconfiguration in bounded bandwidth and tree-depth, A hierarchy for nondeterministic time complexity, The complexity of the temporal logic with ``until over general linear time, Space hierarchy theorem revised., Tree-size bounded alternation, Lower bounds on the size of sweeping automata, Separability by piecewise testable languages is \textsc{PTime}-complete, An extension of Savitch's theorem to small space bounds, Non deterministic polynomial optimization problems and their approximations, Complexity of algorithms and computations, On the descriptional complexity of stateless deterministic ordered restarting automata, Bounded query machines: on NP and PSPACE, On tape-bounded probabilistic Turing machine acceptors, A note on three-dimensional finite automata, Time and space complexity for splicing systems, Mathematical modal logic: A view of its evolution, 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^*$, Towards efficient universal planning: A randomized approach, Expected parallel time and sequential space complexity of graph and digraph problems, On the transformation capability of feasible mechanisms for programmable matter, Space-efficient algorithms for longest increasing subsequence, 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, PSPACE-completeness of modular supervisory control problems, Deciding global partial-order properties, 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 formal methods approach to predicting new features of the eukaryotic vesicle traffic system, 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, Diagnosability of repairable faults, 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, Universal traversal sequences for expander graphs, Computing the throughput of a network with dedicated lines, Bridging across the $\log(n)$ space frontier, A multiparameter analysis of the boundedness problem for vector addition systems, Boundedness, empty channel detection, and synchronization for communicating finite automata, Bandwidth contrained NP-complete problems, Domino-tiling games, A simple linear expected time algorithm for finding a Hamilton path, A space lower bound for $st$-connectivity on node-named JAGs, A variant of inductive counting, Time-space tradeoffs for satisfiability, $\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})$, The complexity of the word problems for commutative semigroups and polynomial ideals, On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata, Voronoi-like nondeterministic partition of a lattice by collectives of finite automata, The relative power of logspace and polynomial time reductions, Is your model checker on time? On the complexity of model checking for timed modal logics, Context-sensitive transitive closure operators, Decision algorithms for multiplayer noncooperative games of incomplete information, Logical and schematic characterization of complexity classes, \textsc{Pull} and \textsc{PushPull} are PSPACE-complete, Integrally closed residuated lattices, On bounded query machines, Runtime monitors for Markov decision processes, On the complexity of existence of homing sequences for nondeterministic finite state machines, Efficient algorithms for membership in Boolean hierarchies of regular languages, Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)$\neq NSPACE(\log \,n)$, Prognosis of $\omega$-languages for the diagnosis of *-languages: a topological perspective, The problem of space invariance for sequential machines, Relating the power of cellular arrays to their closure properties, A generalization of Spira's theorem and circuits with small segregators or separators, Relativized alternation and space-bounded computation, White pebbles help, The complexity of intersecting finite automata having few final states, On a complexity hierarchy between L and NL, On selective unboundedness of VASS, 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, On the computational complexity of membrane systems, The logarithmic alternation hierarchy collapses: $A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}$, A note on the best-case complexity, On iterative and cellular tree arrays, On the complexity of deciding avoidability of sets of partial words, Compaction and separation algorithms for non-convex polygons and their applications, Extending inclusion dependencies with conditions, The complexity of rerouting shortest paths, Evaluation of permanents in rings and semirings, Model-checking hierarchical structures, Generalized Pete's Pike is PSPACE-complete, On the complexity of reconfiguration problems, Recurrence and transience for finite probabilistic tables, The complexity of temporal logic over the reals, Topological invariants of classification problems, Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree, Complexity of independent set reconfigurability problems, New developments in structural complexity theory, If deterministic and nondeterministic space complexities are equal for log log n, then they are also equal for log n, Parallel models of computation: An introductory survey, Polynomial size $\Omega$-branching programs and their computational power, The depth of resolution proofs, On the convergence of query evaluation, Treewidth governs the complexity of target set selection, The difference between one tape and two tapes: With respect to reversal complexity, A note on algebras of languages, On the computational complexity of behavioral description-based web service composition, Bounded memory Dolev-Yao adversaries in collaborative systems, The complexity of deciding reachability properties of distributed negotiation schemes, An improved time-space lower bound for tautologies, Incremental branching programs, Two-way automata making choices only at the endmarkers, Reversal complexity revisited, Space-efficient biconnected components and recognition of outerplanar graphs, Approximability of the subset sum reconfiguration problem, Interval logics and their decision procedures. I: An interval logic, Reversible simulation of space-bounded computations, Decreasing the bandwidth of a transition matrix, Multihead two-way probabilistic finite automata, Refining complexity analyses in planning by exploiting the exponential time hypothesis, Complexity of fixed-size bit-vector logics, Automata can show PSpace results for description logics, Undirected $s$--$t$ connectivity in polynomial time and sublinear space, Alternating space is closed under complement and other simulations for sublogarithmic space, CNF and DNF succinct graph encodings, Regular languages viewed from a graph-theoretic perspective, Finite-model theory -- A personal perspective, Recursively indefinite databases, Feasibility analysis of sporadic real-time multiprocessor task systems, On the contribution of backward jumps to instruction sequence expressiveness, Non-determinism in Gödel's system $T$, Rewriting of regular expressions and regular path queries, Collaborative planning with confidentiality, Quasi-interpretations. A way to control resources, Two-way unary automata versus logarithmic space, On regular temporal logics with past, Reconfiguration of list edge-colorings in a graph, Complexity of token swapping and its variants, Inclusion dependencies and their interaction with functional dependencies in SQL, Efficient model checking for LTL with partial order snapshots, A Rice-style theorem for parallel automata, Procedural languages for database queries and updates, 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, Bandwidth constraints on problems complete for polynomial time, Characterizations and computational complexity of systolic trellis automata, The complexity of monadic recursion schemes: executability problems, nesting depth, and applications, The complexity of finding minimum-length generator sequences, A multiprocess network logic with temporal and spatial modalities, Consistency in nondeterministic storage, The complexity of two-player games of incomplete information, The propositional dynamic logic of deterministic, well-structured programs, On oblivious branching programs of linear length, Complete problems for space bounded subclasses of NP, On some natural complete operators, Finite-automaton aperiodicity is PSPACE-complete, On two problems related to cancellativity, Inclusion dependencies and their interaction with functional dependencies, Complexity results on the conjugacy problem for monoids, On the Decidability of Elementary Modal Logics, Push-Pull Block Puzzles are Hard, PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE, The subpower membership problem for semigroups, On the Model Checking Problem for Some Extension of CTL*, Unnamed Item, Formulas versus Circuits for Small Distance Connectivity, Random walks on colored graphs, An Improved Time-Space Lower Bound for Tautologies, Unnamed Item, Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems, A decidable timeout-based extension of linear temporal logic, If deterministic and nondeterministic space complexities are equal for log log n then they are also equal for log n, Lower bounds for the modular communication complexity of various graph accessibility problems, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, The complexity of graph connectivity, Separation logics and modalities: a survey, Unnamed Item, Bisimilarity of Diagrams, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, Space-efficient algorithms for reachability in directed geometric graphs, Synchronization of Parikh automata, On the Simon's congruence neighborhood of languages, The tail-recursive fragment of timed recursive CTL, What is an inference rule?, Parameterized complexity of optimizing list vertex-coloring through reconfiguration, Time and Gödel: fuzzy temporal reasoning in PSPACE, Conversational recommendation: theoretical model and complexity analysis, Optimal controller synthesis for timed systems, HyperATL*: A Logic for Hyperproperties in Multi-Agent Systems, Digraph redicolouring, Computational complexity of reversible reaction systems, Extending the description logic $\mathcal{EL}$ with threshold concepts induced by concept measures, Separating complexity classes related to bounded alternating ?-branching programs, Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification, Synchronizing words under \textsf{LTL} constraints, On the formalization and computational complexity of resilience problems for cyber-physical systems, The Bounded and Precise Word Problems for Presentations of Groups, Simple Optimal Hitting Sets for Small-Success RL, Tight space-noise tradeoffs in computing the ergodic measure, Unnamed Item, Unnamed Item, Unnamed Item, Computational Complexity of Atomic Chemical Reaction Networks, Unnamed Item, Unnamed Item, Unnamed Item, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, Knowledge-based programs, The complexity of N-body simulation, The complexity of searching succinctly represented graphs, A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems, Improved witnessing and local improvement principles for second-order bounded arithmetic, New problems complete for nondeterministic log space, Relativization of questions about log space computability, On the complexity of finite, pushdown, and stack automata, Recursive turing machines †, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, Investigations on Automata and Languages Over a Unary Alphabet, Size, index, and context-sensitivity of controlled partition grammars, Inclusion complete tally languages and the Hartmanis-Berman conjecture, Traversability, reconfiguration, and reachability in the gadget framework, Playing Savitch and Cooking Games, Lower bounds for the majority communication complexity of various graph accessibility problems, Unnamed Item, Unnamed Item, Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect, Computational complexity of some problems involving congruences on algebras, Unification in the Description Logic $\mathcal{EL}$ without the Top Concept, Unnamed Item, Some Results on the Expressive Power and Complexity of LSCs, Restricted Chase Termination for Existential Rules: A Hierarchical Approach and Experimentation, Unnamed Item, Unnamed Item, Unnamed Item, Multihead two-way probabilistic finite automata, Diameter of colorings under Kempe changes, Unsolvability of the knot problem for surface complexes, Unary coded PSPACE-complete languages in $\mathrm{ASPACE}(\log\log n)$, Unary coded PSPACE-complete languages in $\mathrm{ASPACE}(\log\log n)$, Approximation in (Poly-) Logarithmic Space, The Perfect Matching Reconfiguration Problem, Derandomizing Isolation in Space-Bounded Settings, The Complexity of Model-Checking Tail-Recursive Higher-Order Fixpoint Logic, Subexponentials in non-commutative linear logic, Unnamed Item, UNARY CODED NP-COMPLETE LANGUAGES IN ASPACE(log log n), Reversible Kleene lattices, On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata, Complexity of One-Way Cellular Automata, RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION, Complexities of Some Problems Related to Synchronizing, Non-Synchronizing and Monotonic Automata, Everything Is PSPACE-Complete in Interaction Systems, DYNAMIC POINT LABELING IS STRONGLY PSPACE-COMPLETE, Complexity of Coloring Reconfiguration under Recolorability Constraints, On the Satisfiability and Model Checking for one Parameterized Extension of Linear-time Temporal Logic, More on Minimizing Finite Automata with Errors — Nondeterministic Machines, Temporal Logic of Minkowski Spacetime, (Semi)alternating stack automata, A P systems variant for reasoning about sequential controllability of Boolean networks, On some open problems concerning the complexity of cellular arrays, Synchronizing deterministic push-down automata can be really hard, Space efficient algorithm for solving reachability using tree decomposition and separators, The pumping lemma for regular languages is hard, Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets

Cites Work