Nondeterministic Space is Closed under Complementation
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- The complexity of satisfiability problems: Refining Schaefer's theorem
- \(\Sigma_ 2SPACE(n)\) is closed under complement
- On three-way two-dimensional Turing machines
- A hierarchy of propositional Horn formuls
- A communication hierarchy of parallel computations
- An NL hierarchy
- On ``inherently context-sensitive languages -- an application of complexity cores
- Oracle branching programs and Logspace versus \(P^*\)
- The parallel complexity of finite-state automata problems
- 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
- A lower bound for the nondeterministic space complexity of context-free recognition
- The parallel complexity of coarsest set partition problems
- Using the Hamiltonian path operator to capture NP
- A very hard log-space counting class
- On read-once vs. multiple access to randomness in logspace
- Bridging across the (n) space frontier
- On the power of built-in relations in certain classes of program schemes
- Positive versions of polynomial time
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis
- Succinctness as a source of complexity in logical formalisms
- The alternation hierarchy for sublogarithmic space is infinite
- Context-sensitive transitive closure operators
- Logical and schematic characterization of complexity classes
- The complexity of optimizing finite-state transducers
- Census techniques collapse space classes
- Deterministic versus nondeterministic space in terms of synchronized alternating machines
- DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
- Separating classes in the exponential-time hierarchy from classes in PH
- Reachability and the power of local ordering
- On the power of alternation on reversal-bounded alternating Turing machines with a restriction
- On the parallel complexity of loops
- Space hierarchy theorem revised.
- The complexity of the characteristic and the minimal polynomial.
- 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
- Resolution of Hartmanis' conjecture for NL-hard sparse sets
- A note on closure properties of logspace MOD classes
- Decision algorithms for multiplayer noncooperative games of incomplete information
- Hierarchical information and the synthesis of distributed strategies
- Separability by piecewise testable languages is \textsc{PTime}-complete
- Catalytic space: non-determinism and hierarchy
- On the computational complexity of problems related to distinguishability sets
- Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
- Complexity of deciding detectability in discrete event systems
- Sorting, linear time and the satisfiability problem
- Logic, semigroups and automata on words
- Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
- For completeness, sublogarithmic space is no space.
- The complexity of the exponential output size problem for top-down and bottom-up tree transducers
- Alternating and empty alternating auxiliary stack automata.
- Bounded MSC communication
- The complexity of planarity testing
- A note on logspace optimization
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- Isolation, matching, and counting uniform and nonuniform upper bounds
- What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\)
- A trichotomy for regular simple path queries on graphs
- Closure and nonclosure properties of the classes of compressible and rankable sets
- Clocked population protocols
- Comparing the notions of opacity for discrete-event systems
- On verification of D-detectability for discrete event systems
- Varieties
- Traversability, reconfiguration, and reachability in the gadget framework
- On expressive power of regular realizability problems
- The complexity of graph languages generated by hyperedge replacement
- Unique decipherability in formal languages
- Orbit expandability of automaton semigroups and groups
- On Boolean combinations forming piecewise testable languages
- On the complexity of the word problem for automaton semigroups and automaton groups
- An efficiently solvable graph partition problem to which many problems are reducible
- Collapsing degrees via strong computation
- On lower bounds for read-\(k\)-times branching programs
- NL-printable sets and nondeterministic Kolmogorov complexity
- Computation in networks of passively mobile finite-state sensors
- Bounds in ontology-based data access via circuit complexity
- Parallelizing time with polynomial circuits
- Languages of dot-depth 3/2
- A parametric analysis of the state-explosion problem in model checking
- Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems
- Context-free languages can be accepted with absolutely no space overhead
- A survey of two-dimensional automata theory
- Self-reducibility
- On uniformity within \(NC^ 1\)
- Complementing two-way finite automata
- A computation model with automatic functions and relations as primitive operations
- On the unusual effectiveness of logic in computer science
- Logarithmic space and permutations
- The constraint satisfaction problem and universal algebra
- Alternating demon space is closed under complement and other simulations for sublogarithmic space
- Complexity theory basics: NP and NL
- Space complexity of the directed reachability problem over surface-embedded graphs
- A logical characterization of small 2NFAs
- Turing machines for dummies. Why representations do matter
- Weak and strong one-way space complexity classes
This page was built for publication: Nondeterministic Space is Closed under Complementation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3821586)
