A Tractable Class of Model Counting Problems

Denis Deratani MauáFabio Gagliardi Cozman

We develop a polynomial-time algorithm for model counting of formulas in monotone conjunctive normal form where the clauses can be partitioned in two sets: any two clauses in different sets share exactly one variable; any twoclauses in the same set have the same number of variables and share no variables. Our algorithm reduces the problem to edge cover counting problems that can be solved by dynamic programming efficiently. We also comment on extensions and applications of these results, such as solving weighted modelcounting with uniform weights and computing the number of satisfying interpretations of DL-Lite sentences.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: