Intrinsic Universality of Causal Graph Dynamics

Autor: Simon Martiel, Bruno Martin
Přispěvatelé: Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe MC3, Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), John Templeton Foundation, grant ID 15619, EPTCS, ANR-09-BLAN-0164,EMC,Emergence dans les modèles de calcul(2009)
Jazyk: angličtina
Rok vydání: 2013
Předmět:
FOS: Computer and information sciences
Vertex (graph theory)
B.6.1
Discrete Mathematics (cs.DM)
Computation
Intrinsic Simulation
0102 computer and information sciences
02 engineering and technology
Translation (geometry)
Causal Graph Dynamics
01 natural sciences
Universality
lcsh:QA75.5-76.95
Causality (physics)
[INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]
0202 electrical engineering
electronic engineering
information engineering
F.1.1
F.4.2
Invariant (mathematics)
Discrete mathematics
Structure (mathematical logic)
Generalized Cayley Graphs
lcsh:Mathematics
Universality (philosophy)
16. Peace & justice
lcsh:QA1-939
Computer Science - Distributed
Parallel
and Cluster Computing
010201 computation theory & mathematics
Intrinsic Universality
Homogeneous space
020201 artificial intelligence & image processing
Distributed
Parallel
and Cluster Computing (cs.DC)
lcsh:Electronic computers. Computer science
Parallel graph transformations
Computer Science - Discrete Mathematics
Zdroj: Machines, Computations and Universality
Machines, Computations and Universality, Sep 2013, Zürich, Switzerland. pp.137-149, ⟨10.4204/EPTCS.128.19⟩
Electronic Proceedings in Theoretical Computer Science, Vol 128, Iss Proc. MCU 2013, Pp 137-149 (2013)
MCU
DOI: 10.4204/EPTCS.128.19⟩
Popis: Causal graph dynamics are transformations over graphs that capture two important symmetries of physics, namely causality and homogeneity. They can be equivalently defined as continuous and translation invariant transformations or functions induced by a local rule applied simultaneously on every vertex of the graph. Intrinsic universality is the ability of an instance of a model to simulate every other instance of the model while preserving the structure of the computation at every step of the simulation. In this work we present the construction of a family of intrinsically universal instances of causal graphs dynamics, each instance being able to simulate a subset of instances.
In Proceedings MCU 2013, arXiv:1309.1043
Databáze: OpenAIRE
Externí odkaz: