{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T07:10:18Z","timestamp":1777705818978,"version":"3.51.4"},"reference-count":16,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2021,12,24]],"date-time":"2021-12-24T00:00:00Z","timestamp":1640304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Intelligent & Fuzzy Systems"],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"\n 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\n G<\/jats:italic>\n \n m<\/jats:italic>\n ,\n n<\/jats:italic>\n <\/jats:sub>\n . We show that our algorithm is correct and its time complexity is\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n t<\/mml:mi>\n <\/mml:msqrt>\n \u00b7<\/mml:mo>\n 1<\/mml:mn>\n .<\/mml:mo>\n \n 618<\/mml:mn>\n \n \n t<\/mml:mi>\n <\/mml:msqrt>\n +<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n +<\/mml:mo>\n t<\/mml:mi>\n \u00b7<\/mml:mo>\n 1<\/mml:mn>\n .<\/mml:mo>\n \n 618<\/mml:mn>\n \n 2<\/mml:mn>\n \n t<\/mml:mi>\n <\/mml:msqrt>\n +<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:math>\n <\/jats:inline-formula>\n , where\n t<\/jats:italic>\n \u00a0=\u00a0\n n<\/jats:italic>\n \u00a0\u00b7\u00a0\n m<\/jats:italic>\n is the total number of vertices in the graph.\n <\/jats:p>\n 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.<\/jats:p>","DOI":"10.3233\/jifs-219259","type":"journal-article","created":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T11:31:03Z","timestamp":1641295863000},"page":"4719-4726","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["A method for counting models on grid Boolean formulas"],"prefix":"10.1177","volume":"42","author":[{"given":"Marco A.","family":"L\u00f3pez-Medina","sequence":"first","affiliation":[{"name":"Facultad de Ingenier\u00eda, UAEMex and Facultad de Ciencias de la Computaci\u00f3n, BUAP"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Raymundo","family":"Marcial-Romero","sequence":"additional","affiliation":[{"name":"Facultad de Ingenier\u00eda, UAEMex and Facultad de Ciencias de la Computaci\u00f3n, BUAP"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillermo","family":"De Ita Luna","sequence":"additional","affiliation":[{"name":"Facultad de Ingenier\u00eda, UAEMex and Facultad de Ciencias de la Computaci\u00f3n, BUAP"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 A.","family":"Hern\u00e1ndez","sequence":"additional","affiliation":[{"name":"Facultad de Ingenier\u00eda, UAEMex and Facultad de Ciencias de la Computaci\u00f3n, BUAP"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2021,12,24]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF00383444","article-title":"Counting linear extensions","volume":"8","author":"Winkler P.","year":"1991","unstructured":"WinklerP. and BrifhtwellG., Counting linear extensions, Order8(e) (1991), 225\u2013242.","journal-title":"Order"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)00092-1"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.3166\/jancl.11.11-34"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322328"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-27060-9_16"},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","unstructured":"SzeiderS. On Fixed-Parameter Tractable Parametrizations of SAT Springer Berlin Heidelberg (2004) pp. 188\u2013202.","DOI":"10.1007\/978-3-540-24605-3_15"},{"key":"e_1_3_1_8_2","unstructured":"L\u00f3pez-MedinaM.A. Marcial-RomeroJ.R. De Ita LunaG. Montes-VenegasH.A. and AlejoR. A linear time algorithm for solving #2SAT on cactus formulas CoRR ams\/1702.08581 2017."},{"issue":"2018","key":"e_1_3_1_9_2","first-page":"72","article-title":"A Linear Time Algorithm for Computing #2SAT for Outerplanar 2-CNFFormulas","volume":"10880","author":"L\u00f3pez-Medina M.A.","unstructured":"L\u00f3pez-MedinaM.A., Marcial-RomeroJ.R., De ItaG. and MoyaoY., A Linear Time Algorithm for Computing #2SAT for Outerplanar 2-CNFFormulas, Lecture Notes in Computer Science10880(2018), 72\u201381.","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_3_1_10_2","doi-asserted-by":"crossref","unstructured":"Wahlstr\u00f6mM. A tighter bound for counting maxweight solutions to 2sat instances Springer Berlin Heidelberg (2008) pp. 202\u2013213.","DOI":"10.1007\/978-3-540-79723-4_19"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019528993X"},{"key":"e_1_3_1_12_2","first-page":"05","article-title":"The fibonacci number of a grid graph and a new class of integer sequences","volume":"8","author":"Euler R.","year":"2005","unstructured":"EulerR., The fibonacci number of a grid graph and a new class of integer sequences, Journal of Integer Sequences8 (2005), 05.","journal-title":"Journal of Integer Sequences"},{"key":"e_1_3_1_13_2","unstructured":"GolinM. Cho LeungY. WangY. and YongX. Counting structures in grid graphs cylinders and tori using transfer matrices: Survey and new results. In ALENEX\/ANALCO (2005) pp. 250\u2013258 01."},{"key":"e_1_3_1_14_2","unstructured":"GuillenC. Lopez LopezA. and De ItaG. Computing #2-sat of grids grid-cylinders and grid-tori boolean formulas. In Proceedings of the 15th RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion 451. CEUR-WS.org 2008."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01608783"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.915673"},{"key":"e_1_3_1_17_2","doi-asserted-by":"crossref","unstructured":"L\u00f3pez-MedinaM.A. Marcial-RomeroJ.R. De ItaG. and ValdovinosR.M. A fast and efficient method for #2sat via graph transformations Advances in Soft Computing (2017) pp. 95\u2013106.","DOI":"10.1007\/978-3-030-02837-4_8"}],"container-title":["Journal of Intelligent & Fuzzy Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JIFS-219259","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/JIFS-219259","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/JIFS-219259","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:45:19Z","timestamp":1777455919000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/JIFS-219259"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,24]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.3233\/JIFS-219259"],"URL":"https:\/\/doi.org\/10.3233\/jifs-219259","relation":{},"ISSN":["1064-1246","1875-8967"],"issn-type":[{"value":"1064-1246","type":"print"},{"value":"1875-8967","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,24]]}}}