Faster algorithms for weighted recursive state machines Conference Paper

Author(s): Chatterjee, Krishnendu; Kragl, Bernhard; Mishra, Samarth; Pavlogiannis, Andreas
Title: Faster algorithms for weighted recursive state machines
Title Series: LNCS
Affiliation IST Austria
Abstract: 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 best-known 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.
Conference Title: ESOP: European Symposium on Programming
Volume: 10201
Conference Dates: April 22 - 29, 2017
Conference Location: Uppsala, Sweden
ISBN: 978-3-662-54434-1
Publisher: Springer  
Date Published: 2017-03-19
Start Page: 287
End Page: 313
Sponsor: This research was supported in part by the Austrian Science Fund (FWF) under grants S11402-N23, S11407-N23, P23499-N23, and Z211-N23, and by the European Research Council (ERC) under grant 279307.
DOI: 10.1007/978-3-662-54434-1_11
Open access: yes (repository)
IST Austria Authors
  1. Bernhard Kragl
    5 Kragl