scientific article
From MaRDI portal
zbMath0664.68082MaRDI QIDQ3815544
Publication date: 1987
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Turing Machines for Dummies, On lower bounds for read-\(k\)-times branching programs, Factorization in Formal Languages, Efficient algorithms for membership in Boolean hierarchies of regular languages, Completeness for nondeterministic complexity classes, The method of forced enumeration for nondeterministic automata, Self-reducibility, Random walks on colored graphs, The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\), Unnamed Item, Complexity of boundary graph languages, Bounds in ontology-based data access via circuit complexity, Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines, Extending inclusion dependencies with conditions, Reversals and alternation, The complexity of graph connectivity, Empty alternation, \(\Delta\)-languages for sets and LOGSPACE computable graph transformers, Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access, Boundary sets of regular and context-free languages, Parallelizing time with polynomial circuits, Inconsistency-Tolerant Querying of Description Logic Knowledge Bases, New developments in structural complexity theory, Polynomial size \(\Omega\)-branching programs and their computational power, Space bounded computations: Review and new separation results, Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs, Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\), A note on read-$k$ times branching programs, An NL hierarchy, Oracle branching programs and Logspace versus \(P^*\), Some properties of space-bounded synchronized alternating Turing machines with universal states only, Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata, Language-theoretic problems arising from Richelieu cryptosystems, Using the Hamiltonian path operator to capture NP, On the power of parity polynomial time, Languages of dot-depth 3/2, Mediated population protocols, Correctness of linear logic proof structures is NL-complete, The computational power of membrane systems under tight uniformity conditions, The lexicographically first topological order problem is NLOG-complete, The complexity of graph languages generated by hyperedge replacement, Unique decipherability in formal languages, On the complexity of topological sorting, Non-cancellative Boolean circuits: A generalization of monotone boolean circuits, Sparse hard sets for P: Resolution of a conjecture of Hartmanis, Resolution of Hartmanis' conjecture for NL-hard sparse sets, Generalized Predecessor Existence Problems for Boolean Finite Dynamical Systems
