{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T21:01:17Z","timestamp":1750453277081},"reference-count":61,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2002,4,1]],"date-time":"2002-04-01T00:00:00Z","timestamp":1017619200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4125,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2002,4]]},"DOI":"10.1016\/s0304-3975(00)00312-1","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:21:34Z","timestamp":1027653694000},"page":"3-46","source":"Crossref","is-referenced-by-count":15,"title":["Set-sharing is redundant for pair-sharing"],"prefix":"10.1016","volume":"277","author":[{"given":"Roberto","family":"Bagnara","sequence":"first","affiliation":[]},{"given":"Patricia M.","family":"Hill","sequence":"additional","affiliation":[]},{"given":"Enea","family":"Zaffanella","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/S0304-3975(00)00312-1_BIB1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0167-6423(96)00039-1","article-title":"Two classes of Boolean functions for dependency analysis","volume":"31","author":"Armstrong","year":"1998","journal-title":"Sci. Comput. Programming"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB2","unstructured":"R. Bagnara, Data-flow analysis for constraint logic-based languages, Ph.D. Thesis, Dipartimento di Informatica, Universit\u00e0 di Pisa, Corso Italia 40, I-56125 Pisa, Italy, March 1997. Printed as Report TD-1\/97."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB3","first-page":"53","article-title":"Set-sharing is redundant for pair-sharing","volume":"Vol. 1302","author":"Bagnara","year":"1997"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB4","first-page":"432","article-title":"Abstracting S-semantics using a model-theoretic approach","volume":"Vol. 844","author":"Boulanger","year":"1994"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB5","doi-asserted-by":"crossref","unstructured":"M. Bruynooghe, M. Codish, Freeness, sharing, linearity and correctness \u2014 All at once, in: P. Cousot, M. Falaschi, G. Fil\u00e9, A. Rauzy (Eds.), Static Analysis, Proc. 3rd Internat. Workshop, Padova, Italy, Lecture Notes in Computer Science, Vol. 724, Springer, Berlin, 1993, pp. 153\u2013164. An extended version is available as Technical Report CW 179, Department of Computer Science, K.U. Leuven, September 1993.","DOI":"10.1007\/3-540-57264-3_37"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB6","unstructured":"M. Bruynooghe, M. Codish, A. Mulkers, Abstract unification for a composite domain deriving sharing and freeness properties of program variables, in: F.S. de Boer, M. Gabbrielli (Eds.), Verification and Analysis of Logic Languages, Proc. W2 Post-Conf. Workshop, Internat. Conf. on Logic Programming, Santa Margherita Ligure, Italy, 1994, pp. 213\u2013230."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB7","unstructured":"M. Bruynooghe, M. Codish, A. Mulkers, A composite domain for freeness, sharing, and compoundness analysis of logic programs, Tech. Rep. CW 196, Department of Computer Science, K.U. Leuven, Belgium, July 1994."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB8","first-page":"128","article-title":"A freeness and sharing analysis of logic programs based on a pre-interpretation","volume":"Vol. 1145","author":"Bruynooghe","year":"1996"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB9","unstructured":"J.-H. Chang, High performance execution of prolog programs based on a static data dependency analysis, Ph.D. Thesis, Computer Science Division (EECS), University of California at Berkeley 1986. Printed as Report UCB\/CSD 86\/263."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB10","unstructured":"J.-H. Chang, A.M. Despain, D. DeGroot, AND-parallelism of logic programs based on a static data dependency analysis, Digest of Papers of COMPCON Spring\u201985, IEEE Computer Society Press, Silverspring, MD, 1985, pp. 218\u2013225."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB11","unstructured":"W.V. Citrin, Parallel unification scheduling in prolog, Ph.D. Thesis, Computer Science Division (EECS), University of California at Berkeley, 1988. Printed as Report UCB\/CSD 88\/415."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB12","unstructured":"M. Codish, D. Dams, G. Fil\u00e9, M. Bruynooghe, Freeness analysis for logic programs and correctness? in: D.S. Warren (Ed.), Logic Programming: Proc. 10th Internat. Conf. on Logic Programming, Budapest, Hungary, MIT Press Series in Logic Programming, The MIT Press, Cambridge, MA, 1993, pp. 116\u2013131. An extended version is available as Technical Report CW 161, Department of Computer Science, K.U. Leuven, December 1992."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB13","series-title":"Logic Programming: Proc. 8th Internat. Conf. on Logic Programming, Paris, France, MIT Press Series in Logic Programming","first-page":"79","article-title":"Derivation and safety of an abstract unification algorithm for groundness and aliasing analysis","author":"Codish","year":"1991"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB14","first-page":"68","article-title":"An algebraic approach to sharing analysis of logic programs","volume":"Vol. 1302","author":"Codish","year":"1997"},{"issue":"1","key":"10.1016\/S0304-3975(00)00312-1_BIB15","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/200994.200998","article-title":"Improving abstract interpretations by combining domains","volume":"17","author":"Codish","year":"1995","journal-title":"ACM Trans. Programming Languages Systems"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB16","series-title":"Computations, abstractions and constraints, Proc. 4th IEEE Internat. Conf. on Computer Languages","author":"Codognet","year":"1992"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB17","series-title":"Proc. 8th Italian Conf. on Logic Programming (GULP\u201993), Gizzeria, Italy","first-page":"251","article-title":"Comparison and design of abstract domains for sharing analysis","author":"Cortesi","year":"1993"},{"issue":"1","key":"10.1016\/S0304-3975(00)00312-1_BIB18","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/239912.239914","article-title":"Complementation in abstract interpretation","volume":"19","author":"Cortesi","year":"1997","journal-title":"ACM Trans. Programming Languages Systems"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB19","doi-asserted-by":"crossref","unstructured":"A. Cortesi, G. Fil\u00e9, W. Winsborough, Prop revisited: propositional formula as abstract domain for groundness analysis, Proc. 6th Annual IEEE Symp. on Logic in Computer Science, Amsterdam, The Netherlands, IEEE Computer Society Press, Silverspring, MD, 1991, pp. 322\u2013327.","DOI":"10.1109\/LICS.1991.151656"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB20","first-page":"521","article-title":"Comparison of abstract interpretations","volume":"Vol. 623","author":"Cortesi","year":"1992"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB21","unstructured":"A. Cortesi, G. Fil\u00e9, W. Winsborough, The quotient of an abstract interpretation for comparing static analyses, in: M. Alpuente, R. Barbuti, I. Ramos (Eds.), Proc. 1994 Joint Conf. on Declarative Programming (GULP-PRODE\u201994), Pe\u00f1\u0131\u0301scola, Spain, September 1994, pp. 372\u2013397. An extended version has been published as A. Cortesi, G. Fil\u00e9, W. Winsborough, The quotient of an abstract interpretation for comparing static analyses, Theoret. Comput. Sci. 202(1&2) (1998) 163\u2013192."},{"issue":"1&2","key":"10.1016\/S0304-3975(00)00312-1_BIB22","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/S0304-3975(97)00137-0","article-title":"The quotient of an abstract interpretation for comparing static analyses","volume":"202","author":"Cortesi","year":"1998","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB23","series-title":"Conceptual and software support for abstract domain design: generic structural domain and open product, Tech. Rep. CS-93-13","author":"Cortesi","year":"1993"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB24","doi-asserted-by":"crossref","unstructured":"A. Cortesi, B. Le Charlier, P. Van Hentenryck, Combinations of abstract domains for logic programming, Conf. Record of POPL \u201994: 21st ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, Portland, Oregon, 1994, pp. 227\u2013239.","DOI":"10.1145\/174675.177880"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB25","doi-asserted-by":"crossref","unstructured":"P. Cousot, R. Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proc. 4th Annual ACM Symp. on Principles of Programming Languages, 1977, pp. 238\u2013252.","DOI":"10.1145\/512950.512973"},{"issue":"4","key":"10.1016\/S0304-3975(00)00312-1_BIB26","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1093\/logcom\/2.4.511","article-title":"Abstract interpretation frameworks","volume":"2","author":"Cousot","year":"1992","journal-title":"J. Logic and Computation"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB27","doi-asserted-by":"crossref","unstructured":"R. Cousot, D.A. Schmidt (Eds.), Static Analysis: Proc. 3rd Internat. Symp., Aachen, Germany, Lecture Notes in Computer Science, Vol. 1145, Springer, Berlin, 1996.","DOI":"10.1007\/3-540-61739-6"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB28","first-page":"159","article-title":"A comparison of three occur check analysers","volume":"Vol. 1145","author":"Crnogorac","year":"1996"},{"issue":"3","key":"10.1016\/S0304-3975(00)00312-1_BIB29","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1145\/65979.65983","article-title":"Static inference of modes and data dependencies in logic programs","volume":"11","author":"Debray","year":"1989","journal-title":"ACM Trans. Programming Languages Systems"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB30","doi-asserted-by":"crossref","unstructured":"C. Fecht, Efficient and precise sharing domains for logic programs, Tech. Rep. A\/04\/96, Universit\u00e4t des Saarlandes, Fachbereich 14 Informatik, Saarbr\u00fccken, Germany, 1996.","DOI":"10.1007\/3-540-61756-6_104"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB31","unstructured":"G. Fil\u00e9, Share\u00d7Free: simple and correct, Tech. Rep. 15, Dipartimento di Matematica, Universit\u00e0 di Padova, December 1994."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB32","series-title":"Logic Programming: Proc. Joint Internat. Conf. and Symp. on Logic Programming, Bonn, Germany, MIT Press Series in Logic Programming","first-page":"348","article-title":"Complementation of abstract domains made easy","author":"Fil\u00e9","year":"1996"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB33","unstructured":"K. Furukawa (Ed.), Logic Programming: Proc. 8th Internat. Conf. on Logic Programming, Paris, France, MIT Press Series in Logic Programming, The MIT Press, Cambridge, MA, 1991."},{"issue":"3","key":"10.1016\/S0304-3975(00)00312-1_BIB34","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0743-1066(95)00038-0","article-title":"Generalized semantics and abstract interpretation for constraint logic programs","volume":"25","author":"Giacobazzi","year":"1995","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB35","first-page":"231","article-title":"Completeness in abstract interpretation","volume":"Vol. 1349","author":"Giacobazzi","year":"1997"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB36","first-page":"366","article-title":"Complete abstract interpretations made constructive","volume":"Vol. 1450","author":"Giacobazzi","year":"1998"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB37","series-title":"A Compendium of Continuous Lattices","author":"Gierz","year":"1980"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB38","series-title":"Logic Programming: Proc. 7th Internat. Conf. on Logic Programming, Jerusalem, Israel, MIT Press Series in Logic Programming","first-page":"253","article-title":"And -Prolog and its performance","author":"Hermenegildo","year":"1990"},{"issue":"4","key":"10.1016\/S0304-3975(00)00312-1_BIB39","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/0743-1066(92)90053-6","article-title":"Global flow analysis as a practical compilation tool","volume":"13","author":"Hermenegildo","year":"1992","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB40","first-page":"99","article-title":"The correctness of set-sharing","volume":"Vol. 1503","author":"Hill","year":"1998"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB41","doi-asserted-by":"crossref","unstructured":"P.M. Hill, R. Bagnara, E. Zaffanella, The correctness of set-sharing, Tech. Rep. 98.03, School of Computer Studies, University of Leeds, 1998.","DOI":"10.1007\/3-540-49727-7_6"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB42","series-title":"Logic Programming: Proc. North American Conf., Cleveland, Ohio, USA, MIT Press Series in Logic Programming","first-page":"154","article-title":"Accurate and efficient approximation of variable aliasing in logic programs","author":"Jacobs","year":"1989"},{"issue":"2&3","key":"10.1016\/S0304-3975(00)00312-1_BIB43","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0743-1066(92)90034-Z","article-title":"Static analysis of logic programs for independent AND parallelism","volume":"13","author":"Jacobs","year":"1992","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB44","series-title":"Abstract Interpretation of Declarative Languages","first-page":"123","article-title":"A semantics-based framework for the abstract interpretation of Prolog","author":"Jones","year":"1987"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB45","first-page":"363","article-title":"A synergistic analysis for sharing and groundness which traces linearity","volume":"Vol. 788","author":"King","year":"1994"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB46","first-page":"553","article-title":"Depth-k sharing and freeness","author":"King","year":"1994"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB47","unstructured":"A. Langen, Static analysis for independent and-parallelism in logic programs, Ph.D. Thesis, Computer Science Department, University of Southern California, 1990. Printed as Report TR 91-05."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB48","unstructured":"K. Marriott, H. S\u00f8ndergaard, On describing success patterns of logic programs, Tech. Rep. 12, The University of Melbourne, 1988."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB49","series-title":"Logic Programming: Proc. of the North American Conf., Austin, Texas, USA, MIT Press Series in Logic Programming","first-page":"531","article-title":"Analysis of constraint logic programs","author":"Marriott","year":"1990"},{"issue":"1","key":"10.1016\/S0304-3975(00)00312-1_BIB50","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/0743-1066(85)90004-4","article-title":"Some global optimizations for a Prolog compiler","volume":"2","author":"Mellish","year":"1985","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB51","doi-asserted-by":"crossref","unstructured":"K. Muthukumar, M. Hermenegildo, Combined determination of sharing and freeness of program variables through abstract interpretation in: K. Furukawa (Ed.), Logic Programming: Proc. 8th Internat. Conf. on Logic Programming, Paris, France, MIT Press Series in Logic Programming, The MIT Press, Cambridge, MA, 1991, pp. 49\u201363. An extended version appeared in K. Muthukumar, M. Hermenegildo, Compile-time derivation of variable dependency using abstract interpretation, J. Logic Programming 13(2&3) (1992) 315\u2013347.","DOI":"10.1016\/0743-1066(92)90035-2"},{"issue":"2&3","key":"10.1016\/S0304-3975(00)00312-1_BIB52","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0743-1066(92)90035-2","article-title":"Compile-time derivation of variable dependency using abstract interpretation","volume":"13","author":"Muthukumar","year":"1992","journal-title":"J. Logic Programming"},{"issue":"4","key":"10.1016\/S0304-3975(00)00312-1_BIB53","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/BF03037324","article-title":"The occur-check problem in Prolog","volume":"2","author":"Plaisted","year":"1984","journal-title":"New Generation Computing"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB54","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0304-3975(84)90119-1","article-title":"Enumeration of success patterns in logic programs","volume":"34","author":"Sato","year":"1984","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB55","doi-asserted-by":"crossref","unstructured":"H. S\u00f8ndergaard, An application of abstract interpretation of logic programs: occur check reduction, Proc. 1986 European Symp. on Programming, Lecture Notes in Computer Science, Vol. 213, Springer, Berlin 1986, pp. 327\u2013338.","DOI":"10.1007\/3-540-16442-1_25"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB56","unstructured":"A. Taylor, High performance prolog implementation Ph.D. Thesis, Basser Department of Computer Science, University of Sydney, Sydney, Australia, June 1991."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB57","doi-asserted-by":"crossref","unstructured":"P. Van Hentenryck (Ed.), Static Analysis: Proc. 4th Internat. Symp., Paris, France, Lecture Notes in Computer Science, Vol. 1302, Springer, Berlin, 1997.","DOI":"10.1007\/BFb0032729"},{"issue":"2","key":"10.1016\/S0304-3975(00)00312-1_BIB58","doi-asserted-by":"crossref","first-page":"191","DOI":"10.2307\/1968865","article-title":"The closure operators of a lattice","volume":"43","author":"Ward","year":"1942","journal-title":"Ann. Math."},{"key":"10.1016\/S0304-3975(00)00312-1_BIB59","first-page":"92","article-title":"Annotated structure shape graphs for abstract analysis of Prolog","volume":"Vol. 1140","author":"Weyer","year":"1996"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB60","doi-asserted-by":"crossref","unstructured":"E. Zaffanella, R. Bagnara, P.M. Hill, Widening set-sharing, Quaderno 188, Dipartimento di Matematica, Universit\u00e0 di Parma, 1999.","DOI":"10.1007\/10704567_25"},{"key":"10.1016\/S0304-3975(00)00312-1_BIB61","doi-asserted-by":"crossref","unstructured":"E. Zaffanella, P.M. Hill, R. Bagnara, Decomposing non-redundant sharing by complementation, Tech. Rep. 99.07, School of Computer Studies, University of Leeds, 1999.","DOI":"10.1007\/3-540-48294-6_5"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500003121?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397500003121?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,18]],"date-time":"2023-04-18T06:30:39Z","timestamp":1681799439000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397500003121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,4]]},"references-count":61,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2002,4]]}},"alternative-id":["S0304397500003121"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(00)00312-1","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2002,4]]}}}