Default logic and bounded treewidth

DOI10.1007/978-3-319-77313-1_10MaRDI QIDQ5915667zbMATH OpenOpenAlexFDO

Authors Johannes K. Fichte, Markus Hecher, Irina Schindler

Publication date 26 June 2018

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.09393

zbMATH Keywords

dynamic programmingparameterized algorithmspropositional logicReiter's default logictree decompositions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Logic in artificial intelligence (68T27) Knowledge representation (68T30) Analysis of algorithms (68W40)

Abstract: In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (Ext). Our algorithm can even be used to enumerate all generating defaults (ExtEnum) that lead to stable extensions. We show that our algorithm decides Ext in linear time in the input theory and triple exponential time in the treewidth (so-called fixed-parameter linear algorithm). Further, our algorithm solves ExtEnum with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions.

Recommendations

• Default logic and bounded treewidth
• Bounded tree-width and LOGCFL
• Bounded Tree-Width and LOGCFL
• Treewidth with a quantifier alternation revisited
• The tree width of separation logic with recursive definitions
• Extension complexity, MSO logic, and treewidth
• Extension complexity, MSO logic, and treewidth
• A lower bound for treewidth and its consequences
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics

Cited in

(6)

• Bounded treewidth as a key to tractability of knowledge representation and reasoning
• A multiparametric view on answer set programming
• Default logic and bounded treewidth
• Exploiting Database Management Systems and Treewidth for Counting
• Strong backdoors for default logic
• Strong backdoors for default logic

This page was built for publication: Default logic and bounded treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5915667)