---
res:
  bibo_abstract:
  - "Interprocedural analysis is at the heart of numerous applications in programming
    languages, such as alias analysis, constant propagation, and so on. Recursive
    state machines (RSMs) are standard models for interprocedural analysis. We consider
    a general framework with RSMs where the transitions are labeled from a semiring
    and path properties are algebraic with semiring operations. RSMs with algebraic
    path properties can model interprocedural dataflow analysis problems, the shortest
    path problem, the most probable path problem, and so on. The traditional algorithms
    for interprocedural analysis focus on path properties where the starting point
    is fixed as the entry point of a specific method. In this work, we consider possible
    multiple queries as required in many applications such as in alias analysis. The
    study of multiple queries allows us to bring in an important algorithmic distinction
    between the resource usage of the one-time preprocessing vs for each individual
    query. The second aspect we consider is that the control flow graphs for most
    programs have constant treewidth.\r\n\r\nOur main contributions are simple and
    implementable algorithms that support multiple queries for algebraic path properties
    for RSMs that have constant treewidth. Our theoretical results show that our algorithms
    have small additional one-time preprocessing but can answer subsequent queries
    significantly faster as compared to the current algorithmic solutions for interprocedural
    dataflow analysis. We have also implemented our algorithms and evaluated their
    performance for performing on-demand interprocedural dataflow analysis on various
    domains, such as for live variable analysis and reaching definitions, on a standard
    benchmark set. Our experimental results align with our theoretical statements
    and show that after a lightweight preprocessing, on-demand queries are answered
    much faster than the standard existing algorithmic approaches.\r\n@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Amir Kafshdar
      foaf_name: Goharshady, Amir Kafshdar
      foaf_surname: Goharshady
      foaf_workInfoHomepage: http://www.librecat.org/personId=391365CE-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-1702-6584
  - foaf_Person:
      foaf_givenName: Prateesh
      foaf_name: Goyal, Prateesh
      foaf_surname: Goyal
  - foaf_Person:
      foaf_givenName: Rasmus
      foaf_name: Ibsen-Jensen, Rasmus
      foaf_surname: Ibsen-Jensen
      foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0003-4783-0389
  - foaf_Person:
      foaf_givenName: Andreas
      foaf_name: Pavlogiannis, Andreas
      foaf_surname: Pavlogiannis
      foaf_workInfoHomepage: http://www.librecat.org/personId=49704004-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-8943-0722
  bibo_doi: 10.1145/3363525
  bibo_issue: '4'
  bibo_volume: 41
  dct_date: 2019^xs_gYear
  dct_identifier:
  - UT:000564108400004
  dct_isPartOf:
  - http://id.crossref.org/issn/0164-0925
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Faster algorithms for dynamic algebraic queries in basic RSMs with constant
    treewidth@
...