{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:35:42Z","timestamp":1755999342949,"version":"3.41.0"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T00:00:00Z","timestamp":1560902400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["759969"],"award-info":[{"award-number":["759969"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["n\/a"],"award-info":[{"award-number":["n\/a"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/K009907\/1"],"award-info":[{"award-number":["EP\/K009907\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>\n            Minification is a widely accepted technique that aims at reducing the size of the code transmitted over the web. This article concerns the problem of semantic-preserving minification of Cascading Style Sheets (CSS)\u2014the\n            <jats:italic>de facto<\/jats:italic>\n            language for styling web documents\u2014based on merging similar rules.\n          <\/jats:p>\n          <jats:p>The cascading nature of CSS makes the semantics of CSS files sensitive to the ordering of rules in the file. To automatically identify rule-merging opportunities that best minimise file size, we reduce the rule-merging problem to a problem concerning \u201cCSS-graphs,\u201d i.e., node-weighted bipartite graphs with a dependency ordering on the edges, where weights capture the number of characters.<\/jats:p>\n          <jats:p>Constraint solving plays a key role in our approach. Transforming a CSS file into a CSS-graph problem requires us to extract the dependency ordering on the edges (an NP-hard problem), which requires us to solve the selector intersection problem. To this end, we provide the first full formalisation of CSS3 selectors (the most stable version of CSS) and reduce their selector intersection problem to satisfiability of quantifier-free integer linear arithmetic, for which highly optimised SMT-solvers are available. To solve the above NP-hard graph optimisation problem, we show how Max-SAT solvers can be effectively employed. We have implemented our rule-merging algorithm and tested it against approximately 70 real-world examples (including examples from each of the top 20 most popular websites). We also used our benchmarks to compare our tool against six well-known minifiers (which implement other optimisations). Our experiments suggest that our tool produced larger savings. A substantially better minification rate was shown when our tool is used together with these minifiers.<\/jats:p>","DOI":"10.1145\/3310337","type":"journal-article","created":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T12:05:38Z","timestamp":1560945938000},"page":"1-76","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["CSS Minification via Constraint Solving"],"prefix":"10.1145","volume":"41","author":[{"given":"Matthew","family":"Hague","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, Egham, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony W.","family":"Lin","sequence":"additional","affiliation":[{"name":"TU Kaiserslautern and University of Oxford"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chih-Duo","family":"Hong","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,19]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Alexa Internet. 2017. Alexa Top 500 Global Sites. Retrieved from https:\/\/www.alexa.com\/topsites."},{"volume-title":"Proceedings of the Conference on Object-oriented Programming, Systems, Languages, and Applications (OOPSLA\u201914)","author":"Andreasen E.","key":"e_1_2_1_2_1","unstructured":"E. Andreasen and A. M\u00f8ller. 2014. Determinacy in static analysis for jQuery. In Proceedings of the Conference on Object-oriented Programming, Systems, Languages, and Applications (OOPSLA\u201914). 17--31."},{"key":"e_1_2_1_3_1","volume-title":"Felip Many\u00e0, and Jordi Planes.","author":"Argelich Josep","year":"2016","unstructured":"Josep Argelich, Chu Min Li, Felip Many\u00e0, and Jordi Planes. 2016. Max-SAT\u201916 Competition. Retrieved from http:\/\/maxsat.ia.udl.cat\/."},{"key":"e_1_2_1_4_1","unstructured":"Tab Atkins Jr. Elika J. Etemad and Florian Rivoal. 2017. CSS Snapshot 2017. Retrieved from https:\/\/www.w3.org\/TR\/css-2017."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065172"},{"volume-title":"Proceedings of the 9th International Conference on Database Theory (ICDT\u201903)","author":"Benedikt Michael","key":"e_1_2_1_6_1","unstructured":"Michael Benedikt, Wenfei Fan, and Gabriel M. Kuper. 2003. Structural properties of XPath fragments. In Proceedings of the 9th International Conference on Database Theory (ICDT\u201903). 79--95."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832249.2832283"},{"key":"e_1_2_1_8_1","unstructured":"Johan Bleuzen. 2017. cssmin. Retrieved from https:\/\/www.npmjs.com\/package\/cssmin."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.25.1"},{"key":"e_1_2_1_10_1","unstructured":"Bert Bos. 2016. Cascading Style Sheets Level 2 Revision 2 (CSS 2.2) Specification. Retrieved from https:\/\/www.w3.org\/TR\/CSS22\/."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832415.2832558"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1324777"},{"key":"e_1_2_1_13_1","unstructured":"Ben Briggs et al. 2015. cssnano. Retrieved from http:\/\/cssnano.co."},{"key":"e_1_2_1_14_1","volume-title":"Chris Eppstein et al","author":"Catlin Hampton","year":"2006","unstructured":"Hampton Catlin, Natalie Weizenbaum, Chris Eppstein et al. 2006. Sass. Retrieved from http:\/\/sass-lang.com\/."},{"key":"e_1_2_1_15_1","unstructured":"T. \u00c7elik E. J. Etemad D. Glazman I. Hickson P. Linss and J. Williams. 2011. Selectors Level 3: W3C Recommendation 29 September 2011. Retrieved from http:\/\/www.w3.org\/TR\/2011\/REC-css3-selectors-20110929\/."},{"key":"e_1_2_1_16_1","unstructured":"Steve Clay et al. 2017. minify. Retrieved from https:\/\/github.com\/mrclay\/minify."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2338626.2338632"},{"volume-title":"Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS\u201908)","author":"de Moura L. Mendon\u00e7a","key":"e_1_2_1_18_1","unstructured":"L. Mendon\u00e7a de Moura and N. Bj\u00f8rner. 2008. Z3: An efficient SMT solver. In Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS\u201908)."},{"key":"e_1_2_1_19_1","unstructured":"Roman Dvornov et al. 2017. csso. Retrieved from https:\/\/github.com\/css\/csso."},{"key":"e_1_2_1_20_1","volume-title":"Etemad and Tab Atkins Jr","author":"Elika","year":"2013","unstructured":"Elika J. Etemad and Tab Atkins Jr. 2013. Selectors Level 4: W3C Working Draft 2 May 2013. Retrieved from http:\/\/www.w3.org\/TR\/2013\/WD-selectors4-20130502\/."},{"volume-title":"Handbook of formal languages","author":"G\u00e9cseg Ferenc","key":"e_1_2_1_22_1","unstructured":"Ferenc G\u00e9cseg and Magnus Steinby. 1997. Handbook of formal languages, Vol. 3. Springer-Verlag New York, NY, Chapter Tree Languages, 1--68. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id&equals;267871.267872."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185877.1185882"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187946"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2724712"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/645683.664569"},{"volume-title":"MaxSAT Evaluation 2017: Solver and Benchmark Descriptions","author":"Hague Matthew","key":"e_1_2_1_28_1","unstructured":"Matthew Hague and Anthony Widjaja Lin. 2017. MaxSAT benchmarks: CSS refactoring. In MaxSAT Evaluation 2017: Solver and Benchmark Descriptions, vol. B-2017-2. Department of Computer Science Series of Publications B, University of Helsinki."},{"key":"e_1_2_1_29_1","volume-title":"Anthony Widjaja Lin, and Chih-Duo Hong","author":"Hague Matthew","year":"2018","unstructured":"Matthew Hague, Anthony Widjaja Lin, and Chih-Duo Hong. 2018. Data and Source Code for Sat CSS. Retrieved from https:\/\/figshare.com\/articles\/Data_and_Source_Code_for_Sat_CSS\/7277324."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814288"},{"key":"e_1_2_1_31_1","unstructured":"Jake Hickenlooper. 2014. stripmq. Retrieved from https:\/\/www.npmjs.com\/package\/stripmq."},{"key":"e_1_2_1_32_1","volume-title":"Edward O\u2019Connor, and Silvia Pfeiffer.","author":"Hickson Ian","year":"2014","unstructured":"Ian Hickson, Robin Berjon, Steve Faulkner, Travis Leithead, Erika Doyle Navara, Edward O\u2019Connor, and Silvia Pfeiffer. 2014. HTML5. Retrieved from https:\/\/www.w3.org\/TR\/html5\/."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 9th International Workshop on Database Programming Languages (DBPL\u201903)","author":"Hidders Jan","year":"2003","unstructured":"Jan Hidders. 2003. Satisfiability of XPath expressions. In Proceedings of the 9th International Workshop on Database Programming Languages (DBPL\u201903). 21--36."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814291"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2025113.2025125"},{"volume-title":"Proceedings of the International Static Analysis Symposium (SAS\u201909)","author":"Jensen S. H.","key":"e_1_2_1_36_1","unstructured":"S. H. Jensen, A. M\u00f8ller, and P. Thiemann. 2009. Type analysis for JavaScript. In Proceedings of the International Static Analysis Symposium (SAS\u201909). 238--255."},{"key":"e_1_2_1_37_1","volume-title":"Lewis","author":"Moscovitz Meitar","year":"2010","unstructured":"Meitar Moscovitz and Joseph R. Lewis. 2010. AdvancED CSS. APress."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. 105--108","author":"Kayaaslan Enver","year":"2010","unstructured":"Enver Kayaaslan. 2010. On enumerating all maximal bicliques of bipartite graphs. In Proceedings of the 9th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. 105--108."},{"key":"e_1_2_1_39_1","volume-title":"Logics for unranked trees: An overview. Logic. Methods Comput. Sci. 2, 3","author":"Libkin Leonid","year":"2006","unstructured":"Leonid Libkin. 2006. Logics for unranked trees: An overview. Logic. Methods Comput. Sci. 2, 3 (2006)."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2009.09.005"},{"key":"e_1_2_1_41_1","unstructured":"Glacomo Martino et al. 2013. UnCSS. Retrieved from https:\/\/github.com\/giakki\/uncss."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114247"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1083784.1083792"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635868.2635879"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2337223.2337272"},{"volume-title":"Proceedings of the 19th International Conference on World Wide Web (WWW\u201910)","author":"Leo","key":"e_1_2_1_46_1","unstructured":"Leo A. Meyerovich and Rastislav Bod\u00edk. 2010. Fast and parallel webpage layout. In Proceedings of the 19th International Conference on World Wide Web (WWW\u201910). 711--720."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003261"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/2892753.2892928"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601869"},{"key":"e_1_2_1_50_1","volume-title":"On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logic. Methods Comput. Sci. 2, 3","author":"Neven Frank","year":"2006","unstructured":"Frank Neven and Thomas Schwentick. 2006. On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logic. Methods Comput. Sci. 2, 3 (2006)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192407"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984010"},{"key":"e_1_2_1_53_1","unstructured":"Jakub Pawlowicz. 2017. Clean-css. Retrieved from https:\/\/github.com\/jakubpawlowicz\/clean-css."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00333-0"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/2826097"},{"key":"e_1_2_1_56_1","unstructured":"Armin Rigo et al. 2007. PyPy. Retrieved from http:\/\/pypy.org\/."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1984-0742421-9"},{"volume-title":"Proceedings of the Annual ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201913)","author":"Sch\u00e4fer M.","key":"e_1_2_1_58_1","unstructured":"M. Sch\u00e4fer, M. Sridharan, J. Dolby, and F. Tip. 2013. Dynamic determinacy analysis. In Proceedings of the Annual ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201913). 165--174."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_94"},{"key":"e_1_2_1_60_1","unstructured":"Alexis Sellier et al. 2009. Less. Retrieved from http:\/\/lesscss.org\/."},{"key":"e_1_2_1_61_1","unstructured":"Thomas Sha et al. 2014. YUI Compressor. Retrieved from http:\/\/yui.github.io\/yuicompressor\/."},{"volume-title":"Eight Best CSS Minifiers as of","year":"2017","key":"e_1_2_1_62_1","unstructured":"Slant. 2017. Eight Best CSS Minifiers as of 2017. Retrieved from https:\/\/www.slant.co\/topics\/261\/ best-css-minifiers."},{"key":"e_1_2_1_63_1","unstructured":"Jennifer Slegg. 2017. Google mobile first index: Page speed included as a ranking factor. Retrieved from http:\/\/www.thesempost.com\/google-mobile-first-index-page-speed-ranking\/."},{"key":"e_1_2_1_64_1","unstructured":"Steve Souders. 2007. High Performance Web Sites: Essential Knowledge for Front-End Engineers. O\u2019Reilly Media."},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31057-7_20"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3156016"},{"volume-title":"Proceedings of the 5th Annual ACM Symposium on Theory of Computing. 1--9.","author":"Larry","key":"e_1_2_1_67_1","unstructured":"Larry J. Stockmeyer and Albert R. Meyer. 1973. Word problems requiring exponential time: Preliminary report. In Proceedings of the 5th Annual ACM Symposium on Theory of Computing. 1--9."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2009.09.002"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328854.1328858"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9151-9"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/1961204.1961205"},{"key":"e_1_2_1_72_1","unstructured":"Unicode Inc. 2016. The Unicode Standard Version 9.0. Retrieved from http:\/\/www.unicode.org\/versions\/Unicode9.0.0."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.5555\/239519.239527"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804355"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3310337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:37Z","timestamp":1750204417000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,19]]},"references-count":73,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3310337"],"URL":"https:\/\/doi.org\/10.1145\/3310337","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2019,6,19]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}