English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study algorithmic questions for concurrent systems where the transitionsare labeled from a complete, closed semiring, and path properties are algebraicwith semiring operations. The algebraic path properties can model dataflowanalysis problems, the shortest path problem, and many other natural problemsthat arise in program analysis. We consider that each component of theconcurrent system is a graph with constant treewidth, a property satisfied bythe controlflow graphs of most programs. We allow for multiple possiblequeries, which arise naturally in demand driven dataflow analysis. The study ofmultiple queries allows us to consider the tradeoff between the resource usageof the one-time preprocessing and for each individual query. The traditionalapproach constructs the product graph of all components and applies thebest-known graph algorithm on the product. In this approach, even the answer toa single query requires the transitive closure, which provides no room fortradeoff between preprocessing and query time.  Our main contributions are algorithms that significantly improve theworst-case running time of the traditional approach, and provide varioustradeoffs depending on the number of queries. For example, in a concurrentsystem of two components, the traditional approach requires hexic time in theworst case for answering one query as well as computing the transitive closure,whereas we show that with one-time preprocessing in almost cubic time, eachsubsequent query can be answered in at most linear time, and even thetransitive closure can be computed in almost quartic time. Furthermore, weestablish conditional optimality results showing that the worst-case runningtime of our algorithms cannot be improved without achieving major breakthroughsin graph algorithms.

Algorithms for Algebraic Path Properties in Concurrent Systems of Constant Treewidth Components