Complete problems for deterministic polynomial time

Cites work

scientific article; zbMATH DE number 3560737 (Why is no real title available?)
scientific article; zbMATH DE number 3571502 (Why is no real title available?)
scientific article; zbMATH DE number 3311755 (Why is no real title available?)
scientific article; zbMATH DE number 3415409 (Why is no real title available?)
An observation on time-storage trade off
Recognition and parsing of context-free languages in time n3
Space-bounded reducibility among combinatorial problems
The complexity of theorem-proving procedures
Unit Refutations and Horn Sets

Cited in

(83)

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

This page was built for publication: Complete problems for deterministic polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1235982)