On Liveness Enforcing Supervisory Policies for Arbitrary Petri Nets

Chen Chen, Arun Raman, Hesuan Hu, Ramavarapu S. Sreenivas

Research output: Contribution to journalArticlepeer-review

Abstract

Neither the existence nor the nonexistence of a liveness enforcing supervisory policy (LESP) for an arbitrary Petri net (PN) is semidecidable. In an attempt to identify decidable instances, we explore the decidability of certain properties of the set of initial markings for which an LESP exists, and the decidability of the existence of a specific class of LESPs. We first prove that for an arbitrary PN structure, determining if there is an initial marking, or there are no initial markings, for which there is an LESP, is not semidecidable. Then, we characterize the class of PN structures for which the set of all initial markings for which an LESP exists is right-closed. We show that testing membership, or nonmembership, of an arbitrary PN in this class of PNs is not semidecidable. We then consider a restricted class of LESPs, called marking monotone LESPs (MM-LESPs). We show that the existence of an MM-LESP for an arbitrary PN is decidable.

Original languageEnglish (US)
Article number8972386
Pages (from-to)5236-5247
Number of pages12
JournalIEEE Transactions on Automatic Control
Volume65
Issue number12
DOIs
StatePublished - Dec 2020

Keywords

  • Discrete-event dynamic systems (DEDSs)
  • Petri nets (PNs)
  • supervisory control

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'On Liveness Enforcing Supervisory Policies for Arbitrary Petri Nets'. Together they form a unique fingerprint.

Cite this