{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,14]],"date-time":"2025-07-14T02:38:54Z","timestamp":1752460734337},"publisher-location":"Berlin\/Heidelberg","reference-count":20,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540582770"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0049320","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T18:58:16Z","timestamp":1141671496000},"page":"1-17","source":"Crossref","is-referenced-by-count":23,"title":["The complexity of set constraints"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Aiken","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dexter","family":"Kozen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Vardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ed","family":"Wimmers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","unstructured":"A. Aiken, D. Kozen, M. Vardi, and E. Wimmers, The complexity of set constraints. Technical Report 93-1352, Computer Science Department, Cornell University, May 1993."},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"A. Aiken, D. Kozen, and E. Wimmers. Decidability of systems of set constraints with negative constraints. Technical Report 93-1362, Computer Science Department, Cornell University, June 1993.","DOI":"10.7146\/brics.v1i32.21611"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"A. Aiken and B. Murphy. Implementing regular tree expressions. In Proc. 1991 Conf. Functional Programming Languages and Computer Architecture, pages 427\u2013447, August 1991.","DOI":"10.1007\/3540543961_21"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"A. Aiken and B. Murphy. Static type inference in a dynamically typed language. In Proc. 18th Symp. Principles of Programming Languages, pages 279\u2013290. ACM, January 1991.","DOI":"10.1145\/99583.99621"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"A. Aiken and E. Wimmers. Solving systems of set constraints. In Proc. 7th Symp. Logic in Computer Science, pages 329\u2013340. IEEE, June 1992.","DOI":"10.1109\/LICS.1992.185545"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"L. Bachmair, H. Ganzinger, and U. Waldmann. Set constraints are the monadic class. In Proc. 8th Symp. Logic in Computer Science, pages 75\u201383. IEEE, June 1993.","DOI":"10.1109\/LICS.1993.287598"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0304-3975(80)90069-9","volume":"10","author":"J. A. Brzozowski","year":"1980","unstructured":"J. A. Brzozowski and E. Leiss. On equations for regular languages, finite automata, and sequential networks. Theor. Comput. Sci., 10:19\u201335, 1980.","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1_CR8","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. Chandra","year":"1981","unstructured":"A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. J. Assoc. Comput. Mach., 28(1):114\u2013133, 1981.","journal-title":"J. Assoc. Comput. Mach."},{"key":"1_CR9","unstructured":"W. Charatonik and L. Pacholski. Negative set constraints with equality. In Proc. 9th Symp. Logic in Computer Science. IEEE, July 1994. To appear. Also, Max-Planck-Institut f\u00fcr Informatik Technical Report MPI-I-93-265."},{"key":"1_CR10","first-page":"505","volume":"665","author":"R. Gilleron","year":"1993","unstructured":"R. Gilleron, S. Tison, and M. Tommasi. Solving systems of set constraints using tree automata. In Proc. Symp. Theor. Aspects of Comput. Sci., volume 665, pages 505\u2013514. Springer-Verlag Lect. Notes in Comput. Sci., February 1993.","journal-title":"Proc. Symp. Theor. Aspects of Comput. Sci."},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"R. Gilleron, S. Tison, and M. Tommasi. Solving systems of set constraints with negated subset relationships. In Proc. 34th Symp. Foundations of Comput. Sci., pages 372\u2013380. IEEE, November 1993.","DOI":"10.1109\/SFCS.1993.366850"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"N. Heintze and J. Jaffar. A decision procedure for a class of set constraints. In Proc. 5th Symp. Logic in Computer Science, pages 42\u201351. IEEE, June 1990.","DOI":"10.1109\/LICS.1990.113732"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"N. Heintze and J. Jaffar. A finite presentation theorem for approximating logic programs. In Proc. 17th Symp. Principles of Programming Languages, pages 197\u2013209. ACM, January 1990.","DOI":"10.1145\/96709.96729"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"N. D. Jones and S. S. Muchnick. Flow analysis and optimization of LISP-like structures. In Proc. 6th Symp. Principles of Programming Languages, pages 244\u2013256. ACM, January 1979.","DOI":"10.1145\/567752.567776"},{"key":"1_CR15","unstructured":"K. Marriott and M. Odersky. Systems of negative boolean constraints. Technical Report YALEU\/DCS\/RR-900, Computer Science Department, Yale University, April 1992."},{"key":"1_CR16","unstructured":"P. Mishra. Towards a theory of types in PROLOG. In Proc. 1st Symp. Logic Programming, pages 289\u2013298. IEEE, 1984."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"P. Mishra and U. Reddy. Declaration-free type checking. In Proc. 12th Symp. Principles of Programming Languages, pages 7\u201321. ACM, 1985.","DOI":"10.1145\/318593.318603"},{"key":"1_CR18","unstructured":"J. C. Reynolds. Automatic computation of data set definitions. In Information Processing 68, pages 456\u2013461. North-Holland, 1969."},{"key":"1_CR19","unstructured":"K. Stefansson. Systems of set constraints with negative constraints are NEXPTIME-complete. In Proc. 9th Symp. Logic in Computer Science. IEEE, June 1994. To appear. Also Cornell University TR93-1380, August 1993."},{"key":"1_CR20","unstructured":"J. Young and P. O'Keefe. Experience with a type evaluator. In D. Bj\u00f8rner, A. P. Ershov, and N. D. Jones, editors, Partial Evaluation and Mixed Computation, pages 573\u2013581. North-Holland, 1988."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049320.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:55:37Z","timestamp":1607550937000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540582770"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0049320","relation":{},"subject":[]}}