Bounded treewidth as a key to tractability of knowledge representation and reasoning
From MaRDI portal
Publication:2269134
Recommendations
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- All structured programs have small tree width and good register allocation
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution
- Counting Complexity of Minimal Cardinality and Minimal Weight Abduction
- Counting truth assignments of formulas of bounded tree-width or clique-width
- DAG-width
- DAG-Width and Parity Games
- Digraph measures: Kelly decompositions, games, and orderings
- Easy problems for tree-decomposable graphs
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Fast Counting with Bounded Treewidth
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3976378 (Why is no real title available?)
- scientific article; zbMATH DE number 25192 (Why is no real title available?)
- scientific article; zbMATH DE number 1142315 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1926662 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- scientific article; zbMATH DE number 1424025 (Why is no real title available?)
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Logic for Programming, Artificial Intelligence, and Reasoning
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- MONA IMPLEMENTATION SECRETS
- Monadic second-order evaluations on tree-decomposable graphs
- Normal form transformations
- On the computational cost of disjunctive logic programming: Propositional case
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- On the relationship between circumscription and negation as failure
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- Query evaluation via tree-decompositions
- Rational set of trees and the algebraic semantics of logic programming
- Safe reduction rules for weighted treewidth
- Safe separators for treewidth
- The complexity of first-order and monadic second-order logic revisited
- The complexity of logic-based abduction
- The complexity of propositional closed world reasoning and circumscription
- Tree acceptors and some of their applications
- Treewidth: computational experiments
Cited in
(22)- Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints
- Counting linear extensions: parameterizations by treewidth
- New width parameters for SAT and \#SAT
- A multiparametric view on answer set programming
- Backdoors to tractable answer set programming
- Tractable cases of the extended global cardinality constraint
- Parameterized complexity of CTL
- Strong Backdoors for Default Logic
- Belief Revision with Bounded Treewidth
- Recognizable languages of arrows and cospans
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- On the parameterized complexity of non-monotonic logics
- Tractable QBF by knowledge compilation
- Treewidth in non-ground answer set solving and alliance problems in graphs
- Parametrised complexity of satisfiability in temporal logic
- Tractable answer-set programming with weight constraints: bounded treewidth is not enough
- Exploiting Database Management Systems and Treewidth for Counting
- Algorithms and complexity results for persuasive argumentation
- Reasoning in assumption-based argumentation using tree-decompositions
- Strong backdoors for default logic
- Strong backdoors for default logic
- Enumeration of minimal hitting sets parameterized by treewidth
This page was built for publication: Bounded treewidth as a key to tractability of knowledge representation and reasoning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2269134)
