9 citations · 12 across the 6 of their papers we have counts for
6 papers
Separating path systems in trees
Francisco Arrepol, Patricio Asenjo, Raúl Astete +6
For a graph , an edge-separating (resp. vertex-separating) path system of is a family of paths in such that for any pair of edges (resp. pair of vertices $v_1…
Nontrivial Turmites are Turing-universal
Diego Maldonado, Anahí Gajardo, Benjamin Hellouin de Menibus +1
A Turmit is a Turing machine that works over a two-dimensional grid, that is, an agent that moves, reads and writes symbols over the cells of the grid. Its state is an arrow and, d…
Pre-Expansivity in Cellular Automata
A. Gajardo, V. Nesme, Guillaume Theyssier
We introduce the property of pre-expansivity for cellular automata (CA): it is the property of being expansive on asymptotic pairs of configurations (i.e. configurations that diffe…
Time-Symmetric Cellular Automata
Andrés Moreira, Anahi Gajardo
Together with the concept of reversibility, another relevant physical notion is time-symmetry, which expresses that there is no way of distinguishing between backward and forward t…
Zigzags in Turing machines
Anahi Gajardo, Pierre Guillon
We study one-head machines through symbolic and topological dynamics. In particular, a subshift is associated to the subshift, and we are interested in its complexity in terms of r…
Complexity of Langton's Ant
Anahi Gajardo, Andres Moreira, Eric Goles
The virtual ant introduced by C. Langton has an interesting behavior, which has been studied in several contexts. Here we give a construction to calculate any boolean circuit with…