---
res:
bibo_abstract:
- "We study algorithmic questions wrt algebraic path properties in concurrent systems,
where the transitions of the system are labeled from a complete, closed semiring.
The algebraic path properties can model dataflow analysis problems, the shortest
path problem, and many other natural problems that arise in program analysis.
We consider that each component of the concurrent system is a graph with constant
treewidth, a property satisfied by the controlflow graphs of most programs. We
allow for multiple possible queries, which arise naturally in demand driven dataflow
analysis. The study of multiple queries allows us to consider the tradeoff between
the resource usage of the one-time preprocessing and for each individual query.
The traditional approach constructs the product graph of all components and applies
the best-known graph algorithm on the product. In this approach, even the answer
to a single query requires the transitive closure (i.e., the results of all possible
queries), which provides no room for tradeoff between preprocessing and query
time.\r\nOur main contributions are algorithms that significantly improve the
worst-case running time of the traditional approach, and provide various tradeoffs
depending on the number of queries. For example, in a concurrent system of two
components, the traditional approach requires hexic time in the worst case for
answering one query as well as computing the transitive closure, whereas we show
that with one-time preprocessing in almost cubic time, each subsequent query can
be answered in at most linear time, and even the transitive closure can be computed
in almost quartic time. Furthermore, we establish conditional optimality results
showing that the worst-case running time of our algorithms cannot be improved
without achieving major breakthroughs in graph algorithms (i.e., improving the
worst-case bound for the shortest path problem in general graphs). Preliminary
experimental results show that our algorithms perform favorably on several benchmarks.\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: 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: 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: 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/3210257
bibo_issue: '3'
bibo_volume: 40
dct_date: 2018^xs_gYear
dct_identifier:
- UT:000444694800001
dct_isPartOf:
- http://id.crossref.org/issn/0164-0925
dct_language: eng
dct_publisher: Association for Computing Machinery (ACM)@
dct_title: Algorithms for algebraic path properties in concurrent systems of constant
treewidth components@
...