conference paper published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Bernhard Kragl author 320FC952-F248-11E8-B48F-1D18A9856A870000-0001-7745-9117 Samarth Mishra author Andreas Pavlogiannis author 49704004-F248-11E8-B48F-1D18A9856A870000-0002-8943-0722 HongseokYang editor KrCh department ToHe department ESOP: European Symposium on Programming Moderne Concurrency Paradigms project Game Theory project Modern Graph Algorithmic Techniques in Formal Verification project Formal methods for the design and analysis of complex systems project Quantitative Graph Games: Theory and Applications project Pushdown systems (PDSs) and recursive state machines (RSMs), which are linearly equivalent, are standard models for interprocedural analysis. Yet RSMs are more convenient as they (a) explicitly model function calls and returns, and (b) specify many natural parameters for algorithmic analysis, e.g., the number of entries and exits. We consider a general framework where RSM transitions are labeled from a semiring and path properties are algebraic with semiring operations, which can model, e.g., interprocedural reachability and dataflow analysis problems. Our main contributions are new algorithms for several fundamental problems. As compared to a direct translation of RSMs to PDSs and the best-known existing bounds of PDSs, our analysis algorithm improves the complexity for finite-height semirings (that subsumes reachability and standard dataflow properties). We further consider the problem of extracting distance values from the representation structures computed by our algorithm, and give efficient algorithms that distinguish the complexity of a one-time preprocessing from the complexity of each individual query. Another advantage of our algorithm is that our improvements carry over to the concurrent setting, where we improve the bestknown complexity for the context-bounded analysis of concurrent RSMs. Finally, we provide a prototype implementation that gives a significant speed-up on several benchmarks from the SLAM/SDV project. Springer2017Uppsala, Sweden eng 0302-9743 1701.04914 00068170240001110.1007/978-3-662-54434-1_11 10201287 - 313 K. Chatterjee, B. Kragl, S. Mishra, A. Pavlogiannis, in:, H. Yang (Ed.), Springer, 2017, pp. 287–313. Chatterjee, K., Kragl, B., Mishra, S., &#38; Pavlogiannis, A. (2017). Faster algorithms for weighted recursive state machines. In H. Yang (Ed.) (Vol. 10201, pp. 287–313). Presented at the ESOP: European Symposium on Programming, Uppsala, Sweden: Springer. <a href="https://doi.org/10.1007/978-3-662-54434-1_11">https://doi.org/10.1007/978-3-662-54434-1_11</a> Chatterjee K, Kragl B, Mishra S, Pavlogiannis A. Faster algorithms for weighted recursive state machines. In: Yang H, ed. Vol 10201. Springer; 2017:287-313. doi:<a href="https://doi.org/10.1007/978-3-662-54434-1_11">10.1007/978-3-662-54434-1_11</a> Chatterjee, Krishnendu, Bernhard Kragl, Samarth Mishra, and Andreas Pavlogiannis. “Faster Algorithms for Weighted Recursive State Machines.” edited by Hongseok Yang, 10201:287–313. Springer, 2017. <a href="https://doi.org/10.1007/978-3-662-54434-1_11">https://doi.org/10.1007/978-3-662-54434-1_11</a>. K. Chatterjee, B. Kragl, S. Mishra, and A. Pavlogiannis, “Faster algorithms for weighted recursive state machines,” presented at the ESOP: European Symposium on Programming, Uppsala, Sweden, 2017, vol. 10201, pp. 287–313. Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Weighted Recursive State Machines</i>. Edited by Hongseok Yang, vol. 10201, Springer, 2017, pp. 287–313, doi:<a href="https://doi.org/10.1007/978-3-662-54434-1_11">10.1007/978-3-662-54434-1_11</a>. Chatterjee K, Kragl B, Mishra S, Pavlogiannis A. 2017. Faster algorithms for weighted recursive state machines. ESOP: European Symposium on Programming, LNCS, vol. 10201, 287–313. 10112018-12-11T11:49:41Z2025-06-04T08:09:18Z