For the most recent entries see the Petri Nets Newsletter.

The Parallel Complexity of Two Problems on Concurrency.

Alvarez, C.; Gabarro, J.

In: Information Processing Letters, Vol. 38, No. 2, pages 61-70. April 1991.

Abstract: The authors study the parallel complexity of two problems on concurrency: membership for firing sequences on Petri nets and trace equivalence for partially commutative monoids. Both of them can be solved in constant time by unbounded fan-in circuits with threshold gates. However, they cannot be solved in constant time by a PRAM algorithm.

Keywords: parallel random access memory algorithm; firing sequence; trace equivalence (for) partially commutative monoids; parallel complexity.

Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography