In: Rozenberg, G.: Lecture Notes in Computer Science, Vol. 483; Advances in Petri Nets 1990, pages 243-286. Berlin: Springer-Verlag, 1991.
Abstract: This invited paper present in a semi-formal illustrative way several new results concerning the analysis and synthesis of free choice systems. It is a complementary work of the survey by E. Best. In the analysis part, the authors characterize liveness and boundedness in linear algebraic terms. As a consequence of the new characterizations, both properties are shown to be decidable (as a whole) in polynomial time. The authors also provide two different kits of sound and complete reduction rules (the one reverse-dual of the other). The authors address then the problem of synthezising live and bounded free choice systems within the two basic design methodologies: top-down and modular (synthesis by composition of modules). Two complete kits of top-down synthesis rules are provided. They are essentially the reduction kits obtained before, but this time considered in the reverse direction
Back to the Petri Nets Bibliography