Abstract
Petri nets and their languages are a useful model of systems exhibiting concurrent behavior. The sequential language associated with a given Petri net S consists of all possible firing sequences of S, where each element of a firing sequence is a single transition. The concurrent language associated with S consists of all possible concurrent firing sequences of S, where each element of a concurrent firing sequence is a set of transitions. The sequential language and the concurrent language associated with S are denoted by (L)(S) and (x)(S), respectively. In this paper, we consider an important special case of Petri nets, called labeled marked graphs. The main result derived in this paper states that if T1 and T2 are two structurally deterministic labeled marked graphs, then (L)(T1 = L(T2) ⇔a(T1) = r(T2). © 1994 IEEE