Zobrazeno 1 - 10
of 105
pro vyhledávání: '"Theyssier, Guillaume"'
Autor:
Theyssier, Guillaume
We introduce an extension of classical cellular automata (CA) to arbitrary labeled graphs, and show that FO logic on CA orbits is equivalent to MSO logic. We deduce various results from that equivalence, including a characterization of finitely gener
Externí odkaz:
http://arxiv.org/abs/2404.16430
In majority voting dynamics, a group of $n$ agents in a social network are asked for their preferred candidate in a future election between two possible choices. At each time step, a new poll is taken, and each agent adjusts their vote according to t
Externí odkaz:
http://arxiv.org/abs/2309.01852
Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every arborescent monadic second-order (MSO) property is either NP-hard or coNP-hard over graphs given by succinct representations. Succint representations are Boolean
Externí odkaz:
http://arxiv.org/abs/2302.04522
An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. They are studied both from the dynamical and
Externí odkaz:
http://arxiv.org/abs/2209.09527
Autor:
Theyssier, Guillaume
This tutorial is about cellular automata that exhibit 'cold dynamics'. By this we mean zero entropy, stabilization of all orbits, trivial asymptotic dynamics, etc. These are purely transient irreversible dynamics, but they capture many examples from
Externí odkaz:
http://arxiv.org/abs/2206.08139
Autor:
Nalin, Samuel, Theyssier, Guillaume
This paper is about turedos, which are Turing machine whose head can move in the plane (or in a higher-dimensional space) but only in a selfavoiding way, by putting marks (letters) on visited positions and moving only to unmarked, therefore unvisited
Externí odkaz:
http://arxiv.org/abs/2205.04103
Autor:
Theyssier, Guillaume
This note is a survey of examples and results about cellular automata with the purpose of recalling that there is no 'universal' way of being computationally universal. In particular, we show how some cellular automata can embed efficient but bounded
Externí odkaz:
http://arxiv.org/abs/2112.01090
We study qualitative properties of two-dimensional freezing cellular automata with a binary state set initialized on a random configuration. If the automaton is also monotone, the setting is equivalent to bootstrap percolation. We explore the extent
Externí odkaz:
http://arxiv.org/abs/2110.00656
Publikováno v:
In Theoretical Computer Science 12 November 2024 1016
Publikováno v:
In Advances in Applied Mathematics June 2024 157