{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T21:06:27Z","timestamp":1776373587676,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662466681","type":"print"},{"value":"9783662466698","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46669-8_6","type":"book-chapter","created":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T18:37:37Z","timestamp":1427913457000},"page":"132-157","source":"Crossref","is-referenced-by-count":44,"title":["Automatic Static Cost Analysis for Parallel Programs"],"prefix":"10.1007","author":[{"given":"Jan","family":"Hoffmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhong","family":"Shao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"Vasconcelos, P.: Space Cost Analysis Using Sized Types. PhD thesis, School of Computer Science, University of St Andrews (2008)"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Danner, N., Paykin, J., Royer, J.S.: A Static Cost Analysis for a Higher-Order Language. In: 7th Workshop on Prog. Languages Meets Prog. Verification (PLPV 2013), pp. 25\u201334 (2013)","DOI":"10.1145\/2428116.2428123"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Hofmann, M., Jost, S.: Static Prediction of Heap Space Usage for First-Order Functional Programs. In: 30th ACM Symp. on Principles of Prog. Langs. (POPL 2003), pp. 185\u2013197 (2003)","DOI":"10.1145\/640128.604148"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Sim\u00f5es, H.R., Vasconcelos, P.B., Florido, M., Jost, S., Hammond, K.: Automatic Amortised Analysis of Dynamic Memory Allocation for Lazy Functional Programs. In: 17th Int. Conf. on Funct. Prog. (ICFP 2012), pp. 165\u2013176 (2012)","DOI":"10.1145\/2364527.2364575"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Gulwani, S., Mehra, K.K., Chilimbi, T.M.: SPEED: Precise and Efficient Static Estimation of Program Computational Complexity. In: 36th ACM Symp. on Principles of Prog. Langs. (POPL 2009), pp. 127\u2013139 (2009)","DOI":"10.1145\/1480881.1480898"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-540-71316-6_12","volume-title":"Programming Languages and Systems","author":"E. Albert","year":"2007","unstructured":"Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D.: Cost Analysis of Java Bytecode. In: De Nicola, R. (ed.) ESOP 2007. LNCS, vol.\u00a04421, pp. 157\u2013172. Springer, Heidelberg (2007)"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Hoffmann, J., Aehlig, K., Hofmann, M.: Multivariate Amortized Resource Analysis. ACM Trans. Program. Lang. Syst. (2012)","DOI":"10.1145\/2362389.2362393"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Brockschmidt, M., Emmes, F., Falke, S., Fuhs, C., Giesl, J.: Alternating Runtime and Size Complexity Analysis of Integer Programs. In: \u00c1brah\u00e1m, E., Havelund, K. (eds.) TACAS 2014. LNCS, vol.\u00a08413, pp. 140\u2013155. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-642-54862-8_10"},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/978-3-319-08867-9_50","volume-title":"Computer Aided Verification","author":"M. Sinn","year":"2014","unstructured":"Sinn, M., Zuleger, F., Veith, H.: A Simple and Scalable Approach to Bound Analysis and Amortized Complexity Analysis. In: Biere, A., Bloem, R. (eds.) CAV 2014. LNCS, vol.\u00a08559, pp. 745\u2013761. Springer, Heidelberg (2014)"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Greiner, J.: A Provable Time and Space Efficient Implementation of NESL. In: 1st Int. Conf. on Funct. Prog. (ICFP 1996), pp. 213\u2013225 (1996)","DOI":"10.1145\/232629.232650"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Blelloch, G.E., Harper, R.: Cache and I\/O Efficent Functional Algorithms. In: 40th ACM Symp. on Principles Prog. Langs. (POPL 2013), pp. 39\u201350 (2013)","DOI":"10.1145\/2480359.2429077"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Harper, R.: Practical Foundations for Programming Languages. Cambridge University Press (2012)","DOI":"10.1017\/CBO9781139342131"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Hoffmann, J., Aehlig, K., Hofmann, M.: Multivariate Amortized Resource Analysis. In: 38th ACM Symp. on Principles of Prog. Langs. (POPL 2011) (2011)","DOI":"10.1145\/1926385.1926427"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1007\/978-3-642-31424-7_64","volume-title":"Computer Aided Verification","author":"J. Hoffmann","year":"2012","unstructured":"Hoffmann, J., Aehlig, K., Hofmann, M.: Resource Aware ML. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol.\u00a07358, pp. 781\u2013786. Springer, Heidelberg (2012)"},{"key":"6_CR15","unstructured":"Blelloch, G.E.: Nesl: A nested data-parallel language (version 3.1). Technical Report CMU-CS-95-170, CMU (1995)"},{"key":"6_CR16","unstructured":"Aehlig, K., Hofmann, M., Hoffmann, J.: RAML Web Site (2010-2014), http:\/\/raml.tcs.ifi.lmu.de"},{"key":"6_CR17","unstructured":"Hoffmann, J., Shao, Z.: Automatic Static Cost Analysis for Parallel Programs. Full Version (2014), http:\/\/cs.yale.edu\/~hoffmann\/papers\/parallelcost2014.pdf"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-37036-6_3","volume-title":"Programming Languages and Systems","author":"A. Chargu\u00e9raud","year":"2013","unstructured":"Chargu\u00e9raud, A.: Pretty-Big-Step Semantics. In: Felleisen, M., Gardner, P. (eds.) ESOP 2013. LNCS, vol.\u00a07792, pp. 41\u201360. Springer, Heidelberg (2013)"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-642-11957-6_16","volume-title":"Programming Languages and Systems","author":"J. Hoffmann","year":"2010","unstructured":"Hoffmann, J., Hofmann, M.: Amortized Resource Analysis with Polynomial Potential. In: Gordon, A.D. (ed.) ESOP 2010. LNCS, vol.\u00a06012, pp. 287\u2013306. Springer, Heidelberg (2010)"},{"key":"6_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-319-07151-0_10","volume-title":"Functional and Logic Programming","author":"J. Hoffmann","year":"2014","unstructured":"Hoffmann, J., Shao, Z.: Type-Based Amortized Resource Analysis with Integers and Arrays. In: Codish, M., Sumii, E. (eds.) FLOPS 2014. LNCS, vol.\u00a08475, pp. 152\u2013168. Springer, Heidelberg (2014)"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-642-17164-2_13","volume-title":"Programming Languages and Systems","author":"J. Hoffmann","year":"2010","unstructured":"Hoffmann, J., Hofmann, M.: Amortized Resource Analysis with Polymorphic Recursion and Partial Big-Step Operational Semantics. In: Ueda, K. (ed.) APLAS 2010. LNCS, vol.\u00a06461, pp. 172\u2013187. Springer, Heidelberg (2010)"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Jost, S., Hammond, K., Loidl, H.W., Hofmann, M.: Static Determination of Quantitative Resource Usage for Higher-Order Programs. In: 37th ACM Symp. on Principles of Prog. Langs. (POPL 2010), pp. 223\u2013236 (2010)","DOI":"10.1145\/1706299.1706327"},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-642-00590-9_14","volume-title":"Programming Languages and Systems","author":"B. Campbell","year":"2009","unstructured":"Campbell, B.: Amortised Memory Analysis using the Depth of Data Structures. In: Castagna, G. (ed.) ESOP 2009. LNCS, vol.\u00a05502, pp. 190\u2013204. Springer, Heidelberg (2009)"},{"key":"6_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/11693024_3","volume-title":"Programming Languages and Systems","author":"M.O. Hofmann","year":"2006","unstructured":"Hofmann, M.O., Jost, S.: Type-Based Amortised Heap-Space Analysis. In: Sestoft, P. (ed.) ESOP 2006. LNCS, vol.\u00a03924, pp. 22\u201337. Springer, Heidelberg (2006)"},{"key":"6_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/978-3-642-37036-6_32","volume-title":"Programming Languages and Systems","author":"M. Hofmann","year":"2013","unstructured":"Hofmann, M., Rodriguez, D.: Automatic Type Inference for Amortised Heap-Space Analysis. In: Felleisen, M., Gardner, P. (eds.) ESOP 2013. LNCS, vol.\u00a07792, pp. 593\u2013613. Springer, Heidelberg (2013)"},{"key":"6_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-642-11957-6_6","volume-title":"Programming Languages and Systems","author":"R. Atkey","year":"2010","unstructured":"Atkey, R.: Amortised Resource Analysis with Separation Logic. In: Gordon, A.D. (ed.) ESOP 2010. LNCS, vol.\u00a06012, pp. 85\u2013103. Springer, Heidelberg (2010)"},{"key":"6_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-540-27861-0_6","volume-title":"Implementation of Functional Languages","author":"P.B. Vasconcelos","year":"2004","unstructured":"Vasconcelos, P.B., Hammond, K.: Inferring Costs for Recursive, Polymorphic and Higher-Order Functional Programs. In: Trinder, P., Michaelson, G.J., Pe\u00f1a, R. (eds.) IFL 2003. LNCS, vol.\u00a03145, pp. 86\u2013101. Springer, Heidelberg (2004)"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Hughes, J., Pareto, L., Sabry, A.: Proving the Correctness of Reactive Systems Using Sized Types. In: 23th ACM Symp. on Principles of Prog. Langs. (POPL 1996), pp. 410\u2013423 (1996)","DOI":"10.1145\/237721.240882"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Lago, U.D., Gaboardi, M.: Linear Dependent Types and Relative Completeness. In: 26th IEEE Symp. on Logic in Computer Science (LICS 2011), pp. 133\u2013142 (2011)","DOI":"10.1109\/LICS.2011.22"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Lago, U.D., Petit, B.: The Geometry of Types. In: 40th ACM Symp. on Principles Prog. Langs. (POPL 2013), pp. 167\u2013178 (2013)","DOI":"10.1145\/2480359.2429090"},{"key":"6_CR31","doi-asserted-by":"crossref","unstructured":"Crary, K., Weirich, S.: Resource Bound Certification. In: 27th ACM Symp. on Principles of Prog. Langs. (POPL 2000), pp. 184\u2013198 (2000)","DOI":"10.1145\/325694.325716"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Danielsson, N.A.: Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures. In: 35th ACM Symp. on Principles Prog. Langs. (POPL 2008), pp. 133\u2013144 (2008)","DOI":"10.1145\/1328438.1328457"},{"issue":"9","key":"6_CR33","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1145\/361002.361016","volume":"18","author":"B. Wegbreit","year":"1975","unstructured":"Wegbreit, B.: Mechanical Program Analysis. Commun. ACM\u00a018(9), 528\u2013539 (1975)","journal-title":"Commun. ACM"},{"key":"6_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-642-33125-1_27","volume-title":"Static Analysis","author":"D.E. Alonso-Blas","year":"2012","unstructured":"Alonso-Blas, D.E., Genaim, S.: On the limits of the classical approach to cost analysis. In: Min\u00e9, A., Schmidt, D. (eds.) SAS 2012. LNCS, vol.\u00a07460, pp. 405\u2013421. Springer, Heidelberg (2012)"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Grobauer, B.: Cost Recurrences for DML Programs. In: 6th Int. Conf. on Funct. Prog. (ICFP 2001), pp. 253\u2013264 (2001)","DOI":"10.1145\/507669.507666"},{"key":"6_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-642-25318-8_19","volume-title":"Programming Languages and Systems","author":"E. Albert","year":"2011","unstructured":"Albert, E., Arenas, P., Genaim, S., G\u00f3mez-Zamalloa, M., Puebla, G.: Cost Analysis of Concurrent OO Programs. In: Yang, H. (ed.) APLAS 2011. LNCS, vol.\u00a07078, pp. 238\u2013254. Springer, Heidelberg (2011)"},{"key":"6_CR37","unstructured":"Zimmermann, W.: Automatic Worst Case Complexity Analysis of Parallel Programs. Technical Report TR-90-066, University of California, Berkeley (1990)"},{"issue":"3","key":"6_CR38","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1002\/cpe.1898","volume":"25","author":"P.W. Trinder","year":"2013","unstructured":"Trinder, P.W., Cole, M.I., Hammond, K., Loidl, H.W., Michaelson, G.: Resource Analyses for Parallel and Distributed Coordination. Concurrency and Computation: Practice and Experience\u00a025(3), 309\u2013348 (2013)","journal-title":"Concurrency and Computation: Practice and Experience"},{"key":"6_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-642-23702-7_22","volume-title":"Static Analysis","author":"F. Zuleger","year":"2011","unstructured":"Zuleger, F., Gulwani, S., Sinn, M., Veith, H.: Bound Analysis of Imperative Programs with the Size-change Abstraction. In: Yahav, E. (ed.) Static Analysis. LNCS, vol.\u00a06887, pp. 280\u2013297. Springer, Heidelberg (2011)"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46669-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T20:24:09Z","timestamp":1747859049000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46669-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662466681","9783662466698"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46669-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}