| Revue: | Computación y sistemas |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000368975 |
| ISSN: | 1405-5546 |
| Autores: | Guillén, Carlos1 Lemuz, Rafael1 Ayaquica, Irene1 |
| Instituciones: | 1Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación, Puebla. México |
| Año: | 2013 |
| Periodo: | Oct-Dic |
| Volumen: | 17 |
| Número: | 4 |
| Paginación: | 501-514 |
| País: | México |
| Idioma: | Español |
| Tipo de documento: | Artículo |
| Enfoque: | Aplicado, descriptivo |
| Resumen en español | El problema de conteo de modelos en formulas Booleanas es un problema #P-completo, es decir, no se conocen algoritmos deterministas en el modelo clásico de computabilidad (máquinas de Turing) que realice este conteo con complejidad en tiempo polinomial. La dificultad persiste aún imponiendo condiciones mas restrictivas sobre las clases sintácticas de fórmulas Booleanas. En este artículo presentamos una familia tratable dentro de la clase sintáctica 2μ-3MON. La identificación de esta familia se hace a travos del hipergrafo asociado a estructuras simples como cadenas y ciclos. Se identifican también operadores matriciales que actúan sobre estas estructuras; estos operadores conducen a algoritmos eficientes que efectúan el conteo de modelos sobre la familia identificada en tiempo lineal con respecto al número de clausulas de la fórmula instanciada, a diferencia de los métodos basados en invariantes hipergráficos (como el ancho de árbol) que realizan este conteo en tiempo cúbico |
| Resumen en inglés | 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 classes 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 |
| Disciplinas: | Ciencias de la computación, Matemáticas |
| Palabras clave: | Procesamiento de datos, Matemáticas puras, Clase sintáctica, Conteo de modelos, Hipergrafos, Algoritmos |
| Keyword: | Computer science, Mathematics, Data processing, Pure mathematics, Syntactic class, Model counting, Hypergraphs, Algorithms |
| Texte intégral: | Texto completo (Ver HTML) |
