Space-time deterministic graph rewriting
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909337989939200 |
|---|---|
| author | Arrighi, Pablo Costes, Marin Dowek, Gilles Maignan, Luidnel |
| author_facet | Arrighi, Pablo Costes, Marin Dowek, Gilles Maignan, Luidnel |
| contents | We study non-terminating graph rewriting models, whose local rules are applied non-deterministically -- and yet enjoy a strong form of determinism, namely space-time determinism. Of course in the case of terminating computation it is well-known that the mess introduced by asynchronous rule applications may not matter to the end result, as confluence conspires to produce a unique normal form. In the context of non-terminating computation however, confluence is a very weak property, and (almost) synchronous rule applications is always preferred e.g. when it comes to simulating dynamical systems. Here we provide sufficient conditions so that asynchronous local rule applications conspire to produce well-determined events in the space-time unfolding of the graph, regardless of their application orders. Our first example is an asynchronous simulation of a dynamical system. Our second example features time dilation, in the spirit of general relativity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_05838 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Space-time deterministic graph rewriting Arrighi, Pablo Costes, Marin Dowek, Gilles Maignan, Luidnel Discrete Mathematics Distributed, Parallel, and Cluster Computing General Relativity and Quantum Cosmology Dynamical Systems Cellular Automata and Lattice Gases We study non-terminating graph rewriting models, whose local rules are applied non-deterministically -- and yet enjoy a strong form of determinism, namely space-time determinism. Of course in the case of terminating computation it is well-known that the mess introduced by asynchronous rule applications may not matter to the end result, as confluence conspires to produce a unique normal form. In the context of non-terminating computation however, confluence is a very weak property, and (almost) synchronous rule applications is always preferred e.g. when it comes to simulating dynamical systems. Here we provide sufficient conditions so that asynchronous local rule applications conspire to produce well-determined events in the space-time unfolding of the graph, regardless of their application orders. Our first example is an asynchronous simulation of a dynamical system. Our second example features time dilation, in the spirit of general relativity. |
| title | Space-time deterministic graph rewriting |
| topic | Discrete Mathematics Distributed, Parallel, and Cluster Computing General Relativity and Quantum Cosmology Dynamical Systems Cellular Automata and Lattice Gases |
| url | https://arxiv.org/abs/2404.05838 |