Simulating reversible computation with reaction systems
Tóm tắt
Reaction systems are a formal model of computation providing a framework for investigating biochemical reactions inside living cells. We look at the functioning of these systems as a process producing a series of different possible sets of entities representing states which can be changed by the application of reactions, and we study reversibility and its simulation in this framework. Our goal is to establish an Undo-Redo-Do-like semantics of reversibility with environmental control over the direction of the computation following a so-called no-memory approach, that is, without introducing modifications to the model of reaction systems itself. We first establish requirements the systems must satisfy in order to produce processes consisting of states with unique predecessors, then define reversible reaction systems in terms of reversible interactive processes. For such reversible systems, we also construct simulator systems that can traverse between the states of reversible interactive processes back and forth based on the input of a special “rollback” symbol from the environment.
Tài liệu tham khảo
Agrigoroaiei, O., & Ciobanu, G. (2008) Dual P systems. In: D.W. Corne, P. Frisco, G. Paun, G. Rozenberg, A. Salomaa (eds.) Membrane Computing - 9th International Workshop, WMC 2008, Edinburgh, UK, July 28–31, 2008, Revised Selected and Invited Papers, Lecture Notes in Computer Science, vol. 5391, pp. 95–107. Springer. https://doi.org/10.1007/978-3-540-95885-7_7.
Agrigoroaiei, O., & Ciobanu, G. (2010). Reversing computation in membrane systems. The Journal of Logical and Algebraic Methods in Programming, 79(3–5), 278–288. https://doi.org/10.1016/j.jlap.2010.03.003.
Alhazov, A., Freund, R., & Morita, K. (2012). Sequential and maximally parallel multiset rewriting: Reversibility and determinism. Search Results, 11(1), 95–106. https://doi.org/10.1007/s11047-011-9267-8.
Aman, B., & Ciobanu, G. (2017). Reversibility in parallel rewriting systems. Journal of Universal Computer Science, 23(7), 692–703.
Aman, B., & Ciobanu, G. (2018). Controlled reversibility in reaction systems. In M. Gheorghe, G. Rozenberg, A. Salomaa, & C. Zandron (Eds.), Membrane computing (pp. 40–53). Cham: Springer International Publishing.
Aman, B., Ciobanu, G., Glück, R., Kaarsgaard, R., Kari, J., Kutrib, M., et al. (2020). Foundations of reversible computation (pp. 1–40)., Lecture notes in computer science Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-47361-7_1.
Axelsen, H. B., & Glück, R. (2016). On reversible turing machines and their function universality. Acta Informatica, 53(5), 509–543. https://doi.org/10.1007/s00236-015-0253-y.
Bennett, C. H. (1973). Logical reversibility of computation. IBM Journal of Research and Development, 17(6), 525–532.
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.
Danos, V., & Krivine, J. (2004) Reversible Communicating Systems. In: P. Gardner, N. Yoshida (eds.) CONCUR 2004 - Concurrency Theory, Lecture Notes in Computer Science, pp. 292–307. Springer, Berlin, Heidelberg . https://doi.org/10.1007/978-3-540-28644-8_19.
Danos, V., & Krivine, J. (2005) Transactions in RCCS. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005 - Concurrency Theory, 16th International Conference, CONCUR 2005, San Francisco, CA, USA, August 23-26, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3653, pp. 398–412. Springer . https://doi.org/10.1007/11539452_31.
Ehrenfeucht, A., & Rozenberg, G. (2007). Reaction systems. Fundamenta Informaticae, 75(1–4), 263–280.
Frank, M.P. (2005) Introduction to reversible computing: Motivation, progress, and challenges. In: Proceedings of the 2nd Conference on Computing Frontiers, CF ’05, p. 385–390. Association for Computing Machinery, New York, NY, USA . https://doi.org/10.1145/1062261.1062324.
Holzer, M., & Kutrib, M. (2017) Reversible nondeterministic finite automata. In: I. Phillips, H. Rahaman (eds.) Reversible Computation, pp. 35–51. Springer International Publishing, Cham . https://doi.org/10.1007/978-3-319-59936-6_3.
Ibarra, O. H. (2011). On strong reversibility in P systems and related problems. International Journal of Foundations of Computer Science, 22(1), 7–14. https://doi.org/10.1142/S0129054111007782.
Kari, L., & Rozenberg, G. (2008). The many facets of natural computing. Communications of the ACM, 51, 72–83. https://doi.org/10.1145/1400181.1400200.
Landauer, R. (1961). Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 5(3), 183–191.
Lanese, I., Mezzina, C.A., & Stefani, J.B. (2013) Controlled Reversibility and Compensations. In: R. Glück, T. Yokoyama (eds.) Reversible Computation, Lecture Notes in Computer Science, pp. 233–240. Springer, Berlin, Heidelberg . https://doi.org/10.1007/978-3-642-36315-3_19.
Lanese, I., Mezzina, C. A., & Tiezzi, F. (2014). Causal-consistent reversibility. Bulletin-European Association for Theoretical Computer Science, 114, p. 17.
Lanese, I., & Rawski, M. (eds.) (2020) Reversible Computation: 12th International Conference, RC 2020, Oslo, Norway, July 9-10, 2020, Proceedings. Programming and Software Engineering. Springer International Publishing . https://doi.org/10.1007/978-3-030-52482-1.
Meski, A., Penczek, W., & Rozenberg, G. (2015). Model checking temporal properties of reaction systems. The Journal of Information Science, 313, 22–42. https://doi.org/10.1016/j.ins.2015.03.048.
Morita, K. (2017). Theory of Reversible Computing. Springer, Japan,. https://doi.org/10.1007/978-4-431-56606-9.
Nishida, T.Y. (2009). Reversible p systems with symport/antiport rules. In: G. Paun, M. Pérez-Jiménez, A. Riscos-Núñez (eds.) Proceedings of the 10th Workshop on Membrane Computing, WMC 10, pp. 452–460.
Paun, G. (2000). Computing with membranes. Journal of Computer and System Sciences, 61(1), 108–143. https://doi.org/10.1006/jcss.1999.1693.
Paun, G., Rozenberg, G., & Salomaa, A. (Eds.). (2010). The Oxford handbook of membrane computing. Oxford: Oxford University Press Inc.
Perumalla, K.S. (2013). Introduction to Reversible Computing. Chapman & Hall/CRC. Computational Science Series. Boca Raton: CRC Press.
Phillips, I., Ulidowski, I., & Yuen, S.(2013). A Reversible Process Calculus and the Modelling of the ERK Signalling Pathway. In: R. Glück, T. Yokoyama (eds.) Reversible Computation, Lecture Notes in Computer Science, pp. 218–232. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36315-3_18.
Pinna, M.G. (2018). Reversing steps in membrane systems computations. In: M. Gheorghe, G. Rozenberg, A. Salomaa, C. Zandron (eds.) Membrane Computing, Lecture Notes in Computer Science, pp. 245–261. Springer International Publishing, Cham. https://doi.org/10.1007/978-3-319-73359-3_16.
Rozenberg, G., Bäck, T., & Kok, J. N. (2012). Handbook of natural computing. Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-540-92910-9.
Ulidowski, I., Lanese, I., Schultz, U.P., & Ferreira, C. (eds.): (2020). Reversible Computation: Extending Horizons of Computing - Selected Results of the COST Action IC1405, Lecture Notes in Computer Science, vol. 12070. Springer. https://doi.org/10.1007/978-3-030-47361-7.