Earlier Version

Algorithms for algebraic path properties in concurrent systems of constant treewidth components

1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components, IST Austria, 2015.

Download
OA IST-2015-343-v2+1_main.pdf 658.75 KB
Restricted IST-2015-343-v2+2_anonymous.txt
Technical Report | Published | English

Scopus indexed
Author
Anonymous, 1; Anonymous, 2; Anonymous, 3; Anonymous, 4
Series Title
IST Austria Technical Report
Abstract
We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural properties that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, and it is known that the controlflow graphs of most programs have constant treewidth. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis problems (e.g., alias analysis). The study of multiple queries allows us to consider the tradeoff between the resource usage of the \emph{one-time} preprocessing and for \emph{each individual} query. The traditional approaches construct the product graph of all components and apply the best-known graph algorithm on the product. In the traditional approach, even the answer to a single query requires the transitive closure computation (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our 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 that show that the worst-case running times of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (such as improving the worst-case bounds for the shortest path problem in general graphs whose current best-known bound has not been improved in five decades). Finally, we provide a prototype implementation of our algorithms which significantly outperforms the existing algorithmic methods on several benchmarks.
Publishing Year
Date Published
2015-07-14
Page
22
ISSN
IST-REx-ID

Cite this

Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria; 2015.
Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2015). Algorithms for algebraic path properties in concurrent systems of constant treewidth components. IST Austria.
Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015.
1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, Algorithms for algebraic path properties in concurrent systems of constant treewidth components. IST Austria, 2015.
Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2015. Algorithms for algebraic path properties in concurrent systems of constant treewidth components, IST Austria, 22p.
Anonymous, 1, et al. Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components. IST Austria, 2015.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
98fd936102f3e057fc321ef6d316001d
File Name
IST-2015-343-v2+2_anonymous.txt 139 bytes
Access Level
Restricted Closed Access
Date Uploaded
2019-04-16
MD5 Checksum
b31d09b1241b59c75e1f42dadf09d258


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar