{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T01:27:25Z","timestamp":1772242045062,"version":"3.50.1"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2018,11,1]],"date-time":"2018-11-01T00:00:00Z","timestamp":1541030400000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2018,11,1]],"date-time":"2018-11-01T00:00:00Z","timestamp":1541030400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2018,11,1]],"date-time":"2018-11-01T00:00:00Z","timestamp":1541030400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation","award":["1228765"],"award-info":[{"award-number":["1228765"]}]},{"name":"National Science Foundation","award":["1228768"],"award-info":[{"award-number":["1228768"]}]},{"name":"National Science Foundation","award":["1320583"],"award-info":[{"award-number":["1320583"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>We consider the problem of deciding the satisfiability of quantifier-free formulas in the theory of finite sets with cardinality constraints. Sets are a common high-level data structure used in programming; thus, such a theory is useful for modeling program constructs directly. More importantly, sets are a basic construct of mathematics and thus natural to use when formalizing the properties of computational systems. We develop a calculus describing a modular combination of a procedure for reasoning about membership constraints with a procedure for reasoning about cardinality constraints. Cardinality reasoning involves tracking how different sets overlap. For efficiency, we avoid considering Venn regions directly, as done in previous work. Instead, we develop a novel technique wherein potentially overlapping regions are considered incrementally as needed, using a graph to track the interaction among the different regions. The calculus has been designed to facilitate its implementation within SMT solvers based on the DPLL($T$) architecture. Our experimental results demonstrate that the new techniques are competitive with previous techniques and can scale much better on certain classes of problems.<\/jats:p>","DOI":"10.23638\/lmcs-14(4:12)2018","type":"journal-article","created":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T13:30:36Z","timestamp":1743687036000},"source":"Crossref","is-referenced-by-count":3,"title":["Reasoning with Finite Sets and Cardinality Constraints in SMT"],"prefix":"10.23638","volume":"Volume 14, Issue 4","author":[{"given":"Kshitij","family":"Bansal","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9522-3084","authenticated-orcid":false,"given":"Clark","family":"Barrett","sequence":"additional","affiliation":[]},{"given":"Andrew","family":"Reynolds","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6726-775X","authenticated-orcid":false,"given":"Cesare","family":"Tinelli","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2018,11,1]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/1702.06259v3","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/1702.06259v3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,3]],"date-time":"2025-04-03T13:30:37Z","timestamp":1743687037000},"score":1,"resource":{"primary":{"URL":"http:\/\/lmcs.episciences.org\/3155"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,1]]},"references-count":0,"URL":"https:\/\/doi.org\/10.23638\/lmcs-14(4:12)2018","relation":{"has-preprint":[{"id-type":"arxiv","id":"1702.06259v2","asserted-by":"subject"},{"id-type":"arxiv","id":"1702.06259v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1702.06259","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1702.06259","asserted-by":"subject"}],"is-cited-by":[{"id-type":"doi","id":"10.4204\/EPTCS.346.13","asserted-by":"object"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,1]]},"article-number":"3155"}}