Nondeterministic Space is Closed under Complementation
From MaRDI portal
Publication:3821586
DOI10.1137/0217058zbMath0668.68056OpenAlexW2043360684WikidataQ54259208 ScholiaQ54259208MaRDI QIDQ3821586
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/008cc87949facb25b6b63467e18759fbe04f1037
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (only showing first 100 items - show all)
The complexity of optimizing finite-state transducers ⋮ Logarithmic space and permutations ⋮ Census techniques collapse space classes ⋮ Deterministic versus nondeterministic space in terms of synchronized alternating machines ⋮ Weak and strong one-way space complexity classes ⋮ On the sizes of DPDAs, PDAs, LBAs ⋮ Hierarchical information and the synthesis of distributed strategies ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Linearly bounded infinite graphs ⋮ DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization ⋮ The complexity of membership problems for circuits over sets of integers ⋮ Separating classes in the exponential-time hierarchy from classes in PH ⋮ Reachability and the power of local ordering ⋮ On three-way two-dimensional Turing machines ⋮ The language intersection problem for non-recursive context-free grammars ⋮ A hierarchy of propositional Horn formuls ⋮ A communication hierarchy of parallel computations ⋮ Extending inclusion dependencies with conditions ⋮ On the power of alternation on reversal-bounded alternating Turing machines with a restriction ⋮ On the parallel complexity of loops ⋮ Positive and negative proofs for circuits and branching programs ⋮ Boundary sets of regular and context-free languages ⋮ Space hierarchy theorem revised. ⋮ The complexity of the characteristic and the minimal polynomial. ⋮ Model-checking hierarchical structures ⋮ Observations on complete sets between linear time and polynomial time ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Catalytic space: non-determinism and hierarchy ⋮ The complexity of regular DNLC graph languages ⋮ On the computational complexity of problems related to distinguishability sets ⋮ On the structure of linear apex NLC graph grammars ⋮ An alternating hierarchy for finite automata ⋮ New developments in structural complexity theory ⋮ The difference between one tape and two tapes: With respect to reversal complexity ⋮ Passively mobile communicating machines that use restricted space ⋮ A note on algebras of languages ⋮ Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs ⋮ An NL hierarchy ⋮ On ``inherently context-sensitive languages -- an application of complexity cores ⋮ Oracle branching programs and Logspace versus \(P^*\) ⋮ Interval graph representation with given interval and intersection lengths ⋮ Deciding determinism of regular languages ⋮ The parallel complexity of finite-state automata problems ⋮ On almost cylindrical languages and the decidability of the D0L and PWD0L primitivity problems ⋮ The expressiveness of a family of finite set languages ⋮ On the acceptance power of regular languages ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Dynamical properties of PWD0L systems ⋮ Multihead two-way probabilistic finite automata ⋮ The complexity of circuit value and network stability ⋮ The invariant problem for binary string structures and the parallel complexity theory of queries ⋮ Capturing complexity classes by fragments of second-order logic ⋮ A survey of space complexity ⋮ On space-bounded synchronized alternating Turing machines ⋮ Further remarks on DNA overlap assembly ⋮ Alternating space is closed under complement and other simulations for sublogarithmic space ⋮ Computational complexity of finite asynchronous cellular automata ⋮ A lower bound for the nondeterministic space complexity of context-free recognition ⋮ The parallel complexity of coarsest set partition problems ⋮ Methods for proving completeness via logical reductions ⋮ Using the Hamiltonian path operator to capture NP ⋮ Finite-model theory -- A personal perspective ⋮ Low-complexity aggregation in GraphLog and Datalog ⋮ A closed-form evaluation for Datalog queries with integer (gap)-order constraints ⋮ Mediated population protocols ⋮ Correctness of linear logic proof structures is NL-complete ⋮ The computational power of membrane systems under tight uniformity conditions ⋮ A very hard log-space counting class ⋮ On read-once vs. multiple access to randomness in logspace ⋮ The equational complexity of Lyndon's algebra ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ The lexicographically first topological order problem is NLOG-complete ⋮ The strong exponential hierarchy collapses ⋮ Homonym population protocols ⋮ Planar and grid graph reachability problems ⋮ Complexity of deciding detectability in discrete event systems ⋮ The complexity of satisfiability problems: Refining Schaefer's theorem ⋮ On the complexity of topological sorting ⋮ Effective entropies and data compression ⋮ Sorting, linear time and the satisfiability problem ⋮ Logic, semigroups and automata on words ⋮ Bridging across the \(\log(n)\) space frontier ⋮ On the power of built-in relations in certain classes of program schemes ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ A space lower bound for \(st\)-connectivity on node-named JAGs ⋮ A variant of inductive counting ⋮ Positive versions of polynomial time ⋮ Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ Resolution of Hartmanis' conjecture for NL-hard sparse sets ⋮ A note on closure properties of logspace MOD classes ⋮ Succinctness as a source of complexity in logical formalisms ⋮ For completeness, sublogarithmic space is no space. ⋮ The complexity of the exponential output size problem for top-down and bottom-up tree transducers ⋮ The alternation hierarchy for sublogarithmic space is infinite ⋮ A taxonomy of fairness and temporal logic problems for Petri nets ⋮ Finite-automaton aperiodicity is PSPACE-complete ⋮ Context-sensitive transitive closure operators ⋮ Decision algorithms for multiplayer noncooperative games of incomplete information ⋮ Logical and schematic characterization of complexity classes
This page was built for publication: Nondeterministic Space is Closed under Complementation
