Distributing Finite Automata Through Petri Net Synthesis

The synthesis problem for Petri nets consists in deciding constructively the existence of a Petri net with sequential state graph isomorphic to a given graph. If events are attached to locations, one may set as an additional requirement that the synthesised net should be distributable; i.e. such that events at different locations have no common input place, whence distributed conflicts are avoided. Distributable nets are easily implemented by finite families of automata (one per location) communicating with each other by asynchronous message passing. We show that the general Petri net synthesis problem and its distributed version may both be solved in time polynomial in the size of the given graph. We report on some preliminary experiments of Petri net synthesis applied to the distribution of reactive automata using the tool SYNET. Received November 2000 / Accepted in revised form August 2001