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.