{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,19]],"date-time":"2024-06-19T19:48:41Z","timestamp":1718826521951},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,3,1]],"date-time":"2012-03-01T00:00:00Z","timestamp":1330560000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Higher-Order Symb Comput"],"published-print":{"date-parts":[[2012,3]]},"DOI":"10.1007\/s10990-013-9093-z","type":"journal-article","created":{"date-parts":[[2013,8,13]],"date-time":"2013-08-13T12:17:50Z","timestamp":1376396270000},"page":"39-84","source":"Crossref","is-referenced-by-count":10,"title":["Functional programs as compressed data"],"prefix":"10.1007","volume":"25","author":[{"given":"Naoki","family":"Kobayashi","sequence":"first","affiliation":[]},{"given":"Kazutaka","family":"Matsuda","sequence":"additional","affiliation":[]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[]},{"given":"Kazuya","family":"Yaguchi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,8,14]]},"reference":[{"key":"9093_CR1","first-page":"119","volume-title":"Data Compression Conference 1998 (DCC98)","author":"A. Apostolico","year":"1998","unstructured":"Apostolico, A., Lonardi, S.: Some theory and proactive of greedy off-line textual substitution. In: Data Compression Conference 1998 (DCC98), pp.\u00a0119\u2013128 (1998)"},{"issue":"4","key":"9093_CR2","doi-asserted-by":"crossref","first-page":"931","DOI":"10.2307\/2273659","volume":"48","author":"H. Barendregt","year":"1983","unstructured":"Barendregt, H., Coppo, M., Dezani-Ciancaglini, M.: A\u00a0filter lambda model and the completeness of type assignment. J.\u00a0Symb. Log. 48(4), 931\u2013940 (1983)","journal-title":"J.\u00a0Symb. Log."},{"key":"9093_CR3","first-page":"120","volume-title":"Proceedings of LICS 2010","author":"C.H. Broadbent","year":"2010","unstructured":"Broadbent, C.H., Carayol, A., Ong, C.-H.L., Serre, O.: Recursion schemes and logical reflection. In: Proceedings of LICS 2010, pp.\u00a0120\u2013129. IEEE Computer Society Press, Los Alamitos (2010)"},{"issue":"4\u20135","key":"9093_CR4","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/j.is.2008.01.004","volume":"33","author":"G. Busatto","year":"2008","unstructured":"Busatto, G., Lohrey, M., Maneth, S.: Efficient memory representation of XML document trees. Inf. Syst. 33(4\u20135), 456\u2013474 (2008)","journal-title":"Inf. Syst."},{"issue":"7","key":"9093_CR5","doi-asserted-by":"crossref","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":"9093_CR6","volume-title":"Annals of Mathematics Studies","author":"A. Church","year":"1941","unstructured":"Church, A.: The calculi of lambda-conversion. In: Annals of Mathematics Studies, vol.\u00a06. Princeton University Press, Princeton (1941)"},{"key":"9093_CR7","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007). Available on http:\/\/www.grappa.univ-lille3.fr\/tata . Release October, 12th 2007"},{"key":"9093_CR8","doi-asserted-by":"crossref","DOI":"10.1142\/4838","volume-title":"Jewels of Stringology","author":"M. Crochemore","year":"2002","unstructured":"Crochemore, M., Rytter, W.: Jewels of Stringology. World Scientific, Singapore (2002)"},{"key":"9093_CR9","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(82)90009-3","volume":"20","author":"W. Dam","year":"1982","unstructured":"Dam, W.: The IO- and OI-hierarchies. Theor. Comput. Sci. 20, 95\u2013207 (1982)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9093_CR10","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/BF01704020","volume":"9","author":"J. Engelfriet","year":"1975","unstructured":"Engelfriet, J.: Bottom-up and top-down tree transformations\u2014a comparison. Math. Syst. Theory 9(3), 198\u2013231 (1975)","journal-title":"Math. Syst. Theory"},{"issue":"2","key":"9093_CR11","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(80)90058-6","volume":"20","author":"J. Engelfriet","year":"1980","unstructured":"Engelfriet, J., Rozenberg, G., Slutzki, G.: Tree transducers, L systems, and two-way machines. J.\u00a0Comput. Syst. Sci. 20(2), 150\u2013202 (1980)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"1\/2","key":"9093_CR12","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02915449","volume":"26","author":"J. Engelfriet","year":"1988","unstructured":"Engelfriet, J., Vogler, H.: High level tree transducers and iterated pushdown tree transducers. Acta Inform. 26(1\/2), 131\u2013192 (1988)","journal-title":"Acta Inform."},{"key":"9093_CR13","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1145\/165180.165214","volume-title":"FPCA","author":"A.J. Gill","year":"1993","unstructured":"Gill, A.J., Launchbury, J., Peyton-Jones, S.L.: A\u00a0short cut to deforestation. In: FPCA, pp.\u00a0223\u2013232 (1993)"},{"key":"9093_CR14","first-page":"452","volume-title":"Proceedings of LICS 2008","author":"M. Hague","year":"2008","unstructured":"Hague, M., Murawski, A., Ong, C.-H.L., Serre, O.: Collapsible pushdown automata and recursion schemes. In: Proceedings of LICS 2008, pp.\u00a0452\u2013461. IEEE Computer Society, Los Alamitos (2008)"},{"key":"9093_CR15","volume-title":"Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability","author":"M. Hutter","year":"2004","unstructured":"Hutter, M.: Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability. Springer, Berlin (2004)"},{"key":"9093_CR16","first-page":"672","volume-title":"COLING","author":"H. Kaji","year":"1992","unstructured":"Kaji, H., Kida, Y., Morimoto, Y.: Learning translation templates from bilingual text. In: COLING, pp.\u00a0672\u2013678 (1992)"},{"issue":"2","key":"9093_CR17","first-page":"129","volume":"4","author":"M. Karpinski","year":"1997","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: An efficient pattern matching algorithm for strings with short description. Nord. J. Comput. 4(2), 129\u2013144 (1997)","journal-title":"Nord. J. Comput."},{"issue":"298","key":"9093_CR18","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0304-3975(02)00426-7","volume":"1","author":"T. Kida","year":"2003","unstructured":"Kida, T., Matsumoto, T., Shibata, Y., Takeda, M., Shinohara, A., Arikawa, S.: Collage system: a unifying framework for compressed pattern matching. Theor. Comput. Sci. 1(298), 253\u2013272 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9093_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/3-540-45931-6_15","volume-title":"Proceedings of FOSSACS 2002","author":"T. Knapik","year":"2002","unstructured":"Knapik, T., Niwinski, D., Urzyczyn, P.: Higher-order pushdown trees are easy. In: Proceedings of FOSSACS 2002. Lecture Notes in Computer Science, vol.\u00a02303, pp.\u00a0205\u2013222. Springer, Berlin (2002)"},{"key":"9093_CR20","first-page":"25","volume-title":"Proceedings of PPDP 2009","author":"N. Kobayashi","year":"2009","unstructured":"Kobayashi, N.: Model-checking higher-order functions. In: Proceedings of PPDP 2009, pp.\u00a025\u201336. ACM Press, New York (2009)"},{"key":"9093_CR21","first-page":"416","volume-title":"Proceedings of ACM SIGPLAN\/SIGACT Symposium on Principles of Programming Languages (POPL)","author":"N. Kobayashi","year":"2009","unstructured":"Kobayashi, N.: Types and higher-order recursion schemes for verification of higher-order programs. In: Proceedings of ACM SIGPLAN\/SIGACT Symposium on Principles of Programming Languages (POPL), pp.\u00a0416\u2013428 (2009)"},{"key":"9093_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/978-3-642-19805-2_18","volume-title":"Proceedings of FOSSACS 2011","author":"N. Kobayashi","year":"2011","unstructured":"Kobayashi, N.: A\u00a0practical linear time algorithm for trivial automata model checking of higher-order recursion schemes. In: Proceedings of FOSSACS 2011. Lecture Notes in Computer Science, vol.\u00a06604, pp.\u00a0260\u2013274. Springer, Berlin (2011)"},{"key":"9093_CR23","doi-asserted-by":"crossref","unstructured":"Kobayashi, N.: Model checking higher-order programs. J. ACM 60(3) (2013)","DOI":"10.1145\/2487241.2487246"},{"key":"9093_CR24","first-page":"121","volume-title":"Proceedings of PEPM 2012","author":"N. Kobayashi","year":"2012","unstructured":"Kobayashi, N., Matsuda, K., Shinohara, A.: Functional programs as compressed data. In: Proceedings of PEPM 2012, pp.\u00a0121\u2013130. ACM Press, New York (2012)"},{"key":"9093_CR25","first-page":"179","volume-title":"Proceedings of LICS 2009","author":"N. Kobayashi","year":"2009","unstructured":"Kobayashi, N., Ong, C.-H.L.: A\u00a0type system equivalent to the modal mu-calculus model checking of higher-order recursion schemes. In: Proceedings of LICS 2009, pp.\u00a0179\u2013188. IEEE Computer Society Press, Los Alamitos (2009)"},{"key":"9093_CR26","doi-asserted-by":"crossref","unstructured":"Kobayashi, N., Ong, C.-H.L.: Complexity of model checking recursion schemes for fragments of the modal mu-calculus. Logical Methods in Computer Science 7(4) (2011)","DOI":"10.2168\/LMCS-7(4:9)2011"},{"key":"9093_CR27","first-page":"296","volume-title":"Proc. Data Compression Conference\u00a0\u201999 (DCC\u201999)","author":"N.J. Larsson","year":"1999","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Proc. Data Compression Conference\u00a0\u201999 (DCC\u201999), pp.\u00a0296\u2013305. IEEE Computer Society, Los Alamitos (1999)"},{"key":"9093_CR28","first-page":"187","volume-title":"Handbook of Theoretical Computer Science, vol.\u00a0A: Algorithms and Complexity","author":"M. Li","year":"1990","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: Kolmogorov complexity and its applications. In: Handbook of Theoretical Computer Science, vol.\u00a0A: Algorithms and Complexity, pp.\u00a0187\u2013254. MIT Press, Cambridge (1990)"},{"key":"9093_CR29","series-title":"Texts in Computer Science","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"2009","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Texts in Computer Science Springer, Berlin (2009)","edition":"3"},{"key":"9093_CR30","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1109\/DCC.2011.42","volume-title":"Data Compression Conference (DCC 2011)","author":"M. Lohrey","year":"2011","unstructured":"Lohrey, M., Maneth, S., Mennicke, R.: Tree structure compression with repair. In: Data Compression Conference (DCC 2011), pp.\u00a0353\u2013362. IEEE Computer Society, Los Alamitos (2011)"},{"key":"9093_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/978-3-540-24727-2_26","volume-title":"Proceedings of FOSSACS 2004","author":"S. Maneth","year":"2004","unstructured":"Maneth, S., Busatto, G.: Tree transducers and tree compressions. In: Proceedings of FOSSACS 2004. Lecture Notes in Computer Science, vol.\u00a02987, pp.\u00a0363\u2013377. Springer, Berlin (2004)"},{"issue":"8\u201310","key":"9093_CR32","doi-asserted-by":"crossref","first-page":"900","DOI":"10.1016\/j.tcs.2008.12.016","volume":"410","author":"W. Matsubara","year":"2009","unstructured":"Matsubara, W., Inenaga, S., Ishino, A., Shinohara, A., Nakamura, T., Hashimoto, K.: Efficient algorithms to compute compressed longest common substrings and compressed palindromes. Theor. Comput. Sci. 410(8\u201310), 900\u2013913 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2\/3","key":"9093_CR33","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1093\/comjnl\/40.2_and_3.103","volume":"40","author":"C.G. Nevill-Manning","year":"1997","unstructured":"Nevill-Manning, C.G., Witten, I.H.: Compression and explanation using hierarchical grammars. Comput. J. 40(2\/3), 103\u2013116 (1997)","journal-title":"Comput. J."},{"key":"9093_CR34","first-page":"81","volume-title":"LICS 2006","author":"C.-H.L. Ong","year":"2006","unstructured":"Ong, C.-H.L.: On model-checking trees generated by higher-order recursion schemes. In: LICS 2006, pp.\u00a081\u201390. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"9093_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"ESA\u201994","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: ESA\u201994. Lecture Notes in Computer Science, vol.\u00a0855, pp.\u00a0460\u2013470. Springer, Berlin (1994)"},{"issue":"1\u20133","key":"9093_CR36","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 302(1\u20133), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9093_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-540-27836-8_5","volume-title":"ICALP\u201904","author":"W. Rytter","year":"2004","unstructured":"Rytter, W.: Grammar compression, LZ-encodings, and string algorithms with implicit input. In: ICALP\u201904. Lecture Notes in Computer Science, vol.\u00a03142, pp.\u00a015\u201327. Springer, Berlin (2004)"},{"issue":"2\u20134","key":"9093_CR38","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1016\/j.jda.2004.08.016","volume":"3","author":"H. Sakamoto","year":"2005","unstructured":"Sakamoto, H.: A\u00a0fully linear-time approximation algorithm for grammar-based compression. J. Discrete Algorithms 3(2\u20134), 416\u2013430 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"9093_CR39","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1587\/transinf.E92.D.158","volume":"92-D","author":"H. Sakamoto","year":"2009","unstructured":"Sakamoto, H., Maruyama, S., Kida, T., Shimozono, S.: A\u00a0space-saving approximation algorithm for grammar-based compression. IEICE Trans. Inf. Syst. E 92-D(2), 158\u2013165 (2009)","journal-title":"IEICE Trans. Inf. Syst. E"},{"issue":"2","key":"9093_CR40","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1023\/A:1008109312730","volume":"14","author":"H.L. Somers","year":"1999","unstructured":"Somers, H.L.: Review article: example-based machine translation. Mach. Transl. 14(2), 113\u2013157 (1999)","journal-title":"Mach. Transl."},{"key":"9093_CR41","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0304-3975(79)90007-0","volume":"9","author":"R. Statman","year":"1979","unstructured":"Statman, R.: The typed lambda-calculus is not elementary recursive. Theor. Comput. Sci. 9, 73\u201381 (1979)","journal-title":"Theor. Comput. Sci."},{"key":"9093_CR42","doi-asserted-by":"crossref","unstructured":"Stirling, C.: Decidability of higher-order matching. Log. Methods Comput. Sci. 5(3) (2009)","DOI":"10.2168\/LMCS-5(3:2)2009"},{"key":"9093_CR43","unstructured":"Storer, J.: NP-completeness results concerning data compression. Technical Report 234, Department of Electrical Engineering and Computer Science, Princeton University, Princeton, NJ (1997)"},{"key":"9093_CR44","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1145\/224164.224221","volume-title":"Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture, FPCA\u201995","author":"A. Takano","year":"1995","unstructured":"Takano, A., Meijer, E.: Shortcut deforestation in calculational form. In: Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture, FPCA\u201995, pp.\u00a0306\u2013313. ACM, New York (1995)"},{"key":"9093_CR45","series-title":"LIPIcs","first-page":"323","volume-title":"23rd International Conference on Rewriting Techniques and Applications (RTA\u201912)","author":"K. Terui","year":"2012","unstructured":"Terui, K.: Semantic evaluation, intersection types and complexity of simply typed lambda calculus. In: 23rd International Conference on Rewriting Techniques and Applications (RTA\u201912). LIPIcs, vol.\u00a015, pp.\u00a0323\u2013338. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2012)"},{"key":"9093_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/11737414_7","volume-title":"Functional and Logic Programming, 8th International Symposium (FLOPS 2006)","author":"A. Tozawa","year":"2006","unstructured":"Tozawa, A.: XML type checking using high-level tree transducer. In: Functional and Logic Programming, 8th International Symposium (FLOPS 2006). Lecture Notes in Computer Science, vol.\u00a03945, pp.\u00a081\u201396. Springer, Berlin (2006)"},{"key":"9093_CR47","first-page":"237","volume-title":"Randomness and Complexity, from Leibniz to Chaitin","author":"J. Tromp","year":"2008","unstructured":"Tromp, J.: Binary lambda calculus and combinatory logic. In: Claude, C.S. (ed.) Randomness and Complexity, from Leibniz to Chaitin, pp.\u00a0237\u2013260. World Scientific, Singapore (2008)"},{"key":"9093_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/978-3-642-12032-9_24","volume-title":"Proceedings of FOSSACS 2010","author":"T. Tsukada","year":"2010","unstructured":"Tsukada, T., Kobayashi, N.: Untyped recursion schemes and infinite intersection types. In: Proceedings of FOSSACS 2010. Lecture Notes in Computer Science, vol.\u00a06014, pp.\u00a0343\u2013357. Springer, Berlin (2010)"},{"issue":"1","key":"9093_CR49","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0304-3975(92)90297-S","volume":"102","author":"S. Bakel van","year":"1992","unstructured":"van Bakel, S.: Complete restrictions of the intersection type discipline. Theor. Comput. Sci. 102(1), 135\u2013163 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9093_CR50","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0304-3975(95)00073-6","volume":"151","author":"S. Bakel van","year":"1995","unstructured":"van Bakel, S.: Intersection type assignment systems. Theor. Comput. Sci. 151(2), 385\u2013435 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9093_CR51","first-page":"15","volume-title":"Proceedings of ICFP 2010","author":"D. Vytiniotis","year":"2010","unstructured":"Vytiniotis, D., Kennedy, A.: Functional pearl: every bit counts. In: Proceedings of ICFP 2010, pp.\u00a015\u201326 (2010)"}],"container-title":["Higher-Order and Symbolic Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10990-013-9093-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10990-013-9093-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10990-013-9093-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T22:25:02Z","timestamp":1563661502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10990-013-9093-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["9093"],"URL":"https:\/\/doi.org\/10.1007\/s10990-013-9093-z","relation":{},"ISSN":["1388-3690","1573-0557"],"issn-type":[{"value":"1388-3690","type":"print"},{"value":"1573-0557","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}