{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:58:59Z","timestamp":1725551939261},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642122507"},{"type":"electronic","value":"9783642122514"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12251-4_23","type":"book-chapter","created":{"date-parts":[[2010,4,9]],"date-time":"2010-04-09T23:32:42Z","timestamp":1270855962000},"page":"321-336","source":"Crossref","is-referenced-by-count":22,"title":["Automatic Parallelization of Recursive Functions Using Quantifier Elimination"],"prefix":"10.1007","author":[{"given":"Akimasa","family":"Morihata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kiminori","family":"Matsuzaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1145\/178243.178255","volume-title":"Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation","author":"A.L. Fisher","year":"1994","unstructured":"Fisher, A.L., Ghuloum, A.M.: Parallelizing complex scans and reductions. In: Proceedings of the ACM SIGPLAN 1994 Conference on Programming Language Design and Implementation, pp. 135\u2013146. ACM, New York (1994)"},{"key":"23_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-540-30477-7_14","volume-title":"Programming Languages and Systems","author":"D.N. Xu","year":"2004","unstructured":"Xu, D.N., Khoo, S.C., Hu, Z.: Ptype system: A featherweight parallelizability detector. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol.\u00a03302, pp. 197\u2013212. Springer, Heidelberg (2004)"},{"issue":"11","key":"23_CR3","doi-asserted-by":"publisher","first-page":"1206","DOI":"10.1016\/j.jsc.2005.09.012","volume":"41","author":"A. Gr\u00f6\u00dflinger","year":"2006","unstructured":"Gr\u00f6\u00dflinger, A., Griebl, M., Lengauer, C.: Quantifier elimination in automatic loop parallelization. Journal of Symbolic Computation\u00a041(11), 1206\u20131221 (2006)","journal-title":"Journal of Symbolic Computation"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/1148109.1148116","volume-title":"SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures","author":"K. Matsuzaki","year":"2006","unstructured":"Matsuzaki, K., Hu, Z., Takeichi, M.: Towards automatic parallelization of tree reductions in dynamic programming. In: SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 39\u201348. ACM, New York (2006)"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/1250734.1250752","volume-title":"Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation","author":"K. Morita","year":"2007","unstructured":"Morita, K., Morihata, A., Matsuzaki, K., Hu, Z., Takeichi, M.: Automatic inversion generates divide-and-conquer parallel programs. In: Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation, pp. 146\u2013155. ACM, New York (2007)"},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/1542476.1542496","volume-title":"Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"G. Tournavitis","year":"2009","unstructured":"Tournavitis, G., Wang, Z., Franke, B., O\u2019Boyle, M.F.P.: Towards a holistic approach to auto-parallelization: integrating profile-driven parallelism detection and machine-learning based mapping. In: Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 177\u2013187. ACM, New York (2009)"},{"key":"23_CR7","volume-title":"Compilers: Principles, Techniques, and Tools","author":"A.V. Aho","year":"2006","unstructured":"Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, 2nd edn. Addison-Wesley, Reading (2006)","edition":"2"},{"volume-title":"Quantifier Elimination and Cylindrical Algebraic Decomposition","year":"1998","key":"23_CR8","unstructured":"Caviness, B.F., Johnson, J.R. (eds.): Quantifier Elimination and Cylindrical Algebraic Decomposition. Springer, Heidelberg (1998)"},{"volume-title":"Haskell 1998 Language and Libraries: The Revised Report","year":"2003","key":"23_CR9","unstructured":"Peyton Jones, S. (ed.): Haskell 1998 Language and Libraries: The Revised Report. Cambridge University Press, Cambridge (2003)"},{"issue":"5","key":"23_CR10","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1093\/comjnl\/36.5.450","volume":"36","author":"R. Loos","year":"1993","unstructured":"Loos, R., Weispfenning, V.: Applying linear quantifier elimination. Comput. J.\u00a036(5), 450\u2013462 (1993)","journal-title":"Comput. J."},{"key":"23_CR11","first-page":"153","volume-title":"Proceedings of the 1998 International Conference on Computer Languages","author":"W.N. Chin","year":"1998","unstructured":"Chin, W.N., Takano, A., Hu, Z.: Parallelization via context preservation. In: Proceedings of the 1998 International Conference on Computer Languages, pp. 153\u2013162. IEEE Computer Society, Los Alamitos (1998)"},{"key":"23_CR12","first-page":"314","volume-title":"Conference Record of FPCA 1995 SIGPLAN-SIGARCH-WG2.8 Conference on Functional Programming Languages and Computer Architecture","author":"J. Launchbury","year":"1995","unstructured":"Launchbury, J., Sheard, T.: Warm fusion: Deriving build-cata\u2019s from recursive definitions. In: Conference Record of FPCA 1995 SIGPLAN-SIGARCH-WG2.8 Conference on Functional Programming Languages and Computer Architecture, pp. 314\u2013323. ACM, New York (1995)"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/232627.232637","volume-title":"Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming","author":"Z. Hu","year":"1996","unstructured":"Hu, Z., Iwasaki, H., Takeichi, M.: Deriving structural hylomorphisms from recursive definitions. In: Proceedings of the 1996 ACM SIGPLAN International Conference on Functional Programming, pp. 73\u201382. ACM, New York (1996)"},{"key":"23_CR14","first-page":"489","volume-title":"Parallel Computing: Trends and Applications, PARCO 1993","author":"M. Cole","year":"1994","unstructured":"Cole, M.: Parallel programming, list homomorphisms and the maximum segment sum problem. In: Parallel Computing: Trends and Applications, PARCO 1993, pp. 489\u2013492. Elsevier, Amsterdam (1994)"},{"issue":"2","key":"23_CR15","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K.R. Abrahamson","year":"1989","unstructured":"Abrahamson, K.R., Dadoun, N., Kirkpatrick, D.G., Przytycka, T.M.: A simple parallel tree contraction algorithm. J. Algorithms\u00a010(2), 287\u2013302 (1989)","journal-title":"J. Algorithms"},{"volume-title":"Synthesis of Parallel Algorithms","year":"1993","key":"23_CR16","unstructured":"Reif, J.H. (ed.): Synthesis of Parallel Algorithms. Morgan Kaufmann Publishers, San Francisco (1993)"},{"key":"23_CR17","unstructured":"Morihata, A., Matsuzaki, K.: A tree contraction algorithm on non-binary trees. Technical Report METR 2008-27, Department of Mathematical Informatics, University of Tokyo (2008)"},{"key":"23_CR18","first-page":"85","volume-title":"Proceedings of the 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation","author":"Z. Hu","year":"1999","unstructured":"Hu, Z., Takeichi, M., Iwasaki, H.: Diffusion: Calculating efficient parallel programs. In: Proceedings of the 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pp. 85\u201394. ACM, New York (1999)"},{"key":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1007\/978-3-540-45209-6_108","volume-title":"Euro-Par 2003 Parallel Processing","author":"K. Matsuzaki","year":"2003","unstructured":"Matsuzaki, K., Hu, Z., Takeichi, M.: Parallelization with tree skeletons. In: Kosch, H., B\u00f6sz\u00f6rm\u00e9nyi, L., Hellwagner, H. (eds.) Euro-Par 2003. LNCS, vol.\u00a02790, pp. 789\u2013798. Springer, Heidelberg (2003)"},{"issue":"11","key":"23_CR20","doi-asserted-by":"publisher","first-page":"1526","DOI":"10.1109\/12.42122","volume":"38","author":"G.E. Blelloch","year":"1989","unstructured":"Blelloch, G.E.: Scans as primitive parallel operations. IEEE Trans. Computers\u00a038(11), 1526\u20131538 (1989)","journal-title":"IEEE Trans. Computers"},{"issue":"1","key":"23_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-6423(94)00013-1","volume":"23","author":"J. Gibbons","year":"1994","unstructured":"Gibbons, J., Cai, W., Skillicorn, D.B.: Efficient parallel algorithms for tree accumulations. Science of Computer Programming\u00a023(1), 1\u201318 (1994)","journal-title":"Science of Computer Programming"},{"key":"23_CR22","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1145\/258948.258964","volume-title":"Proceedings of the 2nd ACM SIGPLAN International Conference on Functional Programming","author":"Z. Hu","year":"1997","unstructured":"Hu, Z., Iwasaki, H., Takeichi, M., Takano, A.: Tupling calculation eliminates multiple data traversals. In: Proceedings of the 2nd ACM SIGPLAN International Conference on Functional Programming, pp. 164\u2013175. ACM, New York (1997)"},{"issue":"1-2","key":"23_CR23","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.\u00a069(1-2), 1\u201337 (2006)","journal-title":"Fundam. Inform."},{"issue":"3","key":"23_CR24","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1145\/256167.256201","volume":"19","author":"Z. Hu","year":"1997","unstructured":"Hu, Z., Iwasaki, H., Takechi, M.: Formal derivation of efficient parallel programs by construction of list homomorphisms. ACM Trans. Program. Lang. Syst.\u00a019(3), 444\u2013461 (1997)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"23_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-540-45099-3_5","volume-title":"Static Analysis","author":"W.N. Chin","year":"2000","unstructured":"Chin, W.N., Khoo, S.C., Hu, Z., Takeichi, M.: Deriving parallel codes via invariants. In: Palsberg, J. (ed.) SAS 2000. LNCS, vol.\u00a01824, pp. 75\u201394. Springer, Heidelberg (2000)"},{"key":"23_CR26","first-page":"177","volume-title":"Proceedings of the 36th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages","author":"A. Morihata","year":"2009","unstructured":"Morihata, A., Matsuzaki, K., Hu, Z., Takeichi, M.: The third homomorphism theorem on trees: Downward & upward lead to divide-and-conquer. In: Proceedings of the 36th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 177\u2013185. ACM, New York (2009)"},{"issue":"2","key":"23_CR27","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1006\/jsco.1997.0123","volume":"24","author":"A. Dolzmann","year":"1997","unstructured":"Dolzmann, A., Sturm, T.: Simplification of quantifier-free formulae over ordered fields. J. Symb. Comput.\u00a024(2), 209\u2013231 (1997)","journal-title":"J. Symb. Comput."},{"key":"23_CR28","volume-title":"Using OpenMP: Portable shared memory parallel programming","author":"B. Chapman","year":"2007","unstructured":"Chapman, B., Jost, G., der Pas, R.V.: Using OpenMP: Portable shared memory parallel programming. MIT Press, Cambridge (2007)"},{"key":"23_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BFb0038664","volume-title":"Languages and Compilers for Parallel Computing","author":"D. Callahan","year":"1992","unstructured":"Callahan, D.: Recognizing and parallelizing bounded recurrences. In: Banerjee, U., Nicolau, A., Gelernter, D., Padua, D.A. (eds.) LCPC 1991. LNCS, vol.\u00a0589, pp. 169\u2013185. Springer, Heidelberg (1992)"},{"issue":"4","key":"23_CR30","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1017\/S0956796899003457","volume":"9","author":"S. Nishimura","year":"1999","unstructured":"Nishimura, S., Ohori, A.: Parallel functional programming on recursively defined data via data-parallel recursion. J. Funct. Program.\u00a09(4), 427\u2013462 (1999)","journal-title":"J. Funct. Program."},{"key":"23_CR31","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1145\/309831.309888","volume-title":"Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation","author":"V. Weispfenning","year":"1999","unstructured":"Weispfenning, V.: Mixed real-integer linear quantifier elimination. In: Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, pp. 129\u2013136. ACM, New York (1999)"},{"key":"23_CR32","unstructured":"Sturm, T., Weispfenning, V.: Quantifier elimination in term algebras: The case of finite languages. In: Proceedings of the Fifth International Workshop on Computer Algebra in Scientific Computing, pp. 285\u2013300. Technische Universit\u00e4t M\u00fcnchen (2002)"},{"key":"23_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/978-3-642-02658-4_30","volume-title":"Computer Aided Verification","author":"J.H.R. Jiang","year":"2009","unstructured":"Jiang, J.H.R.: Quantifier elimination via functional composition. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol.\u00a05643, pp. 383\u2013397. Springer, Heidelberg (2009)"},{"key":"23_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/BFb0057920","volume-title":"Euro-Par\u201998 Parallel Processing","author":"G. Keller","year":"1998","unstructured":"Keller, G., Chakravarty, M.M.T.: Flattening trees. In: Pritchard, D., Reeve, J.S. (eds.) Euro-Par 1998. LNCS, vol.\u00a01470, pp. 709\u2013719. Springer, Heidelberg (1998)"}],"container-title":["Lecture Notes in Computer Science","Functional and Logic Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12251-4_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:06:44Z","timestamp":1619784404000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12251-4_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642122507","9783642122514"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12251-4_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}