Reaction Systems and Enabling Equivalence

• Autorzy: Kleijn Jetty , Koutny Maciej , Mikulski Łukasz

Identyfikatory

DOI

10.3233/FI-2020-1882

• Języki publikacji: EN

Abstrakty

EN

Reaction systems were introduced in order to provide an abstract model for the study of the biochemical processes that take place in the living cell. Processes of this kind are the result of the interactions between reactions and may be influenced by the environment. Thus, reaction systems can be considered as a model of (interactive) computation. In previous works, various equivalences defined directly on reaction systems and processes had been proposed and compared. These equivalences were all based on functional equivalence that compares a system’s behaviour at every stage of its execution. In this paper, in contrast, we investigate enabling equivalence which focuses on the system behaviour only in specific stages of its evolution, namely those where all of its reactions are active. We discuss the effect of such an approach and, in particular, its relationship to a transition system representation of the system’s behaviour.

Słowa kluczowe

EN

context-independent process; enabling equivalence; functional equivalence; interactive process; living cell; model of computation; reaction system; transition system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 261--277
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Kleijn Jetty

• LIACS, Leiden University, P.O.Box 9512, NL-2300 RA Leiden, The Netherlands

autor

Koutny Maciej

• School of Computing, Newcastle University, Newcastle upon Tyne NE1 7RU, UK

autor

Mikulski Łukasz

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland

Bibliografia

• [1] Ehrenfeucht A, Rozenberg G. Reaction systems. Fundam. Inform., 2007. 75(1-4):263-280. URL http://content.iospress.com/articles/fundamenta-informaticae/fi75-1-4-15.
• [2] Brijder R, Ehrenfeucht A, Main MG, Rozenberg G. A tour of reaction systems. Int. J. Found. Comput. Sci., 2011. 22(7):1499-1517. doi:10.1142/S0129054111008842.
• [3] Corolli L, Maj C, Marini F, Besozzi D, Mauri G. An excursion in reaction systems: From computer science to biology. Theor. Comput. Sci., 2012. 454:95-108. doi:10.1016/j.tcs.2012.04.003.
• [4] Dennunzio A, Formenti E, Manzoni L. Extremal combinatorics of reaction systems. In: Dediu A, Martín-Vide C, Sierra-Rodríguez JL, Truthe B (eds.), Language and Automata Theory and Applications - 8th International Conference, LATA 2014, Madrid, Spain, March 10-14, 2014. Proceedings, volume 8370 of Lecture Notes in Computer Science. Springer, 2014 pp. 297-307. URL https://doi.org/10.1007/978-3-319-04921-2_24.
• [5] Ehrenfeucht A, Kleijn J, Koutny M, Rozenberg G. Reaction systems: A natural computing approach to the functioning of living cells. In: A Computable Universe: Understanding and Exploring Nature As Computation. World Scientific, 2012 pp. 189-208.
• [6] Dennunzio A, Formenti E, Manzoni L, Porreca AE. Ancestors, descendants, and gardens of Eden in reaction systems. Theor. Comput. Sci., 2015. 608:16-26. doi:10.1016/j.tcs.2015.05.046. URL https://doi.org/10.1016/j.tcs.2015.05.046.
• [7] Ehrenfeucht A, Kleijn J, Koutny M, Rozenberg G. Minimal reaction systems. Trans. Computational Systems Biology, 2012. 14:102-122. doi:10.1007/978-3-642-35524-0_5.
• [8] Ehrenfeucht A, Petre I, Rozenberg G. Reaction systems: A model of computation inspired by the functioning of the living cell. In: The Role of Theory in Computer Science: Essays Dedicated to Janusz Brzozowski. World Scientific, 2017 pp. 1-32. URL https://doi.org/10.1142/9789813148208_0001.
• [9] Ehrenfeucht A, Rozenberg G. Events and modules in reaction systems. Theor. Comput. Sci., 2007. 376(1-2):3-16. doi:10.1016/j.tcs.2007.01.008.
• [10] Ehrenfeucht A, Rozenberg G. Zoom structures and reaction systems yield exploration systems. Int. J. Found. Comput. Sci., 2014. 25(3):275-306. doi:10.1142/S0129054114500142.
• [11] Formenti E, Manzoni L, Porreca AE. Fixed points and attractors of reaction systems. In: Beckmann A, Csuhaj-Varjú E, Meer K (eds.), Language, Life, Limits - 10th Conference on Computability in Europe, CiE 2014, Budapest, Hungary, June 23-27, 2014. Proceedings, volume 8493 of Lecture Notes in Computer Science. Springer, 2014 pp. 194-203. URL https://doi.org/10.1007/978-3-319-08019-2_20.
• [12] Pardini G, Barbuti R, Maggiolo-Schettini A, Milazzo P, Tini S. Compositional semantics and behavioural equivalences for reaction systems with restriction. Theor. Comput. Sci., 2014. 551:1-21. doi:10.1016/j.tcs.2014.04.010.
• [13] Salomaa A. Functions and sequences generated by reaction systems. Theor. Comput. Sci., 2012. 466:87-96. doi:10.1016/j.tcs.2012.07.022.
• [14] Salomaa A. On state sequences defined by reaction systems. In: Constable RL, Silva A (eds.), Logic and Program Semantics - Essays Dedicated to Dexter Kozen on the Occasion of His 60th Birthday, volume 7230 of Lecture Notes in Computer Science. Springer, 2012 pp. 271-282. doi:10.1007/978-3-642-29485-3_17.
• [15] Salomaa A. Minimal and almost minimal reaction systems. Natural Computing, 2013. 12(3):369-376. URL https://doi.org/10.1007/s11047-013-9372-y.
• [16] Kleijn J, Koutny M, Mikulski L, Rozenberg G. Reaction systems, transition systems, and equivalences. In: Böckenhauer H, Komm D, Unger W (eds.), Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday, volume 11011 of Lecture Notes in Computer Science. Springer, 2018 pp. 63-84. doi:10.1007/978-3-319-98355-4_5.
• [17] Ehrenfeucht A, Kleijn J, Koutny M, Rozenberg G. Evolving reaction systems. Theor. Comput. Sci., 2017. 682:79-99. doi:10.1016/j.tcs.2016.12.031.
• [18] Gray F. Pulse code communications, 1953. US Patent 2 632 058.
• [19] Genova D, Hoogeboom HJ, Jonoska N. A graph isomorphism condition and equivalence of reaction systems. Theor. Comput. Sci., 2017. 701:109-119. URL https://doi.org/10.1016/j.tcs.2017.05.019.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).