The parallel complexity of two problems on concurrency (Q811123)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The parallel complexity of two problems on concurrency |
scientific article |
Statements
The parallel complexity of two problems on concurrency (English)
0 references
1991
0 references
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.
0 references
Trace equivalence
0 references
boolean circuits
0 references
threshold gates
0 references
Petri nets
0 references
partially commutative monoids
0 references
PRAM
0 references
0 references
