Abstract
Consider a network that evolves reversibly, according to nearest neighbours interactions. Can its dynamics create/destroy nodes? On the one hand, since the nodes are the principal carriers of information, it seems that they cannot be destroyed without jeopardising bijectivity. On the other hand, there are plenty of global functions from graphs to graphs that are non-vertex-preserving and bijective. The question has been answered negatively—in three different ways. Yet, in this paper we do obtain reversible local node creation/destruction—in three relaxed settings, whose equivalence we prove for robustness. We motivate our work both by theoretical computer science considerations (reversible computing, cellular automata extensions) and theoretical physics concerns (basic formalisms towards discrete quantum gravity).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arrighi, P., Dowek, G.: Causal graph dynamics. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7392, pp. 54–66. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31585-5_9
Arrighi, P., Nesme, V., Werner, R.: Unitarity plus causality implies localizability. J. Comput. Syst. Sci. 77, 372–378 (2010). QIP 2010 (long talk)
Arrighi, P., Dowek, G.: Causal graph dynamics (long version). Inf. Comput. 223, 78–93 (2013)
Arrighi, P., Durbec, N., Emmanuel, A.: Reversibility vs local creation/destruction. CoRR, abs/1805.10330 (2018). http://arxiv.org/abs/1805.10330
Arrighi, P., Martiel, S.: Quantum causal graph dynamics. Phys. Rev. D 96, 024026 (2017). https://doi.org/10.1103/PhysRevD.96.024026
Arrighi, P., Martiel, S., Nesme, V.: Cellular automata over generalized cayley graphs. Math. Struct. Comput. Sci. 28(3), 340–383 (2018). https://doi.org/10.1017/S0960129517000044
Arrighi, P., Martiel, S., Perdrix, S.: Block representation of reversible causal graph dynamics. In: Kosowski, A., Walukiewicz, I. (eds.) FCT 2015. LNCS, vol. 9210, pp. 351–363. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22177-9_27
Arrighi, P., Martiel, S., Perdrix, S.: Reversible causal graph dynamics. In: Devitt, S., Lanese, I. (eds.) RC 2016. LNCS, vol. 9720, pp. 73–88. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-40578-0_5
Bartholdi, L.: Gardens of Eden and amenability on cellular automata. J. Eur. Math. Soc. 12(1), 241–248 (2010)
Boehm, P., Fonio, H.R., Habel, A.: Amalgamation of graph transformations: a synchronization mechanism. J. Comput. Syst. Sci. 34(2–3), 377–408 (1987)
Chalopin, J., Das, S., Widmayer, P.: Deterministic symmetric rendezvous in arbitrary graphs: overcoming anonymity, failures and uncertainty. In: Alpern, S., Fokkink, R., Gąsieniec, L., Lindelauf, R., Subrahmanian, V. (eds.) Search Theory, pp. 175–195. Springer, Berlin (2013). https://doi.org/10.1007/978-1-4614-6825-7_12
Danos, V., Laneve, C.: Formal molecular biology. Theor. Comput. Sci. 325(1), 69–110 (2004). https://doi.org/10.1016/j.tcs.2004.03.065. http://www.sciencedirect.com/science/article/pii/S0304397504002336. Computational Systems Biology
Durand-Lose, J.O.: Representing reversible cellular automata with reversible block cellular automata. Discrete Math. Theor. Comput. Sci. 145, 154 (2001)
Ehrig, H., Lowe, M.: Parallel and distributed derivations in the single-pushout approach. Theor. Comput. Sci. 109(1–2), 123–143 (1993)
Ceccherini-Silberstein, T., Fiorenzi, F., Scarabotti, F.: The garden of Eden theorem for cellular automata and for symbolic dynamical systems. In: Random Walks and Geometry. Proceedings of a Workshop at the Erwin Schrödinger Institute, Vienna, 18 June–13 July 2001. Collaboration with Klaus Schmidt and Wolfgang Woess. Collected papers, pp. 73–108. de Gruyter, Berlin (2004)
Ganzinger, H. (ed.): RTA 1996. LNCS, vol. 1103. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-61464-8
Gromov, M.: Endomorphisms of symbolic algebraic varieties. J. Eur. Math. Soc. 1(2), 109–197 (1999). https://doi.org/10.1007/pl00011162
Hamma, A., et al.: A quantum Bose-Hubbard model with evolving graph as toy model for emergent spacetime. Arxiv preprint arXiv:0911.5075 (2009)
Hasslacher, B., Meyer, D.A.: Modelling dynamical geometry with lattice gas automata. Expanded Version of a Talk Presented at the Seventh International Conference on the Discrete Simulation of Fluids Held at the University of Oxford, June 1998
Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory 3, 320–375 (1969)
Kari, J.: Reversibility of 2D cellular automata is undecidable. In: Cellular Automata: Theory and Experiment, vol. 45, pp. 379–385. MIT Press (1991)
Kari, J.: Representation of reversible cellular automata with block permutations. Theory Comput. Syst. 29(1), 47–61 (1996)
Kari, J.: On the circuit depth of structurally reversible cellular automata. Fundam. Inf. 38(1–2), 93–107 (1999)
Klales, A., Cianci, D., Needell, Z., Meyer, D.A., Love, P.J.: Lattice gas simulations of dynamical geometry in two dimensions. Phys. Rev. E 82(4), 046705 (2010). https://doi.org/10.1103/PhysRevE.82.046705
Konopka, T., Markopoulou, F., Smolin, L.: Quantum graphity. Arxiv preprint hep-th/0611197 (2006)
Maignan, L., Spicher, A.: Global graph transformations. In: Proceedings of the 6th International Workshop on Graph Computation Models, L’Aquila, Italy, 20 July 2015, pp. 34–49 (2015)
Martiel, S., Martin, B.: Intrinsic universality of causal graph dynamics. In: Neary, T., Cook, M. (eds.) Electronic Proceedings in Theoretical Computer Science, Proceedings, Machines, Computations and Universality 2013, Zürich, Switzerland, 9 September 2013–11 September 2013, vol. 128, pp. 137–149. Open Publishing Association (2013). https://doi.org/10.4204/EPTCS.128.19
Papazian, C., Rémila, E.: Hyperbolic recognition by graph automata. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 330–342. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45465-9_29
Schumacher, B., Werner, R.: Reversible quantum cellular automata. arXiv pre-print quant-ph/0405174 (2004)
Sorkin, R.: Time-evolution problem in Regge calculus. Phys. Rev. D. 12(2), 385–396 (1975)
Taentzer, G.: Parallel high-level replacement systems. Theor. Comput. Sci. 186(1–2), 43–81 (1997)
Tomita, K., Kurokawa, H., Murata, S.: Graph automata: natural expression of self-reproduction. Phys. D: Nonlinear Phenom. 171(4), 197–210 (2002). https://doi.org/10.1016/S0167-2789(02)00601-2. http://www.sciencedirect.com/science/article/pii/S0167278902006012
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Arrighi, P., Durbec, N., Emmanuel, A. (2019). Reversibility vs Local Creation/Destruction. In: Thomsen, M., Soeken, M. (eds) Reversible Computation. RC 2019. Lecture Notes in Computer Science(), vol 11497. Springer, Cham. https://doi.org/10.1007/978-3-030-21500-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-21500-2_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-21499-9
Online ISBN: 978-3-030-21500-2
eBook Packages: Computer ScienceComputer Science (R0)