Investigating dynamic causalities in reaction systems

Reaction systems are a qualitative formalism for modeling systems of biochemical reactions characterized by the non-permanency of the elements: molecules disappear if not produced by any enabled reaction. Moreover, reaction systems execute in an environment that provides new molecules at each step. Brijder, Ehrenfeucht and Rozenberg investigated dynamic causalities in reaction systems by introducing the idea of predictors. A predictor of a molecule s, for a given n, is the set of molecules to be observed in the environment in order to determine whether s is produced or not by the system at step n. In this paper, we continue the investigation on dynamic causalities by defining an abstract interpretation framework containing three different notions of predictor: Formula based predictors, that is a propositional logic formula that precisely characterizes environments that lead to the production of s after n steps; Multi-step based predictors, that consist of n sets of molecules to be observed in the environment, one for each step; and Set based predictors, that are those proposed by Brijder, Ehrenfeucht and Rozenberg, and consist of a unique set of molecules to be observed in all steps. For each kind of predictor we define an effective operator that allows predictors to be computed for any molecule s and number of steps n. The abstract interpretation framework allows us to compare the three notions of predictor in terms of precision, to relate the three defined operators and to compute minimal predictors. We also discuss a generalization of this approach that allows predictors to be defined independently of the value of n, and a tabling approach for the practical use of predictors on reaction systems models. As an application, we use predictors, generalization and tabling to give theoretical grounds to previously obtained results on a model of gene regulation.