On minimal representations of Petri net languages

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. ), and consequently language-containment, is decidable , 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.