  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 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, 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 showing that the worst-case running
time of our algorithms cannot be improved without achieving major breakthroughs
in graph algorithms.
