The parallel complexity of two problems on concurrency
It is shown that unbounded fan-in circuits can solve the following two problems in constant time: The membership problem for firing sequences of Petri nets and the trace equivalence for partially commutative monoids. It is proved in addition that neither problem can be solved in constant time by a PRAM with a polynomial number of processors.
scientific article; zbMATH DE number 4215361
scientific article