Petri nets and regular languages

摘要

It is shown that the regularity problem for firing sequence sets of Petri nets is decidable. For the proof, new techniques to characterize unbounded places are introduced. In the class L0 of terminal languages of labelled Petri nets the regularity problem in undecidable. In addition some lower bounds for the undecidability of the equality problems in L0 and L are given. L0λ is shown to be not closed under complementation without reference to the reachability problem.