Reversible Causal Graph Dynamics

详细信息    查看全文

• 关键词：Bijective ; Invertible ; Cayley graphs ; Hedlund ; Reversible cellular automata
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9720
• 期：1
• 页码：73-88
• 全文大小：460 KB
• 参考文献：1.Arrighi, P., Dowek, G.: Causal graph dynamics. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol. 7392, pp. 54–66. Springer, Heidelberg (2012)CrossRef
  2.Arrighi, P., Martiel, S., Nesme, V., Cayley, G.: Graphs, cellular automata over them submitted (long version) (2013). Pre-print arXiv:​1212.​0027
  3.Arrighi, P., Nesme, V., Werner, R.: Unitarity plus causality implies localizability. J. Comput. Syst. Sci. 77, 372–378 (2010). QIP 2010 (long talk)MathSciNet CrossRef MATH
  4.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, Heidelberg (2015)CrossRef
  5.Boehm, P., Fonio, H.R., Habel, A.: Amalgamation of graph transformations: a synchronization mechanism. J. Comput. Syst. Sci. 34(2–3), 377–408 (1987)MathSciNet CrossRef MATH
  6.Danos, V., Laneve, C.: Formal molecular biology. Theoret. Comput. Sci. 325(1), 69–110 (2004). Computational Systems BiologyMathSciNet CrossRef MATH
  7.Durand-Lose, J.O.: Representing reversible cellular automata with reversible block cellular automata. Discret. Math. Theoret. Comput. Sci. 145, 154 (2001)MathSciNet MATH
  8.Ehrig, H., Lowe, M.: Parallel and distributed derivations in the single-pushout approach. Theoret. Comput. Sci. 109(1–2), 123–143 (1993)MathSciNet CrossRef MATH
  9.Ferrari, G.-L., Hirsch, D., Lanese, I., Montanari, U., Tuosto, E.: Synchronised hyperedge replacement as a model for service oriented computing. In: Boer, F.S., Bonsangue, M.M., Graf, S., Roever, W.-P. (eds.) FMCO 2005. LNCS, vol. 4111, pp. 22–43. Springer, Heidelberg (2006)CrossRef
  10.Gromov, M.: Endomorphisms of symbolic algebraic varieties. J. Eur. Math. Soc. 1(2), 109–197 (1999)MathSciNet CrossRef MATH
  11.Hasslacher, B., Meyer, D.A.: Modelling dynamical geometry with lattice gas automata. In: 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
  12.Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theor. 3, 320–375 (1969)MathSciNet CrossRef MATH
  13.Kari, J.: Reversibility of 2D cellular automata is undecidable. In: Cellular Automata: Theory and Experiment, vol. 45, pp. 379–385. MIT Press (1991)
  14.Kari, J.: Representation of reversible cellular automata with block permutations. Theor. Comput. Syst. 29(1), 47–61 (1996)MathSciNet MATH
  15.Kari, J.: On the circuit depth of structurally reversible cellular automata. Fundamenta Informaticae 38(1–2), 93–107 (1999)MathSciNet MATH
  16.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)MathSciNet CrossRef
  17.Konopka, T., Markopoulou, F., Smolin, L.: Quantum graphity. Arxiv preprint arXiv:​hep-th/​0611197 (2006)
  18.Morita, K.: Reversible simulation of one-dimensional irreversible cellular automata. Theoret. Comput. Sci. 148(1), 157–163 (1995)MathSciNet CrossRef MATH
  19.Sorkin, R.: Time-evolution problem in Regge calculus. Phys. Rev. D. 12(2), 385–396 (1975)MathSciNet CrossRef
  20.Taentzer, G.: Parallel and distributed graph transformation: formal description and application to communication-based systems. Ph.D. thesis, Technische Universitat Berlin (1996)
  21.Taentzer, G.: Parallel high-level replacement systems. Theoret. Comput. Sci. 186(1–2), 43–81 (1997)MathSciNet CrossRef MATH
  22.Tomita, K., Kurokawa, H., Murata, S.: Graph automata: natural expression of self-reproduction. Physica D: Nonlinear Phenom. 171(4), 197–210 (2002)MathSciNet CrossRef MATH
  
• 作者单位：Pablo Arrighi (15)
  Simon Martiel (16)
  Simon Perdrix (17)
  
  15. Aix-Marseille University, LIF, F-13288, Marseille Cedex 9, France
  16. University Nice Sophia Antipolis, I3S, 06900, Sophia Antipolis, France
  17. CNRS, LORIA, Inria Project Team CARTE, University de Lorraine, Nancy, France
  
• 丛书名：Reversible Computation
• ISBN：978-3-319-40578-0
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9720

文摘

Causal Graph Dynamics extend Cellular Automata to arbitrary, bounded-degree, time-varying graphs. The whole graph evolves in discrete time steps, and this global evolution is required to have a number of physics-like symmetries: shift-invariance (it acts everywhere the same) and causality (information has a bounded speed of propagation). We study a further physics-like symmetry, namely reversibility. We extend a fundamental result on reversible cellular automata by proving that the inverse of a causal graph dynamics is a causal graph dynamics. We also address the question of the evolution of the structure of the graphs under reversible causal graph dynamics, showing that any reversible causal graph dynamics preserves the size of all but a finite number of graphs.