Logic Journal of the IGPL 28 (6):1130-1140 (2020)

Jose A. Hernandez
Barry University
Counting models for a two conjunctive formula $F$, a problem known as $\sharp $2Sat, is a classic $\sharp $P complete problem. Given a 2-CF $F$ as input, its constraint graph $G$ is built. If $G$ is acyclic, then $\sharp $2Sat can be computed efficiently. In this paper, we address the case when $G$ has cycles. When $G$ is cyclic, we propose a decomposition on the constraint graph $G$ that allows the computation of $\sharp $2Sat in incremental way. Let $T$ be a cactus graph of $G$ containing a maximal number of independent cycles, and let $\overline{T}=-E)$ be a subset of frond edges from $G$. The clauses in $\overline{T}$ are ordered in connected components $\{K_1, \ldots, K_r\}$. Each $, i=1,\ldots,r$ is a knot of the graph. The arrangement of the clauses of $\overline{T}$ allows the decomposition of $G$ in knots and provides a way of computing $\sharp $2Sat in an incremental way. Our procedure has a bottom-up orientation for the computation of $\sharp $2Sat. It begins with $F_0 = T$. In each iteration of the procedure, a new clause $C_i \in \overline{T}$ is considered in order to form $F_i = $ and then to compute $\sharp $2Sat$$ based on the computation of $\sharp $2Sat$$.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1093/jigpal/jzaa009
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,319
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On the Hardness of Approximate Reasoning.Dan Roth - 1996 - Artificial Intelligence 82 (1-2):273-302.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Algebraic Functions.M. Campercholi & D. Vaggione - 2011 - Studia Logica 98 (1-2):285-306.
Satisfiability Decay Along Conjunctions of Pseudo-Random Clauses.Eli Shamir - 2006 - Logic Journal of the IGPL 14 (5):815-825.
Invisible Genericity and 0$^{Sharp}$.M. C. Stanley - 1998 - Journal of Symbolic Logic 63 (4):1297-1318.
Remembering Gene Sharp.Barry Gan - 2017 - The Acorn 17 (2):95-97.
Determinacy and the Sharp Function on the Reals.Derrick Albert DuBose - 1991 - Annals of Pure and Applied Logic 54 (1):59-85.
Twilight Graphs.J. C. E. Dekker - 1981 - Journal of Symbolic Logic 46 (3):539-571.
Engels on Video.Mac Sharp, Mac Daly & Ellis Sharp - 1996 - Journal of Nietzsche Studies 11:72-73.
Determinacy and the Sharp Function on Objects of Type K.Derrick Albert Dubose - 1995 - Journal of Symbolic Logic 60 (4):1025-1053.
Representation Operators and Computation.Brendan Kitts - 1999 - Minds and Machines 9 (2):223-240.
Aspects of a Graph-Based Proof Procedure for Horn Clauses.Stan T. Raatz - 1987 - Dissertation, University of Pennsylvania
An Algorithm for the Decomposition of Finite Languages.W. Wieczorek - 2010 - Logic Journal of the IGPL 18 (3):355-366.


Added to PP index

Total views
3 ( #1,321,991 of 2,448,752 )

Recent downloads (6 months)
1 ( #447,034 of 2,448,752 )

How can I increase my downloads?


My notes