scientific article; zbMATH DE number 4087055
From MaRDI portal
Publication:3815544
Recommendations
Cited in
(51)- The method of forced enumeration for nondeterministic automata
- [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
- Space bounded computations: Review and new separation results
- Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\)
- An NL hierarchy
- Oracle branching programs and Logspace versus \(P^*\)
- Some properties of space-bounded synchronized alternating Turing machines with universal states only
- Using the Hamiltonian path operator to capture NP
- Sparse hard sets for P: Resolution of a conjecture of Hartmanis
- -languages for sets and LOGSPACE computable graph transformers
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
- Resolution of Hartmanis' conjecture for NL-hard sparse sets
- Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
- The complexity of graph languages generated by hyperedge replacement
- Unique decipherability in formal languages
- On lower bounds for read-\(k\)-times branching programs
- Bounds in ontology-based data access via circuit complexity
- Parallelizing time with polynomial circuits
- Languages of dot-depth 3/2
- Self-reducibility
- Turing machines for dummies. Why representations do matter
- Inconsistency-Tolerant Querying of Description Logic Knowledge Bases
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- Factorization in formal languages
- Complexity of boundary graph languages
- scientific article; zbMATH DE number 4080941 (Why is no real title available?)
- Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
- Nondeterministic Space is Closed under Complementation
- Extending inclusion dependencies with conditions
- Completeness for nondeterministic complexity classes
- Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
- Separating \oplus L from L, NL, co-NL, and AL = P for oblivious Turing machines of linear access
- Random walks on colored graphs
- A note on read-k times branching programs
- The parameterized space complexity of model-checking bounded variable first-order logic
- Reversals and alternation
- The complexity of graph connectivity
- Empty alternation
- Generalized predecessor existence problems for Boolean finite dynamical systems
- Mediated population protocols
- Correctness of linear logic proof structures is NL-complete
- The computational power of membrane systems under tight uniformity conditions
- On the power of parity polynomial time
- The lexicographically first topological order problem is NLOG-complete
- On the difference set of two transductions
- Language-theoretic problems arising from Richelieu cryptosystems
- Local proofs approaching the witness length
- On the complexity of topological sorting
- Boundary sets of regular and context-free languages
- New developments in structural complexity theory
- Polynomial size \(\Omega\)-branching programs and their computational power
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815544)
