{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T07:42:36Z","timestamp":1770277356225,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662544334","type":"print"},{"value":"9783662544341","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-662-54434-1_11","type":"book-chapter","created":{"date-parts":[[2017,3,18]],"date-time":"2017-03-18T04:20:06Z","timestamp":1489810806000},"page":"287-313","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Faster Algorithms for Weighted Recursive State Machines"],"prefix":"10.1007","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard","family":"Kragl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samarth","family":"Mishra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Pavlogiannis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,19]]},"reference":[{"key":"11_CR1","unstructured":"jMoped 2.0. https:\/\/www7.in.tum.de\/tools\/jmoped\/"},{"key":"11_CR2","unstructured":"Moped. http:\/\/www2.informatik.uni-stuttgart.de\/fmi\/szs\/tools\/moped\/"},{"key":"11_CR3","unstructured":"WALi. https:\/\/research.cs.wisc.edu\/wpis\/wpds\/"},{"issue":"4","key":"11_CR4","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1145\/1075382.1075387","volume":"27","author":"R Alur","year":"2005","unstructured":"Alur, R., Benedikt, M., Etessami, K., Godefroid, P., Reps, T.W., Yannakakis, M.: Analysis of recursive state machines. ACM Trans. Program. Lang. Syst. 27(4), 786\u2013818 (2005)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"11_CR5","volume-title":"Handbook of Model Checking","author":"R Alur","year":"2016","unstructured":"Alur, R., Bouajjani, A., Esparza, J.: Model checking procedural programs. In: Clarke, E.M., Henzinger, T.A., Veith, H., Bloem, R. (eds.) Handbook of Model Checking. Springer, Heidelberg (2016)"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-14295-6_11","volume-title":"Computer Aided Verification","author":"T Ball","year":"2010","unstructured":"Ball, T., Bounimova, E., Levin, V., Kumar, R., Lichtenberg, J.: The static driver verifier research platform. In: Touili, T., Cook, B., Jackson, P. (eds.) CAV 2010. LNCS, vol. 6174, pp. 119\u2013122. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-14295-6_11"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/10722468_7","volume-title":"SPIN Model Checking and Software Verification","author":"T Ball","year":"2000","unstructured":"Ball, T., Rajamani, S.K.: Bebop: a symbolic model checker for boolean programs. In: Havelund, K., Penix, J., Visser, W. (eds.) SPIN 2000. LNCS, vol. 1885, pp. 113\u2013130. Springer, Heidelberg (2000). doi:10.1007\/10722468_7"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Bhattacharya, P., Iliofotou, M., Neamtiu, I., Faloutsos, M.: Graph-based analysis and prediction for software evolution. In: ICSE (2012)","DOI":"10.1109\/ICSE.2012.6227173"},{"key":"11_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/11590156_28","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"A Bouajjani","year":"2005","unstructured":"Bouajjani, A., Esparza, J., Schwoon, S., Strej\u010dek, J.: Reachability analysis of multithreaded software with asynchronous communication. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol. 3821, pp. 348\u2013359. Springer, Heidelberg (2005). doi:10.1007\/11590156_28"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Callahan, D., Cooper, K.D., Kennedy, K., Torczon, L.: Interprocedural constant propagation. In: CC (1986)","DOI":"10.1145\/12276.13327"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Ibsen-Jensen, R., Pavlogiannis, A., Goyal, P.: Faster algorithms for algebraic path properties in recursive state machines with constant treewidth. In: POPL (2015)","DOI":"10.1145\/2676726.2676979"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Kragl, B., Mishra, S., Pavlogiannis, A.: Faster algorithms for weighted recursive state machines. Technical report arXiv:1701.04914 [cs.PL] (2017)","DOI":"10.1007\/978-3-662-54434-1_11"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Chaudhuri, S.: Subcubic algorithms for recursive state machines. In: POPL (2008)","DOI":"10.1145\/1328438.1328460"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Cousot, P., Cousot, R.: Static determination of dynamic properties of recursive procedures. In: IFIP Conference on Formal Description of Programming Concepts (1977)","DOI":"10.1145\/390017.808314"},{"key":"11_CR15","first-page":"1","volume-title":"GI - 11. Jahrestagung","author":"R Giegerich","year":"1981","unstructured":"Giegerich, R., M\u00f6ncke, U., Wilhelm, R.: Invariance of approximate semantics with respect to program transformations. In: Brauer, W. (ed.) ECI 1981, vol. 50, pp. 1\u201310. Springer, Heidelberg (1981)"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Grove, D., Torczon, L.: Interprocedural constant propagation: a study of jump function implementation. In: PLDI (1993)","DOI":"10.1145\/155090.155099"},{"issue":"4","key":"11_CR17","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1145\/222132.222146","volume":"20","author":"S Horwitz","year":"1995","unstructured":"Horwitz, S., Reps, T., Sagiv, M.: Demand interprocedural dataflow analysis. SIGSOFT Softw. Eng. Notes 20(4), 104\u2013115 (1995)","journal-title":"SIGSOFT Softw. Eng. Notes"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/3-540-55984-1_13","volume-title":"Compiler Construction","author":"J Knoop","year":"1992","unstructured":"Knoop, J., Steffen, B.: The interprocedural coincidence theorem. In: Kastens, U., Pfahler, P. (eds.) CC 1992. LNCS, vol. 641, pp. 125\u2013140. Springer, Heidelberg (1992). doi:10.1007\/3-540-55984-1_13"},{"issue":"3","key":"11_CR19","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/229542.229545","volume":"18","author":"J Knoop","year":"1996","unstructured":"Knoop, J., Steffen, B., Vollmer, J.: Parallelism for free: efficient and optimal bitvector analyses for parallel programs. ACM Trans. Program. Lang. Syst. 18(3), 268\u2013299 (1996)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"11_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-540-69166-2_7","volume-title":"Static Analysis","author":"A Lal","year":"2008","unstructured":"Lal, A., Reps, T.: Solving multiple dataflow queries using WPDSs. In: Alpuente, M., Vidal, G. (eds.) SAS 2008. LNCS, vol. 5079, pp. 93\u2013109. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-69166-2_7"},{"issue":"1","key":"11_CR21","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s10703-009-0078-9","volume":"35","author":"A Lal","year":"2009","unstructured":"Lal, A., Reps, T.W.: Reducing concurrent analysis under a context bound to sequential analysis. Formal Methods Syst. Des. 35(1), 73\u201397 (2009)","journal-title":"Formal Methods Syst. Des."},{"key":"11_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/11513988_44","volume-title":"Computer Aided Verification","author":"A Lal","year":"2005","unstructured":"Lal, A., Reps, T., Balakrishnan, G.: Extended weighted pushdown systems. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol. 3576, pp. 434\u2013448. Springer, Heidelberg (2005). doi:10.1007\/11513988_44"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-540-78800-3_20","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"A Lal","year":"2008","unstructured":"Lal, A., Touili, T., Kidd, N., Reps, T.: Interprocedural analysis of concurrent programs under a context bound. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 282\u2013298. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-78800-3_20"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Landi, W., Ryder, B.G.: Pointer-induced aliasing: a problem classification. In: POPL (1991)","DOI":"10.1145\/99583.99599"},{"issue":"3","key":"11_CR25","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.ipl.2008.09.028","volume":"109","author":"E Liberty","year":"2009","unstructured":"Liberty, E., Zucker, S.W.: The mailman algorithm: a note on matrix-vector multiplication. Inf. Process. Lett. 109(3), 179\u2013182 (2009)","journal-title":"Inf. Process. Lett."},{"key":"11_CR26","doi-asserted-by":"crossref","unstructured":"Musuvathi, M., Qadeer, S.: Iterative context bounding for systematic testing of multithreaded programs. In: PLDI (2007)","DOI":"10.1145\/1250734.1250785"},{"key":"11_CR27","unstructured":"Musuvathi, M., Qadeer, S., Ball, T., Basler, G., Nainar, P.A., Neamtiu, I.: Finding and reproducing heisenbugs in concurrent programs. In: OSDI (2008)"},{"issue":"2","key":"11_CR28","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1145\/128749.128755","volume":"39","author":"G Myers","year":"1992","unstructured":"Myers, G.: A four russians algorithm for regular expression pattern matching. J. ACM 39(2), 430\u2013448 (1992)","journal-title":"J. ACM"},{"key":"11_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-540-31980-1_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"S Qadeer","year":"2005","unstructured":"Qadeer, S., Rehof, J.: Context-bounded model checking of concurrent software. In: Halbwachs, N., Zuck, L.D. (eds.) TACAS 2005. LNCS, vol. 3440, pp. 93\u2013107. Springer, Heidelberg (2005). doi:10.1007\/978-3-540-31980-1_7"},{"issue":"1","key":"11_CR30","first-page":"1","volume":"40","author":"Q Yu","year":"2015","unstructured":"Yu, Q., Guan, X., Zheng, Q., Liu, T., Zhou, J., Li, J.: Calling network: a new method for modeling software runtime behaviors. ACM SIGSOFT Softw. Eng. Notes 40(1), 1\u20138 (2015)","journal-title":"ACM SIGSOFT Softw. Eng. Notes"},{"issue":"2","key":"11_CR31","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1145\/349214.349241","volume":"22","author":"G Ramalingam","year":"2000","unstructured":"Ramalingam, G.: Context-sensitive synchronization-sensitive analysis is undecidable. ACM Trans. Program. Lang. Syst. 22(2), 416\u2013430 (2000)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"11_CR32","doi-asserted-by":"crossref","unstructured":"Reps, T., Horwitz, S., Sagiv, M.: Precise interprocedural dataflow analysis via graph reachability. In: POPL (1995)","DOI":"10.1145\/199448.199462"},{"key":"11_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-540-77050-3_4","volume-title":"FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science","author":"T Reps","year":"2007","unstructured":"Reps, T., Lal, A., Kidd, N.: Program analysis using weighted pushdown systems. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol. 4855, pp. 23\u201351. Springer, Heidelberg (2007). doi:10.1007\/978-3-540-77050-3_4"},{"issue":"1\u20132","key":"11_CR34","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.scico.2005.02.009","volume":"58","author":"TW Reps","year":"2005","unstructured":"Reps, T.W., Schwoon, S., Jha, S., Melski, D.: Weighted pushdown systems and their application to interprocedural dataflow analysis. Sci. Comput. Program. 58(1\u20132), 206\u2013263 (2005)","journal-title":"Sci. Comput. Program."},{"issue":"1","key":"11_CR35","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(96)00072-2","volume":"167","author":"M Sagiv","year":"1996","unstructured":"Sagiv, M., Reps, T., Horwitz, S.: Precise interprocedural dataflow analysis with applications to constant propagation. Theor. Comput. Sci. 167(1), 131\u2013170 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR36","unstructured":"Schwoon, S.: Model-checking pushdown systems. Ph.D. thesis, Technische Universit\u00e4t M\u00fcnchen (2002)"},{"key":"11_CR37","unstructured":"Williams, R.: Matrix-vector multiplication in sub-quadratic time (some preprocessing required). In: SODA (2007)"},{"key":"11_CR38","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: STOC (2012)","DOI":"10.1145\/2213977.2214056"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-54434-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T15:46:59Z","timestamp":1635263219000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-54434-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783662544334","9783662544341"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-54434-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"19 March 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ESOP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Symposium on Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Uppsala","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sweden","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 April 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 April 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"esop2017a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.etaps.org\/index.php\/2017\/esop","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}