Abstract | ||
---|---|---|
We study the parallel complexity of three problems on concurrency: decision of firing sequences for Petri nets, trace equivalence for partially commutative monoids, and strong bisimilarity in finite transition systems. We show that the first two problems can be efficiently parallelized, allowing logarithmic time Parallel RAM algorithms and even constant time unbounded fan-in circuits with threshold gates. However, lower bounds imply that they cannot be solved in constant time by a PRAM algorithm. On the other hand, strong bisimilarity in finite labelled transition systems can be classified as P-complete; as a consequence, algorithms for automated analysis of finite state systems based on bisimulation seem to be inherently sequential in the following sense: the design of an efficient parallel algorithm to solve any of these problems will require an exceedingly hard algorithmic breakthrough. |
Year | DOI | Venue |
---|---|---|
1991 | 10.1007/978-3-662-25209-3_20 | Parallel Architectures and Languages Europe |
Keywords | Field | DocType |
parallel complexity,concurrent system,petri net,parallel algorithm,lower bound | Boolean circuit,Petri net,Commutative property,Parallel algorithm,Concurrency,Computer science,Parallel computing,Theoretical computer science,Equivalence (measure theory),Monoid,Bisimulation | Conference |
Volume | ISBN | Citations |
505 | 3-540-54151-9 | 18 |
PageRank | References | Authors |
1.77 | 15 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Carme Àlvarez | 1 | 316 | 28.75 |
José L. Balcázar | 2 | 701 | 62.06 |
Joaquim Gabarró | 3 | 197 | 28.76 |
Miklós Sántha | 4 | 96 | 7.95 |