Fixed-parameter complexity in AI and nonmonotonic reasoning
From MaRDI portal
Publication:1603733
DOI10.1016/S0004-3702(02)00182-0zbMATH Open0995.68118WikidataQ59259714 ScholiaQ59259714MaRDI QIDQ1603733FDOQ1603733
Authors: Georg Gottlob, Francesco Scarcello, Martha Sideri 
Publication date: 15 July 2002
Published in: Artificial Intelligence (Search for Journal in Brave)
Recommendations
constraint satisfactionnonmonotonic reasoningparameterized complexityconjunctive querieslogic programmingcircumscriptionstable modelsprime implicantsmixed-parameter tractability
Cites Work
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- The directed subgraph homeomorphism problem
- Title not available (Why is that?)
- Closure properties of constraints
- A theory of diagnosis from first principles
- A comparison of structural CSP decomposition methods
- Conjunctive-query containment and constraint satisfaction
- Graph minors. II. Algorithmic aspects of tree-width
- Fixed-Parameter Tractability and Completeness I: Basic Results
- On the Desirability of Acyclic Database Schemes
- Title not available (Why is that?)
- The complexity of acyclic conjunctive queries
- Title not available (Why is that?)
- Tree clustering for constraint networks
- A sufficient condition for backtrack-bounded search
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Declarative problem-solving using the DLV system
- Constraint satisfaction from a deductive viewpoint
- Extremal problems in logic programming and stable model computation
- Propositional lower bounds: Algorithms and complexity
Cited In (34)
- Bounded treewidth as a key to tractability of knowledge representation and reasoning
- Strong backdoors for default logic
- Strong Backdoors for Default Logic
- Data reductions, fixed parameter tractability, and random weighted \(d\)-CNF satisfiability
- Title not available (Why is that?)
- Parameterized algorithms for edge biclique and related problems
- An improved kernel for max-bisection above tight lower bound
- Tractable structures for constraint satisfaction with truth tables
- Constraint satisfaction with bounded treewidth revisited
- Visualizing SAT instances and runs of the DPLL algorithm
- New width parameters for SAT and \#SAT
- An improved FPT algorithm for almost forest deletion problem
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- A multiparametric view on answer set programming
- Solving infinite-domain CSPs using the patchwork property
- On the complexity of planning for agent teams and its implications for single agent planning
- Strong backdoors for default logic
- Solving \#SAT using vertex covers
- Title not available (Why is that?)
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- Algorithms for propositional model counting
- DynASP2.5: Dynamic Programming on Tree Decompositions in Action
- Fixed-parameter complexity of semantics for logic programs
- Computational properties of argument systems satisfying graph-theoretic constraints
- Backdoors to tractable answer set programming
- On the parameterized complexity of non-monotonic logics
- Logic programming and knowledge representation---The A-Prolog perspective
- Algorithms for Propositional Model Counting
- Parameterized complexity classes beyond para-NP
- Dealing with several parameterized problems by random methods
- Complexity and Algorithms for Well-Structured k-SAT Instances
- Improved kernel results for some FPT problems based on simple observations
- Fixed-parameter algorithms for closed world reasoning
- Sum-of-Products with Default Values: Algorithms and Complexity Results
Uses Software
This page was built for publication: Fixed-parameter complexity in AI and nonmonotonic reasoning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1603733)
