Fixed-parameter complexity in AI and nonmonotonic reasoning

DOI10.1016/S0004-3702(02)00182-0zbMath0995.68118WikidataQ59259714 ScholiaQ59259714MaRDI QIDQ1603733

Georg Gottlob, Francesco Scarcello, Martha Sideris

Publication date: 15 July 2002

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

nonmonotonic reasoning; logic programming; constraint satisfaction; parameterized complexity; conjunctive queries; circumscription; stable models; prime implicants; mixed-parameter tractability

Mathematics Subject Classification ID

68T37: Reasoning under uncertainty in the context of artificial intelligence

Related Items

Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability, Constraint satisfaction with bounded treewidth revisited, Computational properties of argument systems satisfying graph-theoretic constraints, Logic programming and knowledge representation---The A-Prolog perspective, Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable, Algorithms for propositional model counting, Visualizing SAT instances and runs of the DPLL algorithm, Solving \#SAT using vertex covers, Algorithms for Propositional Model Counting, Complexity and Algorithms for Well-Structured k-SAT Instances

Uses Software

• Smodels

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A theory of diagnosis from first principles
• Constraint satisfaction from a deductive viewpoint
• Tree clustering for constraint networks
• The directed subgraph homeomorphism problem
• A comparison of structural CSP decomposition methods
• Conjunctive-query containment and constraint satisfaction
• Propositional lower bounds: Algorithms and complexity
• Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
• On the Desirability of Acyclic Database Schemes
• The complexity of acyclic conjunctive queries
• Graph minors. II. Algorithmic aspects of tree-width
• A sufficient condition for backtrack-bounded search
• Extremal problems in logic programming and stable model computation
• Closure properties of constraints
• Fixed-Parameter Tractability and Completeness I: Basic Results
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth