Model Counting in the 2mu-3MON Syntactic Class

Authors

  • Carlos Guillén Galván Benemérita Universidad Autónoma de Puebla.
  • Rafael Lemuz López Benemérita Universidad Autónoma de Puebla.
  • Irene Olaya Ayaquica Martínez Benemérita Universidad Autónoma de Puebla.

DOI:

https://doi.org/10.13053/cys-17-4-1363

Keywords:

#SAT, 2mu-3MON, syntactic class, hypergraph.

Abstract

The counting model problem in Boolean formulas is #P-complete, i.e., there is no known deterministic algorithm in the classical computability model (Turing machine) that makes this count in polynomial time. The difficulty persists even imposing more restrictive conditions on the syntactic clases of Boolean formulas. In this paper we present a treatable family within the syntactical class 2_-3MON. The identification of this family is done by using the hypergraph associated with simple structures such as chains and cycles. Then, matrix operators acting over these structures are identified; these operators lead to efficient algorithms that perform the model counting on the identified family in linear time for the number of clauses in the instantiated formula; unlike hypergraphic invariant based methods (such as tree width), which perform the count in cubic time.

Author Biographies

Carlos Guillén Galván, Benemérita Universidad Autónoma de Puebla.

Doctor en CienciasComputacionales por el InstitutoNacional de Astrofísica, Ópticay Electrónica (INAOE) y el gradode Maestría en Matemáticaspor la Facultad de FísicoMatemáticas de la BUAP. Esprofesor de tiempo completo en la Facultad deCiencias de la Computación de la BeneméritaUniversidad Autónoma de Puebla desde 1995.Sus intereses de investigación son en teoría de lacomputación y procesamiento de imágenes.

Rafael Lemuz López, Benemérita Universidad Autónoma de Puebla.

Obtuvo el título de Licenciado en Ciencias de la Computación por la Benemérita Universidad Autónoma de Puebla en 2002. Obtuvo el grado de Maestro  y Doctor en Ciencias de la Computación por el Instituto Nacional de  Astrofísica, Óptica y Electrónica en 2003 y 2008 respectivamente. Desde el 2008 es profesor-investigador en la Benemérita Universidad Autónoma de Puebla.

Irene Olaya Ayaquica Martínez, Benemérita Universidad Autónoma de Puebla.

Obtuvo el grado de Doctor en Ciencias Computacionales por el Instituto Nacional de  Astrofísica, Óptica y Electrónica (INAOE); el grado de Maestro en Ciencias de la Computación por el Centro de Investigación en Computación del IPN (CIC-IPN) y el título de Licenciado en Ciencias de la Computación por la Facultad de Ciencias de la Computación de la Benemérita Universidad Autónoma de Puebla (FCC-BUAP). Es profesor de tiempo completo en la Facultad de Computación de la Benemérita Universidad Autónoma de Puebla desde 2009. Sus principales líneas de investigación son: reconocimiento de patrones y agrupamiento conceptual difuso.

Downloads

Published

2013-12-30

Issue

Vol. 17 No. 4 (2013): 17(4) October-December 2013

Section

Articles

License 

Hereby I transfer exclusively to the Journal "Computación y 
Sistemas", published by the Computing Research Center (CIC-IPN),
the Copyright of the aforementioned paper. I also accept that these 
rights will not be transferred to any other publication, in any other 
format, language or other existing means of developing.
I certify that the paper has not been previously disclosed or simultaneo
usly submitted to any other publication, and that it does not contain 
material whose publication would violate the Copyright or other 
proprietary rights of any person, company or institution. I certify that 
I have the permission from the institution or company where I work or 
study to publish this work.
The representative author accepts the responsibility for the publication
of this paper on behalf of each and every one of the authors. 
This transfer is subject to the following conditions:
  • The authors retain all ownership rights (such as patent rights) of this work, except for the publishing rights transferred to the CIC, through this document.
  • Authors retain the right to publish the work in whole or in part in any book they are the authors or publishers. They can also make use of this work in conferences, courses, personal web pages, and so on.
  • Authors may include working as part of his thesis, for non-profit distribution only.