Pages that link to "Item:Q1235982"
From MaRDI portal
The following pages link to Complete problems for deterministic polynomial time (Q1235982):
Displaying 50 items.
- The incremental maintenance of a depth-first-search tree in directed acyclic graphs (Q286984) (← links)
- Complexity of equations over sets of natural numbers (Q633764) (← links)
- Regular languages of nested words: fixed points, automata, and synchronization (Q649107) (← links)
- Synthesis from component libraries with costs (Q683714) (← links)
- Algorithms for the maximum satisfiability problem (Q753502) (← links)
- Prediction-preserving reducibility (Q756441) (← links)
- Priority systems with many identical processes (Q758201) (← links)
- The Nielsen reduction and P-complete problems in free groups (Q760500) (← links)
- Nivat's processing systems: decision problems related to protection and synchronization (Q761796) (← links)
- The complexity of the satisfiability problem for Krom formulas (Q800915) (← links)
- New techniques for proving the decidability of equivalence problem (Q913523) (← links)
- Parallel models of computation: An introductory survey (Q916358) (← links)
- Incremental branching programs (Q929291) (← links)
- Depth-first search is inherently sequential (Q1062456) (← links)
- Complete problems in the first-order predicate calculus (Q1075318) (← links)
- On the construction of parallel computers from various basis of Boolean functions (Q1083204) (← links)
- The equivalence of finite valued transducers (on HDT0L languages) is decidable (Q1090467) (← links)
- Automata-theoretic techniques for modal logics of programs (Q1090675) (← links)
- The parallel complexity of deadlock detection (Q1091805) (← links)
- An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems (Q1097037) (← links)
- Parallel complexity of logical query programs (Q1104095) (← links)
- The word and generator problems for lattices (Q1105626) (← links)
- A topological approach to dynamic graph connectivity (Q1108030) (← links)
- On the complexity of deciding fair termination of probabilistic concurrent finite-state programs (Q1111384) (← links)
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation (Q1111776) (← links)
- Alternating multihead finite automata (Q1116353) (← links)
- Optimizing propositional calculus formulas with regard to questions of deducibility (Q1117918) (← links)
- A hierarchy of propositional Horn formuls (Q1122571) (← links)
- Stratification and knowledge base management (Q1122994) (← links)
- \(\varepsilon\)-productions in context-free grammars (Q1148693) (← links)
- The equivalence of Horn and network complexity for Boolean functions (Q1160604) (← links)
- The maximum flow problem is log space complete for P (Q1165000) (← links)
- Arithmetizing uniform \(NC\) (Q1176198) (← links)
- Iterated stack automata and complexity classes (Q1183602) (← links)
- Oracle branching programs and Logspace versus \(P^*\) (Q1183604) (← links)
- Capturing complexity classes by fragments of second-order logic (Q1193408) (← links)
- Two \(P\)-complete problems in the theory of the reals (Q1203649) (← links)
- Recognition of \(q\)-Horn formulae in linear time (Q1337669) (← links)
- On problems with short certificates (Q1338895) (← links)
- A short certificate of the number of universal optimal strategies for stopping simple stochastic games (Q1350746) (← links)
- The unique Horn-satisfiability problem and quadratic Boolean equations. (Q1353999) (← links)
- Computational complexity and constraint logic programming languages (Q1354033) (← links)
- Polynomial-time inference of all valid implications for Horn and related formulae (Q1356205) (← links)
- On the parallel complexity of loops (Q1391751) (← links)
- McNaughton families of languages. (Q1401181) (← links)
- Interconvertibility of a class of set constraints and context-free-language reachability (Q1583350) (← links)
- Pushdown reachability with constant treewidth (Q1675921) (← links)
- Reversible pushdown automata (Q1757838) (← links)
- Sorting, linear time and the satisfiability problem (Q1817067) (← links)
- Resolution deduction to detect satisfiability for another class including non-Horn sentences in propositional logic (Q1819946) (← links)
