{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T15:13:52Z","timestamp":1767453232516,"version":"3.37.3"},"reference-count":44,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"1","license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/501100001691","name":"JSPS KAKENHI","doi-asserted-by":"publisher","award":["JP16H02783","JP20H04141"],"award-info":[{"award-number":["JP16H02783","JP20H04141"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"JSPS KAKENHI","doi-asserted-by":"publisher","award":["JP17H01697"],"award-info":[{"award-number":["JP17H01697"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"JST PRESTO","doi-asserted-by":"publisher","award":["JPMJPR1922"],"award-info":[{"award-number":["JPMJPR1922"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"National Science Centre, Poland","doi-asserted-by":"publisher","award":["2017\/26\/E\/ST6\/00191"],"award-info":[{"award-number":["2017\/26\/E\/ST6\/00191"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"DFG","doi-asserted-by":"publisher","award":["LO 748\/10-1 (QUANTKOMP)"],"award-info":[{"award-number":["LO 748\/10-1 (QUANTKOMP)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1109\/tit.2020.3038147","type":"journal-article","created":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T22:01:59Z","timestamp":1605304919000},"page":"317-328","source":"Crossref","is-referenced-by-count":5,"title":["The Smallest Grammar Problem Revisited"],"prefix":"10.1109","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6856-5185","authenticated-orcid":false,"given":"Hideo","family":"Bannai","sequence":"first","affiliation":[]},{"given":"Momoko","family":"Hirayama","sequence":"additional","affiliation":[]},{"given":"Danny","family":"Hucke","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4321-3105","authenticated-orcid":false,"given":"Artur","family":"Jez","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4680-7198","authenticated-orcid":false,"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3884-8942","authenticated-orcid":false,"given":"Carl Philipp","family":"Reh","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref39","first-page":"1","article-title":"Universal lossless data compression via binary decision diagrams","volume":"abs 1111 1432","author":"kieffer","year":"2011","journal-title":"CoRR"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2016.69"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00426-7"},{"article-title":"Browsing and searching compressed documents","year":"2003","author":"wan","key":"ref32"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/1841909.1841913"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32686-9_3"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2017.52"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2019.00059"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.06.006"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73437-6_23"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.4310\/CIS.2002.v2.n1.a2"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.1998.672138"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/18.841161"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38905-4_23"},{"key":"ref13","article-title":"Entropy bounds for grammar compression","volume":"abs 1804 8547","author":"ga?czorz","year":"2018","journal-title":"CoRR"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2871452"},{"key":"ref15","first-page":"11:1","article-title":"Entropy lower bounds for dictionary compression","volume":"128","author":"ga?czorz","year":"2019","journal-title":"Proc Annual Symp on Combinatorial Pattern Matching (CPM)"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/130936889"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1515\/gcc-2012-0016"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188814"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.016"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90031-7"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00777-6"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/18.850665"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2017.24"},{"article-title":"A new combinatorial complexity measure for languages","year":"1986","author":"diwan","key":"ref5"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.1999.755679"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1613\/jair.374"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/360363.360368"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46049-9_4"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797331105"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322346"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/0205008"},{"key":"ref42","first-page":"758","article-title":"A combinatorial problem","volume":"49","author":"de bruijn","year":"1946","journal-title":"Proc Sect Sci Koninklijke"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2006.59"},{"key":"ref41","first-page":"3","article-title":"Approximation ratios of RePair, LongestMatch and Greedy on unary strings","volume":"11811","author":"hucke","year":"2019","journal-title":"Proc 26th Int Symp String Process Inf Retr (SPIRE)"},{"key":"ref23","first-page":"122:1","article-title":"On the complexity of grammar-based compression over fixed alphabets","volume":"55","author":"casel","year":"2016","journal-title":"Proc 43rd Int Colloq Automata Lang Program (ICALP)"},{"key":"ref44","volume":"11811","author":"brisaboa","year":"2019","journal-title":"Proc 26th Int Symp String Process Inf Retr (SPIRE)"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.12.032"},{"journal-title":"Proc Data Compression Conference (DCC)","year":"2017","author":"bilgin","key":"ref43"},{"key":"ref25","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2015.05.027","article-title":"Approximation of grammar-based compression via recompression","volume":"592","author":"je?","year":"2015","journal-title":"Theor Comput Sci"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/9300279\/09259056.pdf?arnumber=9259056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,10]],"date-time":"2022-05-10T14:54:24Z","timestamp":1652194464000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9259056\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":44,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.1109\/tit.2020.3038147","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"type":"print","value":"0018-9448"},{"type":"electronic","value":"1557-9654"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}