Trichotomies in the complexity of minimal inference
From MaRDI portal
Publication:692908
DOI10.1007/s00224-011-9320-0zbMath1290.68057MaRDI QIDQ692908
Miki Hermann, Gustav Nordh, Arnaud Durand
Publication date: 6 December 2012
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-011-9320-0
68Q25: Analysis of algorithms and problem complexity
03B60: Other nonclassical logic
68T27: Logic in artificial intelligence
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Bases for Boolean co-clones
- On the relationship between circumscription and negation as failure
- Circumscription - a form of non-monotonic reasoning
- Characterizing diagnoses and systems
- The complexity of model checking for circumscriptive formulae
- The complexity of propositional closed world reasoning and circumscription
- A dichotomy in the complexity of propositional circumscription
- The complexity of minimal satisfiability problems
- Graph minors. XIII: The disjoint paths problem
- The complexity of selecting maximal solutions
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- Closed systems of functions and predicates
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- The Complexity of Circumscriptive Inference in Post’s Lattice
- The algebras of partial functions and their invariants
- Closure properties of constraints
- The complexity of satisfiability problems
- On the Complexity of Some Enumeration Problems for Matroids
- Partial Polymorphisms and Constraint Satisfaction Problems
- Logic for Programming, Artificial Intelligence, and Reasoning
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)