Direct Product Representation of Labelled Free Choice Nets

Hack’s theorem [7] shows that every live and bounded free choice net is covered by S-components [5, 2]. If the net is labelled, with a distribution of the alphabet into possibly overlapping subalphabets for components, the question arose whether the net can be decomposed into a product of automata, with several possible definitions of product and of equivalence [1, 13, 11, 4]. Zielonka showed [15] that there is a live and 1bounded net which is not direct product representable. We give a straightforward example of a live and 1-bounded labelled free choice net which is not direct product representable, we do not know of any earlier such example. We give two sufficient conditions for 1-bounded labelled free choice nets to be direct product representable. In the other direction, we give two sufficient conditions on products of automata using which we can construct labelled free choice nets. In [14] expressions corresponding to such products has been recently given.