Bounded treewidth as a key to tractability of knowledge representation and reasoning
From MaRDI portal
Publication:2269134
DOI10.1016/j.artint.2009.10.003zbMath1185.68690OpenAlexW2075530391WikidataQ59259554 ScholiaQ59259554MaRDI QIDQ2269134
Fang Wei, Georg Gottlob, Reinhard Pichler
Publication date: 16 March 2010
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.artint.2009.10.003
treewidthabductiondisjunctive logic programmingfixed-parameter tractabilitymonadic Datalogclosed world reasoning
Related Items (17)
Parametrised Complexity of Satisfiability in Temporal Logic ⋮ Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints ⋮ Recognizable languages of arrows and cospans ⋮ Exploiting Database Management Systems and Treewidth for Counting ⋮ Tractable cases of the extended global cardinality constraint ⋮ Algorithms and complexity results for persuasive argumentation ⋮ Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ On the parameterized complexity of non-monotonic logics ⋮ Counting linear extensions: parameterizations by treewidth ⋮ New width parameters for SAT and \#SAT ⋮ Tractable answer-set programming with weight constraints: bounded treewidth is not enough ⋮ Unnamed Item ⋮ Parameterized Complexity of CTL ⋮ Strong Backdoors for Default Logic ⋮ A multiparametric view on answer set programming ⋮ Backdoors to tractable answer set programming
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monadic second-order evaluations on tree-decomposable graphs
- Safe separators for treewidth
- Safe reduction rules for weighted treewidth
- Digraph measures: Kelly decompositions, games, and orderings
- Rational set of trees and the algebraic semantics of logic programming
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- On the relationship between circumscription and negation as failure
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- All structured programs have small tree width and good register allocation
- The complexity of propositional closed world reasoning and circumscription
- The complexity of first-order and monadic second-order logic revisited
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- On the computational cost of disjunctive logic programming: Propositional case
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Tree acceptors and some of their applications
- MONA IMPLEMENTATION SECRETS
- Easy problems for tree-decomposable graphs
- Query evaluation via tree-decompositions
- Counting Complexity of Minimal Cardinality and Minimal Weight Abduction
- DAG-width
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- The complexity of logic-based abduction
- DAG-Width and Parity Games
- Fast Counting with Bounded Treewidth
- Generalized finite automata theory with an application to a decision problem of second-order logic
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Logic for Programming, Artificial Intelligence, and Reasoning
- Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
This page was built for publication: Bounded treewidth as a key to tractability of knowledge representation and reasoning
