An equivalence theorem for labeled marked graphs

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 (π)(S), respectively. In this paper, we consider an important special ease of Petri nets, called labeled marked graphs. The main result derived in this paper states that if Γ₁ and Γ₂ are two structurally deterministic labeled marked graphs, then (L)(Γ₁)=L(Γ₂)&rlhar2;π(Γ ₁)=π(Γ₂)