Nondeterministic Space is Closed under Complementation
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Some modifications of auxiliary pushdown automata
- Pseudo-deterministic proofs
- Planar and grid graph reachability problems
- Extensions of an idea of McNaughton
- A closed-form evaluation for Datalog queries with integer (gap)-order constraints
- Low-complexity aggregation in GraphLog and Datalog
- Correctness of linear logic proof structures is NL-complete
- Passively mobile communicating machines that use restricted space
- scientific article; zbMATH DE number 6970796 (Why is no real title available?)
- Automata theory and model checking
- Comparing the notions of opacity for discrete-event systems
- scientific article; zbMATH DE number 4080941 (Why is no real title available?)
- Expressive Power of Broadcast Consensus Protocols
- Bridging across the (n) space frontier
- Using the Hamiltonian path operator to capture NP
- scientific article; zbMATH DE number 7561616 (Why is no real title available?)
- Orbit expandability of automaton semigroups and groups
- Interval graph representation with given interval and intersection lengths
- Deciding determinism of regular languages
- A note on read-$k$ times branching programs
- Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
- On the complexity of the word problem for automaton semigroups and automaton groups
- The equational complexity of Lyndon's algebra
- Logarithmic space and permutations
- On the power of alternation on reversal-bounded alternating Turing machines with a restriction
- A very hard log-space counting class
- Alternating and empty alternating auxiliary stack automata.
- Inherent vacuity in lattice automata
- On completeness for NP via projection translations
- Finite-model theory -- A personal perspective
- Model-checking hierarchical structures
- Structure and importance of logspace-MOD class
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
- A hierarchy that does not collapse : alternations in low level space
- Positive versions of polynomial time
- The complexity of satisfiability problems: Refining Schaefer's theorem
- Computational complexity of finite asynchronous cellular automata
- The computational power of membrane systems under tight uniformity conditions
- On three-way two-dimensional Turing machines
- On read-once vs. multiple access to randomness in logspace
- A trichotomy for regular simple path queries on graphs
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
- Linearly bounded infinite graphs
- Relativized logspace and generalized quantifiers over finite ordered structures
- For completeness, sublogarithmic space is no space.
- Unique decipherability in formal languages
- Space complexity of the directed reachability problem over surface-embedded graphs
- On the power of built-in relations in certain classes of program schemes
- Mediated population protocols
- The complexity of graph connectivity
- Completeness for nondeterministic complexity classes
- Lattice Automata
- Hierarchical information and the synthesis of distributed strategies
- Descriptive complexity for counting complexity classes
- On Boolean combinations forming piecewise testable languages
- Bounded MSC communication
- A hierarchy of propositional Horn formuls
- DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
- Weak cardinality theorems
- Logical and schematic characterization of complexity classes
- Homonym population protocols
- Weak and strong one-way space complexity classes
- On the sizes of DPDAs, PDAs, LBAs
- The lexicographically first topological order problem is NLOG-complete
- The parallel complexity of finite-state automata problems
- A communication hierarchy of parallel computations
- Varieties
- New developments in structural complexity theory
- The complexity of graph languages generated by hyperedge replacement
- Methods for proving completeness via logical reductions
- The parameterized space complexity of model-checking bounded variable first-order logic
- On the structure of linear apex NLC graph grammars
- An alternating hierarchy for finite automata
- Succinctness as a source of complexity in logical formalisms
- scientific article; zbMATH DE number 4087055 (Why is no real title available?)
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- A logical characterization of small 2NFAs
- scientific article; zbMATH DE number 7533347 (Why is no real title available?)
- An unambiguous class possessing a complete set
- An efficiently solvable graph partition problem to which many problems are reducible
- A logical characterization of small 2NFAs
- StUSPACE(log n) ⊂-DSPACE(log2 n/log log n)
- The language intersection problem for non-recursive context-free grammars
- Tailoring recursion for complexity
- Complexity of deciding detectability in discrete event systems
- Complexity theory basics: NP and NL
- Derandomizing isolation in space-bounded settings
- Deterministic versus nondeterministic space in terms of synchronized alternating machines
- Hierarchies in transitive closure logic, stratified Datalog and infinitary logic
- A Trichotomy for Regular Trail Queries
- On the complexity of topological sorting
- Minimal and hyper-minimal biautomata
- Collapsing degrees via strong computation
- \(\Sigma_ 2SPACE(n)\) is closed under complement
- The complexity of membership problems for circuits over sets of integers
- scientific article; zbMATH DE number 7204396 (Why is no real title available?)
- On verification of D-detectability for discrete event systems
- On the synchronization of semi-traces
- Closure and nonclosure properties of the classes of compressible and rankable sets
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)
