Minimizing Cycles in Reaction Systems

Introduced by Ehrenfeucht and Rozenberg, the formal model of reaction systems captures the dynamics of biochemical reactions based on the two main mechanisms of facilitation and inhibition. Functionally equivalent reaction systems evolve through the same result function and various types of minimization of reaction systems have been studied. This paper aims to extend two types of reaction system minimization, rank and degree, to partially-defined RS functions, with a focus on minimizing cycles within reaction systems. We provide bounds on the rank and degree of cycles, as well as computational techniques used to determine when such bounds are strict. Finally, we assign a measure of “complexity” to each family of states via the maximum degree of a cycle over this family. We show this derived measure of complexity satisfies a useful monotonicity condition.