{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T05:21:29Z","timestamp":1743139289295,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319192246"},{"type":"electronic","value":"9783319192253"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19225-3_8","type":"book-chapter","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T15:51:06Z","timestamp":1434383466000},"page":"93-104","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Compressibility of Finite Languages by Grammars"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Eberhard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Hetzl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"key":"8_CR1","first-page":"2","volume-title":"The Handbook of Proof Theory","author":"S Buss","year":"1998","unstructured":"Buss, S.: An Introduction to proof theory. In: Buss, S. (ed.) The Handbook of Proof Theory, pp. 2\u201378. Elsevier, Amsterdam (1998)"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/3-540-60178-3_85","volume-title":"Logic and Computational Complexity","author":"SR Buss","year":"1995","unstructured":"Buss, S.R.: On Herbrand\u2019s theorem. In: Leivant, D. (ed.) LCC\u201994. LNCS, vol. 960, pp. 195\u2013209. Springer, Heidelberg (1995)"},{"key":"8_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/3-540-48057-9_4","volume-title":"Automata Implementation","author":"C C\u00e2mpeanu","year":"1999","unstructured":"C\u00e2mpeanu, C., S\u00e2ntean, N., Yu, S.: Minimal cover-automata for finite languages. In: Champarnaud, J.-M., Maurel, D., Ziadi, D. (eds.) WIA 1998. LNCS, vol. 1660, pp. 43\u201356. Springer, Heidelberg (1999)"},{"issue":"1\u20132","key":"8_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(00)00292-9","volume":"267","author":"C C\u00e2mpeanu","year":"2001","unstructured":"C\u00e2mpeanu, C., Santean, N., Yu, S.: Minimal cover-automata for finite languages. Theoret. Comput. Sci. 267(1\u20132), 3\u201316 (2001)","journal-title":"Theoret. Comput. Sci."},{"issue":"7","key":"8_CR5","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR6","unstructured":"Herbrand, J.: Recherches sur la th\u00e9orie de la d\u00e9monstration. Ph.D. thesis, Universit\u00e9 de Paris (1930)"},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-642-28332-1_26","volume-title":"Language and Automata Theory and Applications","author":"S Hetzl","year":"2012","unstructured":"Hetzl, S.: Applying tree languages in proof theory. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 301\u2013312. Springer, Heidelberg (2012)"},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/978-3-319-08587-6_17","volume-title":"Automated Reasoning","author":"S Hetzl","year":"2014","unstructured":"Hetzl, S., Leitsch, A., Reis, G., Tapolczai, J., Weller, D.: Introducing quantified cuts in logic with equality. In: Demri, S., Kapur, D., Weidenbach, C. (eds.) IJCAR 2014. LNCS, vol. 8562, pp. 240\u2013254. Springer, Heidelberg (2014)"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2014.05.018","volume":"549","author":"S Hetzl","year":"2014","unstructured":"Hetzl, S., Leitsch, A., Reis, G., Weller, D.: Algorithmic introduction of quantified cuts. Theoret. Comput. Sci. 549, 1\u201316 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-642-28717-6_19","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"S Hetzl","year":"2012","unstructured":"Hetzl, S., Leitsch, A., Weller, D.: Towards algorithmic cut-introduction. In: Bj\u00f8rner, N., Voronkov, A. (eds.) LPAR-18 2012. LNCS, vol. 7180, pp. 228\u2013242. Springer, Heidelberg (2012)"},{"key":"8_CR11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Cambridge (1979)"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-642-00982-2_38","volume-title":"Language and Automata Theory and Applications","author":"F Jacquemard","year":"2009","unstructured":"Jacquemard, F., Klay, F., Vacher, C.: Rigid tree automata. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 446\u2013457. Springer, Heidelberg (2009)"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1016\/j.ic.2010.11.015","volume":"209","author":"F Jacquemard","year":"2011","unstructured":"Jacquemard, F., Klay, F., Vacher, C.: Rigid tree automata and applications. Inf. Comput. 209, 486\u2013512 (2011)","journal-title":"Inf. Comput."},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-3-642-38905-4_17","volume-title":"Combinatorial Pattern Matching","author":"A Je\u017c","year":"2013","unstructured":"Je\u017c, A.: Approximation of grammar-based compression via recompression. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 165\u2013176. Springer, Heidelberg (2013)"},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/978-3-319-07566-2_19","volume-title":"Combinatorial Pattern Matching","author":"A Je\u017c","year":"2014","unstructured":"Je\u017c, A.: A really simple approximation of smallest grammar. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 182\u2013191. Springer, Heidelberg (2014)"},{"issue":"3","key":"8_CR16","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1109\/18.841160","volume":"46","author":"JC Kieffer","year":"2000","unstructured":"Kieffer, J.C., Yang, E.H.: Grammar-based codes: a new class of universal lossless source codes. IEEE Trans. Inf. Theory 46(3), 737\u2013754 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Data Compression Conference (DCC 1999). pp. 296\u2013305. IEEE Computer Society (1999)","DOI":"10.1109\/DCC.1999.755679"},{"issue":"2","key":"8_CR18","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on SLP-compressed strings: a survey. Groups Complex. Cryptol. 4(2), 241\u2013299 (2012)","journal-title":"Groups Complex. Cryptol."},{"key":"8_CR19","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.374","volume":"7","author":"CG Nevill-Manning","year":"1997","unstructured":"Nevill-Manning, C.G., Witten, I.H.: Identifying hierarchical structure in sequences: a linear-time algorithm. J. Artif. Intell. Res. 7, 67\u201382 (1997)","journal-title":"J. Artif. Intell. Res."},{"key":"8_CR20","first-page":"137","volume":"88","author":"V Orevkov","year":"1979","unstructured":"Orevkov, V.: Lower bounds for increasing complexity of derivations after cut elimination. Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta 88, 137\u2013161 (1979)","journal-title":"Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta"},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/S0049-237X(98)80023-2","volume-title":"Handbook of Proof Theory","author":"P Pudl\u00e1k","year":"1998","unstructured":"Pudl\u00e1k, P.: The Lengths of proofs. In: Buss, S. (ed.) Handbook of Proof Theory, pp. 547\u2013637. Elsevier, Amsterdam (1998)"},{"key":"8_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/978-3-540-79709-8_4","volume-title":"Computer Science \u2013 Theory and Applications","author":"P Pudl\u00e1k","year":"2008","unstructured":"Pudl\u00e1k, P.: Twelve problems in proof complexity. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol. 5010, pp. 13\u201327. Springer, Heidelberg (2008)"},{"issue":"1\u20133","key":"8_CR23","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theoret. Comput. Sci. 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"2\u20134","key":"8_CR24","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1016\/j.jda.2004.08.016","volume":"3","author":"H Sakamoto","year":"2005","unstructured":"Sakamoto, H.: A fully linear-time approximation algorithm for grammar-based compression. J. Discrete Algorithms 3(2\u20134), 416\u2013430 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"8_CR25","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1006\/jcss.1996.0046","volume":"53","author":"J Shallit","year":"1996","unstructured":"Shallit, J., Breitbart, Y.: Automaticity I: properties of a measure of descriptional complexity. J. Comput. Syst. Sci. 53, 10\u201325 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"8_CR26","first-page":"537","volume":"6","author":"J Shallit","year":"2001","unstructured":"Shallit, J., Wang, M.W.: Automatic complexity of strings. J. Automata, Lang. Comb. 6(4), 537\u2013554 (2001)","journal-title":"J. Automata, Lang. Comb."},{"key":"8_CR27","first-page":"104","volume":"75","author":"R Statman","year":"1979","unstructured":"Statman, R.: Lower bounds on Herbrand\u2019s theorem. Proc. Am. Math. Soc. 75, 104\u2013107 (1979)","journal-title":"Proc. Am. Math. Soc."},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Storer, J.A., Szymanski, T.G.: The macro model for data compression (extended abstract). In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing (STOC \u201978). pp. 30\u201339. ACM, New York (1978)","DOI":"10.1145\/800133.804329"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19225-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T08:23:24Z","timestamp":1676017404000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19225-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319192246","9783319192253"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19225-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"16 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}