Extracting reaction systems from function behavior
Tóm tắt
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.
Tài liệu tham khảo
Azimi, S., Gratie, C., Ivanov, S., Manzoni, L., Petre, I., & Porreca, A. E. (2016). Complexity of model checking for reaction systems. Theoretical Computer Science, 623, 103–113. https://doi.org/10.1016/j.tcs.2015.11.040.
Barbuti, R., Gori, R., Levi, F., & Milazzo, P. (2016). Investigating dynamic causalities in reaction systems. Theoretical Computer Science, 623, 114–145. https://doi.org/10.1016/j.tcs.2015.11.041.
Brayton, R. K., Hachtel, G. D., McMullen, C. T., & Sangiovanni-Vincentelli, A. L. (1984). Logic minimization algorithms for VLSI synthesis. Amsterdam: Kluwer Academic Publishers.
Brijder, R., Ehrenfeucht, A., Main, M., & Rozenberg, G. (2011). A tour of reaction systems. International Journal of Foundations of Computer Science, 22, 1499–1517. https://doi.org/10.1142/S0129054111008842.
Corolli, L., Maja, C., Marini, F., Besozzi, D., & Mauri, G. (2012). An excursion in reaction systems: From computer science to biology. Theoretical Computer Science, 454, 95–108. https://doi.org/10.1016/j.tcs.2012.04.003.
Ehrenfeucht, A., & Rozenberg, G. (2007). Reaction systems. Fundamenta Informaticae, 75, 263–280.
Ehrenfeucht, A., Kleijn, J., Koutny, M., & Rozenberg, G. (2017). Evolving reaction systems. Theoretical Computer Science, 682, 79–99. https://doi.org/10.1016/j.tcs.2016.12.031.
Ehrenfeucht, A., Kleijn, J., Koutny, M., & Rozenberg, G. (2012). Minimal reaction systems. In: C. Priami, I. Petre, E. de Vink (eds) Transactions on Computational Systems Biology XIV. Lecture Notes in Computer Science, 7625, 102–122 https://doi.org/10.1007/978-3-642-35524-0_5
Genova, D., Hoogeboom, H. J., & Jonoska, N. (2017). A graph isomorphism condition and equivalence of reaction systems. Theoretical Computer Science, 701, 109–119. https://doi.org/10.1016/j.tcs.2017.05.019.
Gurunath, B., & Biswas, N.N. (1989) An algorithm for multiple output minimization. IEEE Trans. on CAD of Integrated Circuits and Systems 8, 1007–1013. https://doi.org/10.1109/43.35553
Karnaugh, M. (1953). The map method for synthesis of combinational logic circuits. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 72, 593–599. https://doi.org/10.1109/TCE.1953.6371932.
Kleijn, J., Koutny, M., & Mikulski, Ł. (2020). Reaction systems and enabling equivalence. Fundamenta Informaticae, 171, 261–277. https://doi.org/10.3233/FI-2020-1882.
McCluskey, E. J, Jr. (1956). Minimization of Boolean functions. Bell System Technical Journal, 35, 1417–1444. https://doi.org/10.1002/j.1538-7305.1956.tb03835.
Meyer, A.R., & Stockmeyer, L.J. (1972). The equivalence problem for regular expressions with squaring requires exponential space. Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, 125–129. https://doi.org/10.1109/SWAT.1972.29
Rudell, R.L., & Sangiovanni-Vincentelli, A.L. (1987). Multiple-valued minimization for PLA optimization. IEEE Trans. on CAD of Integrated Circuits and Systems 6, 727–750. https://doi.org/10.1109/TCAD.1987.1270318
Rudell, R., Sangiovanni-Vincentelli, A. (2003). Exact minimization of multiple-valued functions for PLA optimization. In: Kuehlmann A. (eds) The Best of ICCAD. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-0292-0_16
Salomaa, A. (2013). Minimal and almost minimal reaction systems. Natural Computing, 12, 369–376. https://doi.org/10.1007/s11047-013-9372-y.
Salomaa, A. (2012). On state sequences defined by reaction systems. Kozen Festschrift, Lecture Notes in Computer Science 7230, 271–282. https://doi.org/10.1007/978-3-642-29485-3_17.
Umans, C. (2001). The minimum equivalent DNF problem and shortest implicants. Journal of Computer and System Sciences, 63, 597–611. https://doi.org/10.1006/jcss.2001.1775.