{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:04Z","timestamp":1760202664653},"reference-count":49,"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":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Higher-Order Symb Comput"],"published-print":{"date-parts":[[2012,3]]},"DOI":"10.1007\/s10990-013-9097-8","type":"journal-article","created":{"date-parts":[[2013,9,25]],"date-time":"2013-09-25T01:11:30Z","timestamp":1380071490000},"page":"3-38","source":"Crossref","is-referenced-by-count":8,"title":["Polynomial-time inverse computation for accumulative functions with multiple data traversals"],"prefix":"10.1007","volume":"25","author":[{"given":"Kazutaka","family":"Matsuda","sequence":"first","affiliation":[]},{"given":"Kazuhiro","family":"Inaba","sequence":"additional","affiliation":[]},{"given":"Keisuke","family":"Nakano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,9,25]]},"reference":[{"key":"9097_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/3-540-36377-7_13","volume-title":"The Essence of Computation","author":"S.M. Abramov","year":"2002","unstructured":"Abramov, S.M., Gl\u00fcck, R.: Principles of inverse computation and the universal resolving algorithm. In: Mogensen, T.\u00c6., Schmidt, D.A., Sudborough, I.H. (eds.) The Essence of Computation. Lecture Notes in Computer Science, vol.\u00a02566, pp.\u00a0269\u2013295. Springer, Berlin (2002)"},{"key":"9097_CR2","doi-asserted-by":"crossref","unstructured":"Abramov, S.M., Gl\u00fcck, R., Klimov, Y.A.: An universal resolving algorithm for inverse computation of lazy languages. In: Virbitskaite and Voronkov [46], pp.\u00a027\u201340","DOI":"10.1007\/978-3-540-70881-0_6"},{"issue":"1","key":"9097_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF03037257","volume":"20","author":"E. Albert","year":"2001","unstructured":"Albert, E., Vidal, G.: The narrowing-driven approach to functional logic program specialization. New Gener. Comput. 20(1), 3\u201326 (2001)","journal-title":"New Gener. Comput."},{"issue":"4","key":"9097_CR4","first-page":"776","volume":"47","author":"S. Antoy","year":"2000","unstructured":"Antoy, S., Echahed, R., Hanus, M.: A\u00a0needed narrowing strategy. J.\u00a0ACM 47(4), 776\u2013822 (2000)","journal-title":"J.\u00a0ACM"},{"issue":"1","key":"9097_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/00207168108803261","volume":"10","author":"P.R. Asveld","year":"1981","unstructured":"Asveld, P.R.: Time and space complexity of inside-out macro languages. Int. J. Comput. Math. 10(1), 3\u201314 (1981)","journal-title":"Int. J. Comput. Math."},{"key":"9097_CR6","volume-title":"Introduction to Functional Programming Using Haskell","author":"R. Bird","year":"1998","unstructured":"Bird, R.: Introduction to Functional Programming Using Haskell, 2nd edn. Prentice Hall, New York (1998)","edition":"2"},{"key":"9097_CR7","series-title":"Text, Speech and Language Technology","volume-title":"New Developments in Parsing Technology","author":"P. Boullier","year":"2004","unstructured":"Boullier, P.: Range concatenation grammars. In: Bunt, H., Carroll, J., Satta, G. (eds.) New Developments in Parsing Technology. Text, Speech and Language Technology, vol.\u00a023. Kluwer Academic, Dordrecht (2004). Chap.\u00a013"},{"issue":"1\u20132","key":"9097_CR8","first-page":"1","volume":"69","author":"W.-N. Chin","year":"2006","unstructured":"Chin, W.-N., Khoo, S.-C., Jones, N.: Redundant call elimination via tupling. Fundam. Inform. 69(1\u20132), 1\u201337 (2006)","journal-title":"Fundam. Inform."},{"key":"9097_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1007\/978-3-540-78969-7_23","volume-title":"FLOPS","author":"J. Christiansen","year":"2008","unstructured":"Christiansen, J., Fischer, S.: EasyCheck\u2014test data for free. In: Garrigue, J., Hermenegildo, M.V. (eds.) FLOPS. Lecture Notes in Computer Science, vol.\u00a04989, pp.\u00a0322\u2013336. Springer, Berlin (2008)"},{"key":"9097_CR10","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007). http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"9097_CR11","first-page":"151","volume-title":"MFCS","author":"G. Dowek","year":"1991","unstructured":"Dowek, G.: A\u00a0second-order pattern matching algorithm for the cube of typed lambda-calculi. In: MFCS, pp.\u00a0151\u2013160 (1991)"},{"issue":"1","key":"9097_CR12","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1006\/inco.1999.2807","volume":"154","author":"J. Engelfriet","year":"1999","unstructured":"Engelfriet, J., Maneth, S.: Macro tree transducers, attribute grammars, and MSO definable tree translations. Inf. Comput. 154(1), 34\u201391 (1999)","journal-title":"Inf. Comput."},{"issue":"9","key":"9097_CR13","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/s00236-003-0120-0","volume":"39","author":"J. Engelfriet","year":"2003","unstructured":"Engelfriet, J., Maneth, S.: A\u00a0comparison of pebble tree transducers with macro tree transducers. Acta Inform. 39(9), 613\u2013698 (2003)","journal-title":"Acta Inform."},{"issue":"4","key":"9097_CR14","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1137\/S0097539701394511","volume":"32","author":"J. Engelfriet","year":"2003","unstructured":"Engelfriet, J., Maneth, S.: Macro tree translations of linear size increase are MSO definable. SIAM J. Comput. 32(4), 950\u20131006 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9097_CR15","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0022-0000(85)90066-2","volume":"31","author":"J. Engelfriet","year":"1985","unstructured":"Engelfriet, J., Vogler, H.: Macro tree transducers. J.\u00a0Comput. Syst. Sci. 31(1), 71\u2013146 (1985)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9097_CR16","first-page":"219","volume-title":"IJCAI","author":"D. Eppstein","year":"1985","unstructured":"Eppstein, D.: A\u00a0heuristic approach to program inversion. In: IJCAI, pp.\u00a0219\u2013221 (1985)"},{"key":"9097_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/978-3-540-75987-4_17","volume-title":"DBPL","author":"A. Frisch","year":"2007","unstructured":"Frisch, A., Hosoya, H.: Towards practical typechecking for macro tree transducers. In: Arenas, M., Schwartzbach, M.I. (eds.) DBPL. Lecture Notes in Computer Science, vol.\u00a04797, pp.\u00a0246\u2013260. Springer, Berlin (2007). Full version is available as Research Report, RR-6107, INRIA, 2007"},{"issue":"2","key":"9097_CR18","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-3975(94)90241-0","volume":"134","author":"Z. F\u00fcl\u00f6p","year":"1994","unstructured":"F\u00fcl\u00f6p, Z.: Undecidable properties of deterministic top-down tree transducers. Theor. Comput. Sci. 134(2), 311\u2013328 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9097_CR19","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jlap.2006.11.001","volume":"71","author":"J. Giesl","year":"2007","unstructured":"Giesl, J., K\u00fchnemann, A., Voigtl\u00e4nder, J.: Deaccumulation techniques for improving provability. J.\u00a0Log. Algebr. Program. 71(2), 79\u2013113 (2007)","journal-title":"J.\u00a0Log. Algebr. Program."},{"key":"9097_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/978-3-540-24754-8_21","volume-title":"FLOPS","author":"R. Gl\u00fcck","year":"2004","unstructured":"Gl\u00fcck, R., Kawabe, M.: Derivation of deterministic inverse programs based on LR parsing. In: Kameyama, Y., Stuckey, P.J. (eds.) FLOPS. Lecture Notes in Computer Science, vol.\u00a02998, pp.\u00a0291\u2013306. Springer, Berlin (2004)"},{"issue":"5","key":"9097_CR21","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/1071221.1071222","volume":"40","author":"R. Gl\u00fcck","year":"2005","unstructured":"Gl\u00fcck, R., Kawabe, M.: Revisiting an automatic program inverter for lisp. SIGPLAN Not. 40(5), 8\u201317 (2005)","journal-title":"SIGPLAN Not."},{"key":"9097_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/3-540-58402-1_13","volume-title":"PLILP","author":"R. Gl\u00fcck","year":"1994","unstructured":"Gl\u00fcck, R., S\u00f8rensen, M.H.: Partial deduction and driving are equivalent. In: Hermenegildo, M.V., Penjam, J. (eds.) PLILP. Lecture Notes in Computer Science, vol.\u00a0844, pp.\u00a0165\u2013181. Springer, Berlin (1994)"},{"key":"9097_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-5983-1","volume-title":"The Science of Programming","author":"D. Gries","year":"1981","unstructured":"Gries, D.: The Science of Programming. Springer, Heidelberg (1981). Chap.\u00a021 \u201cInverting programs\u201d"},{"key":"9097_CR24","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"2006","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Prentice Hall, New York (2006). Chap.\u00a07","edition":"3"},{"key":"9097_CR25","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1145\/258948.258964","volume-title":"ICFP","author":"Z. Hu","year":"1997","unstructured":"Hu, Z., Iwasaki, H., Takeichi, M., Takano, A.: Tupling calculation eliminates multiple data traversals. In: ICFP, pp.\u00a0164\u2013175 (1997)"},{"key":"9097_CR26","unstructured":"Huet, G.P.: R\u00e9solution d\u2019\u00e9quations dans les langages d\u2019ordre 1,2,\u2026,\u03c9. PhD thesis, Universit\u00e9 de Paris VII (1976)"},{"key":"9097_CR27","first-page":"31","volume":"11","author":"G.P. Huet","year":"1978","unstructured":"Huet, G.P., Lang, B.: Proving and applying program transformations expressed with second-order patterns. Acta Inform. 11, 31\u201355 (1978)","journal-title":"Acta Inform."},{"key":"9097_CR28","series-title":"LIPIcs","first-page":"244","volume-title":"FSTTCS","author":"K. Inaba","year":"2008","unstructured":"Inaba, K., Maneth, S.: The complexity of tree transducer output languages. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS. LIPIcs, vol.\u00a02, pp.\u00a0244\u2013255. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik (2008)"},{"key":"9097_CR29","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1145\/1480881.1480933","volume-title":"POPL","author":"N. Kobayashi","year":"2009","unstructured":"Kobayashi, N.: Types and higher-order recursion schemes for verification of higher-order programs. In: Shao, Z., Pierce, B.C. (eds.) POPL, pp.\u00a0416\u2013428. ACM, New York (2009)"},{"key":"9097_CR30","first-page":"1007","volume-title":"IJCAI","author":"R.E. Korf","year":"1981","unstructured":"Korf, R.E.: Inversion of applicative programs. In: Hayes, P.J. (ed.) IJCAI, pp.\u00a01007\u20131009. Kaufmann, Los Altos (1981)"},{"key":"9097_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/3-540-45127-7_13","volume-title":"RTA","author":"A. K\u00fchnemann","year":"2001","unstructured":"K\u00fchnemann, A., Gl\u00fcck, R., Kakehi, K.: Relating accumulative and non-accumulative functional programs. In: Middeldorp, A. (ed.) RTA. Lecture Notes in Computer Science, vol.\u00a02051, pp.\u00a0154\u2013168. Springer, Berlin (2001)"},{"key":"9097_CR32","volume-title":"PLAN-X","author":"S. Maneth","year":"2008","unstructured":"Maneth, S., Nakano, K.: XML type checking for macro tree transducers with holes. In: PLAN-X (2008)"},{"key":"9097_CR33","series-title":"Lecture Notes in Computer Science","first-page":"254","volume-title":"ICDT","author":"S. Maneth","year":"2007","unstructured":"Maneth, S., Perst, T., Seidl, H.: Exact XML type checking in polynomial time. In: Schwentick, T., Suciu, D. (eds.) ICDT. Lecture Notes in Computer Science, vol.\u00a04353, pp.\u00a0254\u2013268. Springer, Berlin (2007)"},{"issue":"1","key":"9097_CR34","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.tcs.2004.10.035","volume":"336","author":"W. Martens","year":"2005","unstructured":"Martens, W., Neven, F.: On the complexity of typechecking top-down XML transformations. Theor. Comput. Sci. 336(1), 153\u2013180 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9097_CR35","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/1480945.1480955","volume-title":"PEPM","author":"K. Matsuda","year":"2009","unstructured":"Matsuda, K., Hu, Z., Takeichi, M.: Type-based specialization of XML transformations. In: Puebla, G., Vidal, G. (eds.) PEPM, pp.\u00a061\u201372. ACM, New York (2009)"},{"key":"9097_CR36","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/2103746.2103752","volume-title":"PEPM","author":"K. Matsuda","year":"2012","unstructured":"Matsuda, K., Inaba, K., Nakano, K.: Polynomial-time inverse computation for accumulative functions with multiple data traversals. In: Kiselyov, O., Thompson, S. (eds.) PEPM, pp.\u00a05\u201314. ACM, New York (2012)"},{"key":"9097_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1007\/978-3-642-11957-6_24","volume-title":"ESOP","author":"K. Matsuda","year":"2010","unstructured":"Matsuda, K., Mu, S.-C., Hu, Z., Takeichi, M.: A\u00a0grammar-based approach to invertible programs. In: Gordon, A.D. (ed.) ESOP. Lecture Notes in Computer Science, vol.\u00a06012, pp.\u00a0448\u2013467. Springer, Berlin (2010)"},{"issue":"1","key":"9097_CR38","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/S0022-0000(02)00030-2","volume":"66","author":"T. Milo","year":"2003","unstructured":"Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers. J.\u00a0Comput. Syst. Sci. 66(1), 66\u201397 (2003)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9097_CR39","doi-asserted-by":"crossref","unstructured":"Mogensen, T.\u00c6.: Report on an implementation of a semi-inverter. In: Virbitskaite and Voronkov\u00a0[46], pp.\u00a0322\u2013334","DOI":"10.1007\/978-3-540-70881-0_28"},{"key":"9097_CR40","series-title":"LIPIcs","first-page":"283","volume-title":"RTA","author":"N. Nishida","year":"2011","unstructured":"Nishida, N., Vidal, G.: Program inversion for tail recursive functions. In: Schmidt-Schau\u00df, M. (ed.) RTA. LIPIcs, vol.\u00a010, pp.\u00a0283\u2013298. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik (2011)"},{"issue":"3","key":"9097_CR41","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/j.ipl.2003.05.001","volume":"89","author":"T. Perst","year":"2004","unstructured":"Perst, T., Seidl, H.: Macro forest transducers. Inf. Process. Lett. 89(3), 141\u2013149 (2004)","journal-title":"Inf. Process. Lett."},{"key":"9097_CR42","first-page":"145","volume-title":"FOCS","author":"W.C. Rounds","year":"1973","unstructured":"Rounds, W.C.: Complexity of recognition in intermediate-level languages. In: FOCS, pp.\u00a0145\u2013158. IEEE Press, New York (1973)"},{"key":"9097_CR43","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1145\/1411286.1411292","volume-title":"Haskell","author":"C. Runciman","year":"2008","unstructured":"Runciman, C., Naylor, M., Lindblad, F.: SmallCheck and lazy SmallCheck: automatic exhaustive testing for small values. In: Gill, A. (ed.) Haskell, pp.\u00a037\u201348. ACM, New York (2008)"},{"key":"9097_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1007\/3-540-44881-0_17","volume-title":"RTA","author":"S. Salvati","year":"2003","unstructured":"Salvati, S., de Groote, P.: On the complexity of higher-order matching in the linear lambda-calculus. In: Nieuwenhuis, R. (ed.) RTA. Lecture Notes in Computer Science, vol.\u00a02706, pp.\u00a0234\u2013245. Springer, Berlin (2003)"},{"issue":"3","key":"9097_CR45","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1145\/5956.5957","volume":"8","author":"V.F. Turchin","year":"1986","unstructured":"Turchin, V.F.: The concept of a supercompiler. ACM Trans. Program. Lang. Syst. 8(3), 292\u2013325 (1986)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9097_CR46","series-title":"Lecture Notes in Computer Science","volume-title":"Perspectives of Systems Informatics, 6th International Andrei Ershov Memorial Conference, PSI, Revised Papers","year":"2007","unstructured":"Virbitskaite, I., Voronkov, A. (eds.) Perspectives of Systems Informatics, 6th International Andrei Ershov Memorial Conference, PSI, Revised Papers, Novosibirsk, Russia, June 27\u201330, 2006. Lecture Notes in Computer Science, vol.\u00a04378, Springer, Berlin (2007)"},{"issue":"3","key":"9097_CR47","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1017\/S0956796803004933","volume":"14","author":"J. Voigtl\u00e4nder","year":"2004","unstructured":"Voigtl\u00e4nder, J., K\u00fchnemann, A.: Composition of functions with accumulating parameters. J.\u00a0Funct. Program. 14(3), 317\u2013363 (2004)","journal-title":"J.\u00a0Funct. Program."},{"issue":"2","key":"9097_CR48","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0304-3975(90)90147-A","volume":"73","author":"P. Wadler","year":"1990","unstructured":"Wadler, P.: Deforestation: transforming programs to eliminate trees. Theor. Comput. Sci. 73(2), 231\u2013248 (1990)","journal-title":"Theor. Comput. Sci."},{"key":"9097_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-19072-4","volume-title":"Attribute Grammar Inversion and Source-to-Source Translation","author":"D.M. Yellin","year":"1988","unstructured":"Yellin, D.M.: Attribute Grammar Inversion and Source-to-Source Translation. Lecture Notes in Computer Science, vol.\u00a0302. Springer, Berlin (1988)"}],"container-title":["Higher-Order and Symbolic Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10990-013-9097-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10990-013-9097-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10990-013-9097-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,4]],"date-time":"2023-07-04T20:38:35Z","timestamp":1688503115000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10990-013-9097-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3]]}},"alternative-id":["9097"],"URL":"https:\/\/doi.org\/10.1007\/s10990-013-9097-8","relation":{},"ISSN":["1388-3690","1573-0557"],"issn-type":[{"value":"1388-3690","type":"print"},{"value":"1573-0557","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}