{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T13:18:20Z","timestamp":1770556700739,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T00:00:00Z","timestamp":1625011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Centre, Poland","award":["2017\/26\/E\/ST6\/00191"],"award-info":[{"award-number":["2017\/26\/E\/ST6\/00191"]}]},{"name":"DFG research project","award":["LO 748\/10-1"],"award-info":[{"award-number":["LO 748\/10-1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>\n            We show that a context-free grammar of size\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            that produces a single string\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            of length\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            (such a grammar is also called a string straight-line program) can be transformed in linear time into a context-free grammar for\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            of size\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , whose unique derivation tree has depth\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            . This solves an open problem in the area of grammar-based compression, improves many results in this area, and greatly simplifies many existing constructions. Similar results are shown for two formalisms for grammar-based tree compression: top dags and forest straight-line programs. These balancing results can be all deduced from a single meta-theorem stating that the depth of an algebraic circuit over an algebra with a certain finite base property can be reduced to\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            with the cost of a constant multiplicative size increase. Here,\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            refers to the size of the unfolding (or unravelling) of the circuit. In particular, this results applies to standard arithmetic circuits over (noncommutative) semirings.\n          <\/jats:p>","DOI":"10.1145\/3457389","type":"journal-article","created":{"date-parts":[[2021,6,30]],"date-time":"2021-06-30T19:11:05Z","timestamp":1625080265000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Balancing Straight-line Programs"],"prefix":"10.1145","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0775-7781","authenticated-orcid":false,"given":"Moses","family":"Ganardi","sequence":"first","affiliation":[{"name":"Max Planck Institute for Software Systems (MPI-SWS), Kaiserslautern, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4321-3105","authenticated-orcid":false,"given":"Artur","family":"Je\u017c","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[{"name":"University of Siegen, Siegen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00227-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_13"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0068-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_9"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC\u201919)","volume":"149","author":"Bille Philip","year":"2019","unstructured":"Philip Bille , Pawe\u0142 Gawrychowski , Inge Li G\u00f8rtz , Gad M. Landau , and Oren Weimann . 2019 . Top tree compression of tries . In Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC\u201919) , volume 149 of LIPIcs, Pinyan Lu and Guochuan Zhang (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 4:1\u20134:18. Philip Bille, Pawe\u0142 Gawrychowski, Inge Li G\u00f8rtz, Gad M. Landau, and Oren Weimann. 2019. Top tree compression of tries. In Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC\u201919), volume 149 of LIPIcs, Pinyan Lu and Guochuan Zhang (Eds.). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 4:1\u20134:18."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.01.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.012"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/130936889"},{"key":"e_1_2_1_9_1","series-title":"Texts in Logic and Games","volume-title":"Proceedings of Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]","author":"Boja\u0144czyk Miko\u0142aj","unstructured":"Miko\u0142aj Boja\u0144czyk and Igor Walukiewicz . 2008. Forest algebras . In Proceedings of Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas] , volume 2 of Texts in Logic and Games . Amsterdam University Press , 107\u2013132. Miko\u0142aj Boja\u0144czyk and Igor Walukiewicz. 2008. Forest algebras. In Proceedings of Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas], volume 2 of Texts in Logic and Games. Amsterdam University Press, 107\u2013132."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01762121"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM\u201918)","volume":"105","author":"Dudek Bart\u0142omiej","year":"2018","unstructured":"Bart\u0142omiej Dudek and Pawe\u0142 Gawrychowski . 2018 . Slowing down top trees for better worst-case compression . In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM\u201918) , volume 105 of LIPIcs. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 16:1\u201316:8. Bart\u0142omiej Dudek and Pawe\u0142 Gawrychowski. 2018. Slowing down top trees for better worst-case compression. In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM\u201918), volume 105 of LIPIcs. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 16:1\u201316:8."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.12.007"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-90530-3_11"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3278158"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00073"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2005.78"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.07.002"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3451400.3451411"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20086-6_2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.009"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.027"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2631920"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.12.032"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/111662.111680"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394373.2394405"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0016"},{"key":"e_1_2_1_30_1","volume-title":"The Compressed Word Problem for Groups","author":"Lohrey Markus","unstructured":"Markus Lohrey . 2014. The Compressed Word Problem for Groups . SpringerBriefs in Mathematics. Springer . Markus Lohrey. 2014. The Compressed Word Problem for Groups. SpringerBriefs in Mathematics. Springer."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21500-6_3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.06.006"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0331-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009179"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90090-6"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00777-6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3485"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38905-4_24"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457389","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457389","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:07Z","timestamp":1750195687000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457389"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1145\/3457389"],"URL":"https:\/\/doi.org\/10.1145\/3457389","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,30]]},"assertion":[{"value":"2020-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}