Default logic and bounded treewidth

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 ( Cons ). Our algorithm can even be used to enumerate all generating defaults ( EnumSD ) that lead to stable extensions. We show that our algorithm decides Cons in linear time in the input theory and triple exponential time in the treewidth Further, our algorithm solves EnumSD 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. Finally, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for Cons.

Authors

• Johannes K. Fichte
• Markus Hecher
• Irina Schindler

Keywords

• Parameterized algorithms
• Tree decompositions
• Dynamic programming
• Reiter's default logic
• Propositional logic
• Lower bounds