• PDF / 1,958,016 Bytes
• 13 Pages / 595.276 x 790.866 pts Page_size
• 14 Downloads / 219 Views

DOWNLOAD

REPORT

---

REGULAR PAPER

Extracting reaction systems from function behavior Daniela Genova1   · Hendrik Jan Hoogeboom2   · Zornitza Prodanoff3 Received: 27 June 2020 / Accepted: 13 August 2020 © Springer Nature Singapore Pte Ltd. 2020

Abstract Reaction systems, introduced by Ehrenfeucht and Rozenberg, are a theoretical model of computation based on the two main features of biochemical reactions: facilitation and inhibition, which are captured by the individual reactions of the system. All reactions, acting together, determine the global behavior or the result function, res, of the system. In this paper, we study decomposing of a given result function to find a functionally equivalent set of reactions. We propose several approaches, based on identifying reaction systems with Boolean functions, Boolean formulas, and logic circuits. We show how to minimize the number of reactions and their resources for each single output individually, as a group, and when only a subset of the states are considered. These approaches work both when the reactions of the given res function are known and not known. We characterize the minimal number of reactions through the minimal number of logical terms of the Boolean formula representation of the reaction system. Finally, we make applications recommendations for our findings. Keywords  Reaction systems · Boolean functions · Minimization · Boolean formulas · DNF · Prime implicants · Logic synthesis · Logic circuits

1 Introduction Reaction systems were introduced by Ehrenfeucht and Rozenberg in [6], as a theoretical model of computation capturing the two main features of biochemical reactions: facilitation and inhibition. Each reaction system is defined over a finite set of background entities and contains reactions, that are triples of entities: reactants, inhibitors, and products. Reactions act together on each subset (state) of entities, such that, if all of the reactants and none of the inhibitors are present, the reaction is enabled in that state and its products are produced. The products of all reactions enabled in a state form the next state and, in that way, define the result function res . The aggregate behavior of the system, can then be represented by a one-out (exactly one edge * Daniela Genova [email protected] Zornitza Prodanoff [email protected] 1



Department of Mathematics and Statistics, University of North Florida, 32224 Jacksonville, FL, USA

2



LIACS, Leiden University, Leiden, The Netherlands

3

School of Computing, University of North Florida, Jacksonville, FL 32224, USA



goes out of each state (vertex)) graph, called the 0-context graph of the system, [9]. Two reaction systems that exhibit the same aggregate behavior (produce the same 0-context graph) are called functionally equivalent, since their result functions act the same way on every single state. Determining whether two reaction systems are functionally equivalent was proved in [6] to be Co-NP-complete. An extensive list of complexity results for reaction systems is obtained in [1]. Other equivalences of r