Fixed-parameter complexity in AI and nonmonotonic reasoning

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

Martha Sideris, Francesco Scarcello, Georg Gottlob

Publication date: 15 July 2002

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

zbMATH Keywords

nonmonotonic reasoninglogic programmingconstraint satisfactionparameterized complexityconjunctive queriescircumscriptionstable modelsprime implicantsmixed-parameter tractability

Mathematics Subject Classification ID

Reasoning under uncertainty in the context of artificial intelligence (68T37)

Related Items (29)

Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability ⋮ Constraint satisfaction with bounded treewidth revisited ⋮ Dealing with several parameterized problems by random methods ⋮ Parameterized algorithms for edge biclique and related problems ⋮ Unnamed Item ⋮ Parameterized complexity classes beyond para-NP ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ Algorithms for Propositional Model Counting ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ On the complexity of planning for agent teams and its implications for single agent planning ⋮ On the parameterized complexity of non-monotonic logics ⋮ Visualizing SAT instances and runs of the DPLL algorithm ⋮ Solving \#SAT using vertex covers ⋮ New width parameters for SAT and \#SAT ⋮ An improved kernel for max-bisection above tight lower bound ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ Tractable structures for constraint satisfaction with truth tables ⋮ Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable ⋮ Algorithms for propositional model counting ⋮ Strong Backdoors for Default Logic ⋮ Computational properties of argument systems satisfying graph-theoretic constraints ⋮ A multiparametric view on answer set programming ⋮ DynASP2.5: Dynamic Programming on Tree Decompositions in Action ⋮ Unnamed Item ⋮ Backdoors to tractable answer set programming ⋮ Logic programming and knowledge representation---The A-Prolog perspective

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

This page was built for publication: Fixed-parameter complexity in AI and nonmonotonic reasoning