{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:04Z","timestamp":1750306804171,"version":"3.41.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T00:00:00Z","timestamp":1380585600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2013,10]]},"abstract":"<jats:p>\n            Modern software systems are built by composing components drawn from large\n            <jats:italic>repositories<\/jats:italic>\n            , whose size and complexity is increasing at a very fast pace. A fundamental challenge for the maintainability and the scalability of such software systems is the ability to quickly identify the components that can or cannot be installed together: this is the\n            <jats:italic>co-installability<\/jats:italic>\n            problem, which is related to boolean satisfiability and is known to be algorithmically hard. This article develops a novel theoretical framework, based on formally certified semantic preserving graph-theoretic transformations, that allows us to associate to each concrete component repository a much smaller one with a simpler structure, that we call\n            <jats:italic>strongly flat<\/jats:italic>\n            , with equivalent co-installability properties. This flat repository can be displayed in a way that provides a concise view of the co-installability issues in the original repository, or used as a basis for various algorithms related to co-installability, like the efficient computation of strong conflicts between components. The proofs contained in this work have been machine checked using the Coq proof assistant.\n          <\/jats:p>","DOI":"10.1145\/2522920.2522927","type":"journal-article","created":{"date-parts":[[2013,10,17]],"date-time":"2013-10-17T12:23:34Z","timestamp":1382012614000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["On software component co-installability"],"prefix":"10.1145","volume":"22","author":[{"given":"J\u00e9r\u00f4me","family":"Vouillon","sequence":"first","affiliation":[{"name":"CNRS, PPS, UMR 7126, Univ Paris Diderot, Sorbonne Paris Cit\u00e9, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto Di","family":"Cosmo","sequence":"additional","affiliation":[{"name":"Univ Paris Diderot, Sorbonne Paris Cit\u00e9, PPS, UMR 7126, CNRS, INRIA, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,10,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ESEM.2009.5316017"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000229.2000255"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2012.02.018"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2304736.2304747"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11785477_26"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.29.2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2157.322404"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215029"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Baader F. and Nipkow T. 1998. Term Rewriting and All That. Cambridge University Press.   Baader F. and Nipkow T. 1998. Term Rewriting and All That. Cambridge University Press.","DOI":"10.1017\/CBO9781139172752"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016553006778"},{"key":"e_1_2_1_11_1","unstructured":"The Coq Development Team. 2008. The Coq Proof Assistant Reference Manual -- Version V8.2.  The Coq Development Team. 2008. The Coq Proof Assistant Reference Manual -- Version V8.2."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294283"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/503209.503226"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1730874.1730905"},{"volume-title":"Proceedings of the FRCSS'06 Workshop. EASST Newsletter.","author":"Di Cosmo R.","key":"e_1_2_1_15_1","unstructured":"Di Cosmo , R. , Durak , B. , Leroy , X. , Mancinelli , F. , and Vouillon , J . 2006a. Maintaining large software distributions: New challenges from the FOSS era . In Proceedings of the FRCSS'06 Workshop. EASST Newsletter. Di Cosmo, R., Durak, B., Leroy, X., Mancinelli, F., and Vouillon, J. 2006a. Maintaining large software distributions: New challenges from the FOSS era. In Proceedings of the FRCSS'06 Workshop. EASST Newsletter."},{"volume-title":"Proceedings of the 2nd Workshop on Logics for Component Configuration, C. Drescher, I. Lynce, and R. Treinen, Eds., EPTCS 65","author":"Di Cosmo R.","key":"e_1_2_1_16_1","unstructured":"Di Cosmo , R. , Lhomme , O. , and Michel , C . 2011. Aligning component upgrades . In Proceedings of the 2nd Workshop on Logics for Component Configuration, C. Drescher, I. Lynce, and R. Treinen, Eds., EPTCS 65 , 1--11. Di Cosmo, R., Lhomme, O., and Michel, C. 2011. Aligning component upgrades. In Proceedings of the 2nd Workshop on Logics for Component Configuration, C. Drescher, I. Lynce, and R. Treinen, Eds., EPTCS 65, 1--11."},{"key":"e_1_2_1_17_1","unstructured":"Di Cosmo R. Mancinelli F. Boender J. Vouillon J. Durak B. Leroy X. Pinheiro D. Trezentos P. Morgado M. Milo T. Zur T. Suarez R. Lijour M. and Treinen R. 2006b. Report on formal mangement of software dependencies. Tech. rep. EDOS. Apr. EDOS project Deliverable 2.2. http:\/\/www.edos-project.org\/xwiki\/bin\/download\/Main\/Deliverables\/edos-wp2d2.pdf.  Di Cosmo R. Mancinelli F. Boender J. Vouillon J. Durak B. Leroy X. Pinheiro D. Trezentos P. Morgado M. Milo T. Zur T. Suarez R. Lijour M. and Treinen R. 2006b. Report on formal mangement of software dependencies. Tech. rep. EDOS. Apr. EDOS project Deliverable 2.2. http:\/\/www.edos-project.org\/xwiki\/bin\/download\/Main\/Deliverables\/edos-wp2d2.pdf."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025149"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Di Cosmo R.\n     and \n      Zacchiroli S\n  . \n  2010\n  . Feature diagrams as package dependencies. In Proceedings of SPLC. J. Bosch and J. Lee Eds Lecture Notes in Computer Science Series vol. \n  6287 Springer 476--480.   Di Cosmo R. and Zacchiroli S. 2010. Feature diagrams as package dependencies. In Proceedings of SPLC. J. Bosch and J. Lee Eds Lecture Notes in Computer Science Series vol. 6287 Springer 476--480.","DOI":"10.1007\/978-3-642-15579-6_40"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(84)90014-1"},{"key":"e_1_2_1_21_1","volume-title":"Graphviz: Open source graph drawing tools. In Lecture Notes in Computer Science","author":"Ellson J.","year":"2001","unstructured":"Ellson , J. , Gansner , E. , Koutsofios , L. , North , S. , Woodhull , G. 2001 . Graphviz: Open source graph drawing tools. In Lecture Notes in Computer Science , Springer-Verlag , 483--484. Ellson, J., Gansner, E., Koutsofios, L., North, S., Woodhull, G. 2001. Graphviz: Open source graph drawing tools. In Lecture Notes in Computer Science, Springer-Verlag, 483--484."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.65.2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.859533"},{"key":"e_1_2_1_24_1","unstructured":"Hanneman R. A. and Riddle M. 2005. Introduction to Social Network Methods. University of California Riverside.  Hanneman R. A. and Riddle M. 2005. Introduction to Social Network Methods. University of California Riverside."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/352591.352593"},{"volume-title":"Proceedings of SPLC (2). S. Thiel and K. Pohl, Eds., Lero International Science Centre","author":"Le Berre D.","key":"e_1_2_1_26_1","unstructured":"Le Berre , D. and Parrain , A . 2008. On SAT technologies for dependency management and beyond . In Proceedings of SPLC (2). S. Thiel and K. Pohl, Eds., Lero International Science Centre , University of Limerick, Ireland, 197--200. Le Berre, D. and Parrain, A. 2008. On SAT technologies for dependency management and beyond. In Proceedings of SPLC (2). S. Thiel and K. Pohl, Eds., Lero International Science Centre, University of Limerick, Ireland, 197--200."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASE.2006.49"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/940071.940110"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"McCamant S.\n     and \n      Ernst M. D\n  . \n  2004\n  . Early identification of incompatibilities in multi-component upgrades. In Proceedings of ECOOP. M. Odersky Ed. Lecture Notes in Computer Science vol. \n  3086 Springer 440--464.  McCamant S. and Ernst M. D. 2004. Early identification of incompatibilities in multi-component upgrades. In Proceedings of ECOOP. M. Odersky Ed. Lecture Notes in Computer Science vol. 3086 Springer 440--464.","DOI":"10.1007\/978-3-540-24851-4_20"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ESEM.2007.87"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315311"},{"volume-title":"Proceedings of, EVOL'08","author":"Pei-Breivold H.","key":"e_1_2_1_32_1","unstructured":"Pei-Breivold , H. , Crnkovic , I. , Land , R. , and Larsson , S . 2008. Using dependency model to support software architecture evolution . In Proceedings of, EVOL'08 . Pei-Breivold, H., Crnkovic, I., Land, R., and Larsson, S. 2008. Using dependency model to support software architecture evolution. In Proceedings of, EVOL'08."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2008.03.001"},{"volume-title":"Proceedings of 9th Annual Conference of the Debian Project (DebConf8). 18--43","author":"Treinen R.","key":"e_1_2_1_34_1","unstructured":"Treinen , R. and Zacchiroli , S . 2008. Solving package dependencies: From EDOS to Mancoosi . In Proceedings of 9th Annual Conference of the Debian Project (DebConf8). 18--43 . Treinen, R. and Zacchiroli, S. 2008. Solving package dependencies: From EDOS to Mancoosi. In Proceedings of 9th Annual Conference of the Debian Project (DebConf8). 18--43."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1858996.1859087"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2007.59"},{"key":"e_1_2_1_37_1","series-title":"Lecture Notes in Computer Science","volume-title":"Petri Nets: Applications and Relationships to Other Models of Concurrency","author":"Winskel G.","unstructured":"Winskel , G. 1987. Event structures . In Petri Nets: Applications and Relationships to Other Models of Concurrency , W. Brauer, W. Reisig, and G. Rozenberg, Eds., Lecture Notes in Computer Science , vol. 255 , Springer Berlin , 325--392. Winskel, G. 1987. Event structures. In Petri Nets: Applications and Relationships to Other Models of Concurrency, W. Brauer, W. Reisig, and G. Rozenberg, Eds., Lecture Notes in Computer Science, vol. 255, Springer Berlin, 325--392."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321631.1321696"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390630.1390640"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1368088.1368161"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2522920.2522927","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2522920.2522927","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:53Z","timestamp":1750232093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2522920.2522927"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1145\/2522920.2522927"],"URL":"https:\/\/doi.org\/10.1145\/2522920.2522927","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"type":"print","value":"1049-331X"},{"type":"electronic","value":"1557-7392"}],"subject":[],"published":{"date-parts":[[2013,10]]},"assertion":[{"value":"2011-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}