On minimal representations of Petri net languages

Research output: Contribution to journalArticlepeer-review


Given a measure of size of a labeled Petri net, we consider the existence of a procedure that takes as input a description of an arbitrary, labeled Petri net, and returns a description of a (possibly different) labeled Petri net with the smallest size that generates the same language as the input. We refer to such procedures as minimization procedures. In this note, we investigate the existence of minimization procedures for a variety of measures. We show that these procedures cannot exist for Petri net languages for a large class of measures. However, for families of Petri net languages where controllability (cf. [15]), and consequently language-containment, is decidable [16], there can be minimization procedures for a restricted class of measures. After showing that minimization procedures for a family of measures are intractable for languages generated by bounded Petri nets, it is argued that a similar conclusion has to be reached for any family of Petri net languages that includes the family of regular languages for which there are minimization procedures.

Original languageEnglish (US)
Pages (from-to)799-804
Number of pages6
JournalIEEE Transactions on Automatic Control
Issue number5
StatePublished - May 2006


  • Discrete-event systems
  • Petri nets
  • Supervisory control

ASJC Scopus subject areas

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


Dive into the research topics of 'On minimal representations of Petri net languages'. Together they form a unique fingerprint.

Cite this