{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T06:20:42Z","timestamp":1777702842944,"version":"3.51.4"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2017,5,29]],"date-time":"2017-05-29T00:00:00Z","timestamp":1496016000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:p>It is well-known that cellular automata can be characterized as the set of translation-invariant continuous functions over a compact metric space; this point of view makes it easy to extend their definition from grids to Cayley graphs. Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their relations; to name all vertices relative to an origin; and the fact that they have a well-defined notion of translation. We propose a notion of graphs, which preserves or generalizes these features. Whereas Cayley graphs are very regular, generalized Cayley graphs are arbitrary, although of a bounded degree. We extend cellular automata theory to these arbitrary, bounded degree, time-varying graphs. The obtained notion of cellular automata is stable under composition and under inversion.<\/jats:p>","DOI":"10.1017\/s0960129517000044","type":"journal-article","created":{"date-parts":[[2017,5,29]],"date-time":"2017-05-29T02:56:56Z","timestamp":1496026616000},"page":"340-383","source":"Crossref","is-referenced-by-count":11,"title":["Cellular automata over generalized Cayley graphs"],"prefix":"10.1017","volume":"28","author":[{"given":"PABLO","family":"ARRIGHI","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SIMON","family":"MARTIEL","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VINCENT","family":"NESME","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,5,29]]},"reference":[{"key":"S0960129517000044_ref17","doi-asserted-by":"crossref","unstructured":"Hasslacher B. and Meyer D. A. (June 1998). 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.","DOI":"10.1142\/S0129183198001448"},{"key":"S0960129517000044_ref31","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2015-1248"},{"key":"S0960129517000044_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.physd.2008.03.039"},{"key":"S0960129517000044_ref36","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00215-0"},{"key":"S0960129517000044_ref33","unstructured":"Schumacher B. and Werner R. (2004). Reversible quantum cellular automata. ArXiv pre-print quant-ph\/0405174."},{"key":"S0960129517000044_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/11527800_5"},{"key":"S0960129517000044_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-010-9245-6"},{"key":"S0960129517000044_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/11553090_71"},{"key":"S0960129517000044_ref37","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-2789(02)00601-2"},{"key":"S0960129517000044_ref34","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.12.385"},{"key":"S0960129517000044_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00213-2"},{"key":"S0960129517000044_ref27","first-page":"167","article-title":"Graph relabelling systems: A general overview","volume":"16","author":"M\u00e9tivier","year":"1997","journal-title":"Computers and Artificial Intelligence"},{"key":"S0960129517000044_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90066-3"},{"key":"S0960129517000044_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01284-6_14"},{"key":"S0960129517000044_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87405-8_8"},{"key":"S0960129517000044_ref1","doi-asserted-by":"crossref","unstructured":"Arrighi P. and Dowek G. (2012). Causal graph dynamics. In: Proceedings of ICALP 2012, Warwick, Lecture Notes in Computer Science, vol. 7392, 54\u201366.","DOI":"10.1007\/978-3-642-31585-5_9"},{"key":"S0960129517000044_ref3","first-page":"30","volume-title":"Proceedings 9th International Workshop on Developments in Computational Models","author":"Arrighi","year":"2014"},{"key":"S0960129517000044_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-009-9090-0"},{"key":"S0960129517000044_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23111-2_9"},{"key":"S0960129517000044_ref8","unstructured":"Danos V. , Feret J. , Fontana W. , Harmer R. , Hayman J. , Krivine J. , Thompson-Walsh C. and Winskel G. (2012). Graphs, rewriting and pathway reconstruction for rule-based models. In: FSTTCS 2012-IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, vol. 18, 276\u2013288."},{"key":"S0960129517000044_ref2","doi-asserted-by":"crossref","unstructured":"Arrighi P. , Fargetton R. , Nesme V. and Thierry E. (2011). Applying causality principles to the axiomatization of probabilistic cellular automata. In: Proceedings of CiE 2011, Sofia, Lecture Notes in Computer Science, vol. 6735, 1\u201310.","DOI":"10.1007\/978-3-642-21875-0_1"},{"key":"S0960129517000044_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71998-4_4"},{"key":"S0960129517000044_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691062"},{"key":"S0960129517000044_ref25","doi-asserted-by":"crossref","unstructured":"Martiel S. and Martin B. (2013). Intrinsic universality of causal graph dynamics. In: Neary T. and Cook M. (eds.) Proceedings Machines, Computations and Universality 2013, Z\u00fcrich, Switzerland, 9\/09\/2013\u201311\/09\/2013, Electronic Proceedings in Theoretical Computer Science, vol. 128, Open Publishing Association, 137\u2013149.","DOI":"10.4204\/EPTCS.128.19"},{"key":"S0960129517000044_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0163-9"},{"key":"S0960129517000044_ref40","first-page":"1","volume-title":"Swarm Intelligence: 7th International Conference, ANTS 2010","author":"Von Mammen","year":"2010"},{"key":"S0960129517000044_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(87)90030-4"},{"key":"S0960129517000044_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90068-5"},{"key":"S0960129517000044_ref10","doi-asserted-by":"crossref","unstructured":"D\u00fcrr C. and Santha M. (1996). A decision procedure for unitary linear quantum cellular automata. In: Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, IEEE, 38\u201345.","DOI":"10.1109\/SFCS.1996.548462"},{"key":"S0960129517000044_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011162"},{"key":"S0960129517000044_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14034-1"},{"key":"S0960129517000044_ref32","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2015-1249"},{"key":"S0960129517000044_ref20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.82.046705"},{"key":"S0960129517000044_ref4","unstructured":"Arrighi P. , Nesme V. and Werner R.F. (2008). Quantum cellular automata over finite, unbounded configurations. In: Proceedings of LATA, Lecture Notes in Computer Science, vol. 5196, Springer, 64\u201375."},{"key":"S0960129517000044_ref28","doi-asserted-by":"crossref","unstructured":"Papazian C. and Remila E. (2002). Hyperbolic recognition by graph automata. In: Proceedings of the Automata, Languages and Programming: 29th International Colloquium, ICALP 2002, M\u00e1laga, Spain, vol. 2380, Springer Verlag, 330.","DOI":"10.1007\/3-540-45465-9_29"},{"key":"S0960129517000044_ref19","unstructured":"Kari K. (2011). Cellular Automata, Lecture notes. Available at: http:\/\/users.utu.fi\/jkari\/ca\/."},{"key":"S0960129517000044_ref7","first-page":"73","volume-title":"Random Walks and Geometry. Proceedings of a Workshop at the Erwin Schr\u00f6dinger Institute, Vienna, June 18\u2013July 13, 2001. In collaboration with Klaus Schmidt and Wolfgang Woess. Collected papers","author":"Ceccherini-Silberstein","year":"2004"},{"key":"S0960129517000044_ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02733251"},{"key":"S0960129517000044_ref35","unstructured":"Taentzer G. (1996). Parallel and Distributed Graph Transformation: Formal Description and Application to Communication-Based Systems. PhD thesis, Technische Universitat Berlin."},{"key":"S0960129517000044_ref12","volume-title":"General Topology I","author":"Fedorchuk","year":"1990"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129517000044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T05:52:40Z","timestamp":1569390760000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129517000044\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,29]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["S0960129517000044"],"URL":"https:\/\/doi.org\/10.1017\/s0960129517000044","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,29]]}}}