THE SYNTHESIS PROBLEM OF PETRI NETS

The synthesis problem of concurrent systems is the problem of synthesi zing a concurrent system model from sequential observations. The paper studies the synthesis problem for elementary Petri nets and transitio n systems. A characterization of the class of transition systems which correspond to elementary Petri nets is proven. It is shown how to gen erate all elementary Petri nets corresponding to a given transition sy stem. If there is any such elementary Petri net, it is proven that the re always exists a small one which has only polynomially many elements in the size of the transition system.