{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:58:29Z","timestamp":1740142709609,"version":"3.37.3"},"reference-count":26,"publisher":"Informa UK Limited","license":[{"start":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T00:00:00Z","timestamp":1248048000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0827397","FA9550-06-0050"],"award-info":[{"award-number":["CCF-0827397","FA9550-06-0050"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["CCF-0827397","FA9550-06-0050"],"award-info":[{"award-number":["CCF-0827397","FA9550-06-0050"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Applied Mathematics and Decision Sciences"],"published-print":{"date-parts":[[2009,7,20]]},"abstract":"<jats:p>This paper is concerned with the computational complexities of three types of queries, namely, satisfiability,\nequivalence, and hull inclusion. The first two queries are analyzed over the domain of CNF formulas, while\nhull inclusion queries are analyzed over continuous and discrete sets defined by rational polyhedra. Although\nCNF formulas can be represented by polyhedra over discrete sets, we analyze them separately on account\nof their distinct structure. In particular, we consider the NAESAT and XSAT versions of satisfiability over\nHornCNF, 2CNF, and Horn<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mo>\u2295<\/mml:mo><\/mml:math>2CNF formulas. These restricted families find applications in a number of\npractical domains. From the hull inclusion perspective, we are primarily concerned with the question of\nchecking whether two succinct descriptions of a set of points are equivalent. In particular, we analyze the\ncomplexities of integer hull inclusion over 2SAT and Horn polyhedra. Hull inclusion problems are important\nfrom the perspective of deriving minimal descriptions of point sets. One of the surprising consequences of\nour work is the stark difference in complexities between equivalence problems in the clausal and polyhedral\ndomains for the same polyhedral structure.<\/jats:p>","DOI":"10.1155\/2009\/845804","type":"journal-article","created":{"date-parts":[[2009,7,20]],"date-time":"2009-07-20T14:59:56Z","timestamp":1248101996000},"page":"1-18","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexities of Selected Satisfiability and Equivalence Queries over Boolean Formulas and Inclusion Queries over Hulls"],"prefix":"10.1080","volume":"2009","author":[{"given":"K.","family":"Subramani","sequence":"first","affiliation":[{"name":"LDCSEE, West Virginia University, Morgantown, WV 26506, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"301","reference":[{"volume":"32","journal-title":"Algorithmica","year":"2002","key":"33"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00017-6"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"year":"1994","key":"23","first-page":"xvi+523"},{"year":"1979","key":"12","first-page":"x+338"},{"issue":"1-2","key":"36","doi-asserted-by":"crossref","first-page":"67","DOI":"10.3233\/SAT190030","volume":"3","year":"2007","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"first-page":"xvi+763","year":"1988","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","key":"22"},{"year":"1992","key":"7"},{"year":"1993","key":"2","first-page":"xvi+846"},{"year":"1995","key":"24"},{"year":"1987","key":"31"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011276507260"},{"key":"19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48168-0_9"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90010-8"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792231179"},{"year":"1998","key":"4","first-page":"xii+342"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90091-9"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.08.011"},{"volume":"28","year":"1970","series-title":"Princeton Mathematics Series","key":"29"},{"year":"1993","key":"15"},{"issue":"1","key":"11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","year":"1991","journal-title":"Journal of the Association for Computing Machinery"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1137\/0217060"},{"first-page":"xvi+365","year":"1999","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","key":"6"},{"issue":"2","key":"26","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1145\/62.322436","volume":"31","year":"1984","journal-title":"Journal of the Association for Computing Machinery"},{"year":"2006","key":"34"},{"key":"38","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310099"}],"container-title":["Journal of Applied Mathematics and Decision Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/2009\/845804.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/archive\/2009\/845804.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/archive\/2009\/845804.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,8]],"date-time":"2024-08-08T14:23:45Z","timestamp":1723127025000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.hindawi.com\/journals\/ads\/2009\/845804\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,20]]},"references-count":26,"alternative-id":["845804","845804"],"URL":"https:\/\/doi.org\/10.1155\/2009\/845804","relation":{},"ISSN":["1173-9126","1532-7612"],"issn-type":[{"type":"print","value":"1173-9126"},{"type":"electronic","value":"1532-7612"}],"subject":[],"published":{"date-parts":[[2009,7,20]]}}}