Trichotomies in the complexity of minimal inference

DOI10.1007/s00224-011-9320-0zbMath1290.68057OpenAlexW2168335621MaRDI 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Other nonclassical logic (03B60) Logic in artificial intelligence (68T27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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)