The Complexity of Minimal Inference Problem for Conservative Constraint Languages

DOI10.1145/3301410MaRDI QIDQ4633640zbMATH OpenOpenAlexWikidataFDO

Authors Michał Wrona

Publication date 3 May 2019

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3301410

zbMATH Keywords

algebraic approachcircumscriptioncommonsense reasoningcomputational complexityminimal inference problemnonmonotonic reasoningSchaefer's frameworktractability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic in artificial intelligence (68T27)

Recommendations

• The complexity of minimal inference problem for conservative constraint languages
• Complexity of conservative constraint satisfaction problems
• The complexity of maximal constraint languages
• Minimal inference problem over finite domains: the landscape of complexity
• On the minimal constraint satisfaction problem: complexity and generation
• Logical Aspects of Computational Linguistics
• Tractability by approximating constraint languages
• Conservative constraint satisfaction re-revisited
• The complexity of minimal satisfiability problems

Cited in

(3)

• Minimal inference problem over finite domains: the landscape of complexity
• The complexity of minimal inference problem for conservative constraint languages
• Trichotomies in the complexity of minimal inference

This page was built for publication: The Complexity of Minimal Inference Problem for Conservative Constraint Languages

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