{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:13:04Z","timestamp":1763467984043,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,4,1]],"date-time":"2010-04-01T00:00:00Z","timestamp":1270080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0502793"],"award-info":[{"award-number":["CCF-0502793"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,4]]},"abstract":"<jats:p>\n            Set constraints form a constraint system where variables range over the domain of sets of trees. They give a natural formalism for many problems in program analysis. Syntactically, set constraints are conjunctions of inclusions between expressions built over variables, constructors (constants and function symbols from a given signature) and a choice of set operators that defines the specific class of set constraints. In this article, we are interested in the class of\n            <jats:italic>set constraints with projections<\/jats:italic>\n            , which is the class with all Boolean operators (union, intersection and complement) and\n            <jats:italic>projections<\/jats:italic>\n            that in program analysis directly correspond to type destructors. We prove that the problem of existence of a solution of a system of set constraints with projections is in NEXPTIME, and thus that it is NEXPTIME-complete.\n          <\/jats:p>","DOI":"10.1145\/1734213.1734217","type":"journal-article","created":{"date-parts":[[2010,5,4]],"date-time":"2010-05-04T14:14:06Z","timestamp":1272982446000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Set constraints with projections"],"prefix":"10.1145","volume":"57","author":[{"given":"Witold Charatonik Leszek","family":"Pacholski","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Wroc\u0142aw, Poland"}]}],"member":"320","published-online":{"date-parts":[[2010,5,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Ackermann W. 1954. Solvable Cases of the Decision Problem. North-Holland Amsterdam The Netherlands.  Ackermann W. 1954. Solvable Cases of the Decision Problem. North-Holland Amsterdam The Netherlands."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6423(99)00007-6"},{"volume":"832","volume-title":"Proceedings of the Symposium on Computer Science Logic'93","author":"Aiken A.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1139"},{"volume-title":"Proceedings of the 7th Seventh Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Aiken A.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the 8th Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Bachmair L.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2692"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00152-5"},{"volume-title":"Proceedings of the 9th Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Charatonik W.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365727"},{"volume":"1118","volume-title":"Proceedings of the Conference on Principles and Practice of Constraint Programming. Lecture Notes in Computer Science","author":"Charatonik W.","key":"e_1_2_1_12_1"},{"volume":"1379","volume-title":"Proceedings of the 9th International Conference on Rewriting Techniques and Applications. Lecture Notes in Computer Science","author":"Charatonik W.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.2952"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/325694.325730"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/647201.718734"},{"volume":"1099","volume-title":"Languages and Programming. Lecture Notes in Computer Science","author":"Cheng A.","key":"e_1_2_1_17_1"},{"volume":"665","volume-title":"Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science","author":"Gilleron R.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366850"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2747"},{"volume-title":"Proceedings of the 16th Annual Conference of the European Association for Computer Science Logic","series-title":"Lecture Notes in Computer Science","author":"Goubault-Larrecq J.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","unstructured":"Heintze N. 1992. Set based program analysis. Ph.D. dissertation School of Computer Science Carnegie Mellon Univ. Pittsburgh PA.   Heintze N. 1992. Set based program analysis. Ph.D. dissertation School of Computer Science Carnegie Mellon Univ. Pittsburgh PA."},{"volume-title":"Proceedings of the 5th Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Heintze N.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/96709.96729"},{"volume":"874","volume-title":"Proceedings of the Workshop on Principles and Practice of Constraint Programming. Lecture Notes in Computer Science","author":"Heintze N.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11547662_16"},{"volume-title":"Proceedings of the 1993 Conference on Computer Science Logic","series-title":"Lecture Notes in Computer Science","author":"Kozen D.","key":"e_1_2_1_28_1"},{"volume-title":"Proceedingss of the 1st International Conference Constraints in Computational Logics","series-title":"Lecture Notes in Computer Science","author":"Kozen D.","key":"e_1_2_1_29_1"},{"volume-title":"TAPSOFT: Proceedings of the 6th International Joint Conference on Theory and Practice of Software Development","series-title":"Lecture Notes in Computer Science","author":"Kozen D.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2694"},{"volume-title":"Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"McAllester D. A.","key":"e_1_2_1_32_1"},{"volume":"1330","volume-title":"Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming (CP97)","author":"M\u00fcller M.","key":"e_1_2_1_33_1"},{"volume-title":"14th Annual IEEE Symposium on Logic in Computer Science (LICS). IEEE Computer Society Press","author":"M\u00fcller M.","key":"e_1_2_1_34_1"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90043-0"},{"key":"e_1_2_1_36_1","first-page":"456","article-title":"Automatic computation of data set definitions","volume":"68","author":"Reynolds J. C.","year":"1969","journal-title":"Information Processing"},{"volume":"3210","volume-title":"Computer Science Logic. Lecture Notes in Computer Science","author":"Rychlikowski P.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00032-3"},{"volume":"1214","volume-title":"Proceedings of the 9th International Joint Conference on Theory and Practice of Software Development. Lecture Notes in Computer Science","author":"Seynhaeve F.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1994.316077"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00030-2"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009826603139"},{"volume-title":"Proceedings of the 11th International Conference on Automated Deduction","series-title":"Lecture Notes in Artificial Intelligence","author":"Uribe T. E.","key":"e_1_2_1_43_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1734213.1734217","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1734213.1734217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:28Z","timestamp":1750250728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1734213.1734217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,4]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,4]]}},"alternative-id":["10.1145\/1734213.1734217"],"URL":"https:\/\/doi.org\/10.1145\/1734213.1734217","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2010,4]]},"assertion":[{"value":"2006-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}