On commoner's liveness theorem and supervisory policies that enforce liveness in free-choice Petri nets

✍ Scribed by Ramavarapu S. Sreenivas

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 613 KB
• Volume: 31
• Category: Article
• ISSN: 0167-6911
• DOI: 10.1016/s0167-6911(97)00019-4

✦ Synopsis

A Petri net (PN) (Pe::erson, 1981;Reisig, 1985) is said to be live if it is possible to fire any transition from every reachable marking, although not: necessarily immediately. A free-choice Petri net (FCPN) is a PN, where every arc from a place to a transition is either t~e unique output arc from that place or it is the unique input arc to the transition. Commoner's Liveness Theorem (cf. Hack, 1972, Ch. 4; Reisig, 1985, Section 7.2) states that a FCPN is live if and only if every siphon contains a marked trap at the initial marking. A siphon (trap) is a collection of places P such that °P _~ P" (P° _ °P). We concern ourselves with marking-dependent supervisory policies that can prevent the firing of a transition. We characterize supervisory policies that enforce liveness in non-live FCPNs using observations that strongly parallel Commoner's Liveness Theorem. We use this characterization to establish the existence of supervisory policies that enforce liveness in a Class of FCPNs called independent, increasing free-choice petri nets (II-FCPNs).