Complete problems for deterministic polynomial time
From MaRDI portal
Publication:1235982
DOI10.1016/0304-3975(76)90068-2zbMath0352.68068OpenAlexW1999647826MaRDI QIDQ1235982
William T. Laaser, Neil D. Jones
Publication date: 1977
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(76)90068-2
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)
Related Items
On the Average Case Complexity of Some P-complete Problems, On the construction of parallel computers from various basis of Boolean functions, COMPUTATIONAL COMPLEXITY OF GENERATORS AND NONGENERATORS IN ALGEBRA, The incremental maintenance of a depth-first-search tree in directed acyclic graphs, Recognition of \(q\)-Horn formulae in linear time, Logic programs and connectionist networks, On problems with short certificates, The equivalence of finite valued transducers (on HDT0L languages) is decidable, Automata-theoretic techniques for modal logics of programs, The parallel complexity of deadlock detection, Bounded self-stabilizing Petri nets, An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems, A short certificate of the number of universal optimal strategies for stopping simple stochastic games, The unique Horn-satisfiability problem and quadratic Boolean equations., Computational complexity and constraint logic programming languages, On the parallel complexity of discrete relaxation in constraint satisfaction networks, Polynomial-time inference of all valid implications for Horn and related formulae, Deadlocks and traps in Petri nets as Horn-satisfiability solutions and some related polynomially solvable problems, Parallel complexity of logical query programs, The word and generator problems for lattices, A topological approach to dynamic graph connectivity, On the complexity of deciding fair termination of probabilistic concurrent finite-state programs, LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation, Alternating multihead finite automata, Optimizing propositional calculus formulas with regard to questions of deducibility, Games for active XML revisited, A hierarchy of propositional Horn formuls, Stratification and knowledge base management, Pushdown reachability with constant treewidth, Testing membership: Beyond permutation groups, On the parallel complexity of loops, The complexity of searching implicit graphs, On the complexity of decision problems for some classes of machines and applications, McNaughton families of languages., \(\varepsilon\)-productions in context-free grammars, On the complexity of computational problems associated with simple stochastic games, Complexity of equations over sets of natural numbers, New techniques for proving the decidability of equivalence problem, The equivalence of Horn and network complexity for Boolean functions, DECIDABILITY AND COMPLEXITY ANALYSIS OF FORBIDDEN STATE PROBLEMS FOR DISCRETE EVENT SYSTEMS, Parallel models of computation: An introductory survey, The maximum flow problem is log space complete for P, Regular languages of nested words: fixed points, automata, and synchronization, Maximum renamable Horn sub-CNFs, Incremental branching programs, Arithmetizing uniform \(NC\), Iterated stack automata and complexity classes, Oracle branching programs and Logspace versus \(P^*\), The complexity of searching succinctly represented graphs, Capturing complexity classes by fragments of second-order logic, Extending regular expressions with homomorphic replacement, Synthesis from component libraries with costs, New problems complete for nondeterministic log space, Complexity and expressive power of second‐order extended Horn logic, Complexity results for prefix grammars, Two \(P\)-complete problems in the theory of the reals, Reversible pushdown automata, The complexity of linear programming, COMPUTATIONAL COMPLEXITY OF TERM-EQUIVALENCE, Classes of bounded nondeterminism, On the complexity of some problems on groups input as multiplication tables, Computational complexity of some problems involving congruences on algebras, Descriptional complexity of iterated uniform finite-state transducers, Complexity of some problems concerningL systems, Unnamed Item, Algorithms for the maximum satisfiability problem, On digital nondeterminism, Sorting, linear time and the satisfiability problem, Prediction-preserving reducibility, Priority systems with many identical processes, Resolution deduction to detect satisfiability for another class including non-Horn sentences in propositional logic, The Nielsen reduction and P-complete problems in free groups, Nivat's processing systems: decision problems related to protection and synchronization, The lexicographically first maximal subgraph problems:P-completeness andNC algorithms, Idempotent n -permutable varieties, Interconvertibility of a class of set constraints and context-free-language reachability, The complexity of the exponential output size problem for top-down and bottom-up tree transducers, On the space and circuit complexity of parameterized problems: classes and completeness, The complexity of the satisfiability problem for Krom formulas, Depth-first search is inherently sequential, Complete problems in the first-order predicate calculus
Cites Work
