Trichotomies in the complexity of minimal inference

DOI10.1007/S00224-011-9320-0zbMATH Open1290.68057OpenAlexW2168335621MaRDI QIDQ692908FDOQ692908

Authors: Arnaud Durand, Miki Hermann, Gustav Nordh 

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

Recommendations

• Logic for Programming, Artificial Intelligence, and Reasoning
• The Complexity of Minimal Inference Problem for Conservative Constraint Languages
• The complexity of minimal inference problem for conservative constraint languages
• Minimal inference problem over finite domains: the landscape of complexity
• scientific article; zbMATH DE number 1884382

Mathematics Subject Classification ID

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

Cites Work

• The complexity of selecting maximal solutions
• Graph minors. XIII: The disjoint paths problem
• Complexity classifications of Boolean constraint satisfaction problems
• Closure properties of constraints
• The complexity of satisfiability problems
• The algebras of partial functions and their invariants
• Closed systems of functions and predicates
• Title not available (Why is that?)
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Characterizing diagnoses and systems
• The complexity of model checking for circumscriptive formulae
• On the relationship between circumscription and negation as failure
• Circumscription - a form of non-monotonic reasoning
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• Title not available (Why is that?)
• The Complexity of Circumscriptive Inference in Post’s Lattice
• Title not available (Why is that?)
• The complexity of minimal satisfiability problems
• The complexity of propositional closed world reasoning and circumscription
• Title not available (Why is that?)
• Logic for Programming, Artificial Intelligence, and Reasoning
• Partial Polymorphisms and Constraint Satisfaction Problems
• Title not available (Why is that?)
• On the Complexity of Some Enumeration Problems for Matroids
• Bases for Boolean co-clones
• A dichotomy in the complexity of propositional circumscription

Cited In (3)

• Logic for Programming, Artificial Intelligence, and Reasoning
• On the complexity of semantic self-minimization
• Minimal inference problem over finite domains: the landscape of complexity

This page was built for publication: Trichotomies in the complexity of minimal inference

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