Model reconstruction for discrete deterministic systems

In a previous paper [Torres, L.M. and A.K. Wagler, Encoding the dynamics of deterministic systems, Preprint 09-29, Otto-von-Guericke Universitنt, FMA (2009)] we proposed a compact model for encoding the dynamic behavior of certain discrete deterministic systems based on extending the widely accepted framework of Petri nets. Here, the problem of reconstructing such a model from experimental data obtained by observation of dynamic processes in the system is addressed. This is equivalent to inferring a valid orientation of a certain transition conflict graph. For a special class of systems where the corresponding valid orientations are acyclic, we present a lower bound on the number of experiments required for model reconstruction and show that it is not possible to devise a solution strategy that achieves this bound for every instance.