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

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item