Liu, Cong; Kondratyev, Alex; Watanabe, Yosinori; Desel, Jörg; Sangiovanni-Vincentelli, Alberto Schedulability analysis of Petri nets based on structural properties. (English) Zbl 1167.68401 Fundam. Inform. 86, No. 3, 325-341 (2008). Summary: A schedule of a Petri Net (PN) represents a set of firing sequences that can be infinitely repeated within a bounded state space, regardless of the outcomes of the nondeterministic choices. Schedulability analysis for a given PN answers the question whether a schedule exists in the reachability space of this net. This paper suggests a novel approach for schedulability analysis based solely on PN structure. It shows that unschedulability can be caused by a structural relation among transitions modelling nondeterministic choices. A method based on linear programming for checking this relation is proposed. This paper also presents a necessary condition for schedulability based on the rank of the incidence matrix of the underlying PN. These results shed a light on the sources of unschedulability often found in PN models of embedded multimedia systems. Cited in 3 Documents MSC: 68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) Keywords:PN structure; incidence matrix PDFBibTeX XMLCite \textit{C. Liu} et al., Fundam. Inform. 86, No. 3, 325--341 (2008; Zbl 1167.68401)