BriefGPT.xyz
May, 2023
利用树宽及其限制条件解决投影模型计数问题
Solving Projected Model Counting by Utilizing Treewidth and its Limits
HTML
PDF
Johannes K. Fichte, Markus Hecher, Michael Morak, Patrick Thier, Stefan Woltran
TL;DR
本文介绍了一种新算法来解决投影模型计数(PMC)问题,该算法利用输入实例的原始图的小树宽,并在同时考虑了指标化的树宽有理论下限的情况下,提供固定参数可解,通过使用嵌套动态规划,并在数据库技术的帮助下,可以解决树宽上限超过200的实例的PMC问题和热门的PMC特殊情况#Sat。
Abstract
In this paper, we introduce a novel algorithm to solve
projected model counting
(PMC). PMC asks to count solutions of a
boolean formula
with respect to a given set of projection variables, where multiple solution
→