In: Proceedings of the 11th International Conference on Application and Theory of Petri Nets, 1990, Paris, France, pages 284-294. 1990.
Also in: Rozenberg, G.: Lecture Notes in Computer Science, Vol. 524; Advances in Petri Nets 1991, pages 48-57. Berlin, Germany: Springer-Verlag, 1991.
Abstract: By Best and Devillers a semantic for place/transition nets has been defined on equivalence classes of firing sequences induced by the exchange relation (two transitions can be exchanged of they are concurrently enabled). The author shows that the question whether two firing sequences are equivalent is NP-hard and that for a corresponding equivalence relation on processes (or partially ordered multisets) the test of eqivalence remains NP-hard.
Keywords: equivalence complexity (of) transition sequences; exchange relation; net-based semantics; place/transition net; causaltity; net behaviour.