Back to Search
Start Over
A method for counting models on grid Boolean formulas1.
- Source :
- Journal of Intelligent & Fuzzy Systems; 2022, Vol. 42 Issue 5, p4719-4726, 8p
- Publication Year :
- 2022
-
Abstract
- We present a novel algorithm based on combinatorial operations on lists for computing the number of models on two conjunctive normal form Boolean formulas whose restricted graph is represented by a grid graph G<subscript>m,n</subscript>. We show that our algorithm is correct and its time complexity is O (t · 1. 618 t + 2 + t · 1. 618 2 t + 4) , where t = n · m is the total number of vertices in the graph. For this class of formulas, we show that our proposal improves the asymptotic behavior of the time-complexity with respect of the current leader algorithm for counting models on two conjunctive form formulas of this kind. [ABSTRACT FROM AUTHOR]
- Subjects :
- COUNTING
BOOLEAN functions
COMPLEXITY (Philosophy)
Subjects
Details
- Language :
- English
- ISSN :
- 10641246
- Volume :
- 42
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- Journal of Intelligent & Fuzzy Systems
- Publication Type :
- Academic Journal
- Accession number :
- 156139452
- Full Text :
- https://doi.org/10.3233/JIFS-219259