6 citations · 11 across the 9 of their papers we have counts for
9 papers
A Linear Acceleration Theorem for 2D Cellular Automata on all Complete Neighborhoods
Anaël Grandjean, Victor Poupet
Linear acceleration theorems are known for most computational models. Although such results have been proved for two-dimensional cellular automata working on specific neighborhoods…
5-State Rotation-Symmetric Number-Conserving Cellular Automata are not Strongly Universal
Katsunobu Imai, Hisamichi Ishizaka, Victor Poupet
We study two-dimensional rotation-symmetric number-conserving cellular automata working on the von Neumann neighborhood (RNCA). It is known that such automata with 4 states or less…
Comparing 1D and 2D Real Time on Cellular Automata
Anaël Grandjean, Victor Poupet
We study the influence of the dimension of cellular automata (CA) for real time language recognition of one-dimensional languages with parallel input. Specifically, we focus on the…
L-Convex Polyominoes are Recognizable in Real Time by 2D Cellular Automata
Anaël Grandjean, Victor Poupet
A polyomino is said to be L-convex if any two of its cells are connected by a 4-connected inner path that changes direction at most once. The 2-dimensional language representing su…
-Limit Sets of Cellular Automata from a Computational Complexity Perspective
Laurent Boyer, Martin Delacourt, Victor Poupet +2
This paper concerns -limit sets of cellular automata: sets of configurations made of words whose probability to appear does not vanish with time, starting from an initial -ra…
A Universal Semi-totalistic Cellular Automaton on Kite and Dart Penrose Tilings
Katsunobu Imai, Takahiro Hatsuda, Victor Poupet +1
In this paper we investigate certain properties of semi-totalistic cellular automata (CA) on the well known quasi-periodic kite and dart two dimensional tiling of the plane present…
Yet another aperiodic tile set
Victor Poupet
We present here an elementary construction of an aperiodic tile set. Although there already exist dozens of examples of aperiodic tile sets we believe this construction introduces…
Directional Dynamics along Arbitrary Curves in Cellular Automata
Martin Delacourt, Victor Poupet, Mathieu Sablik +1
This paper studies directional dynamics in cellular automata, a formalism previously introduced by the third author. The central idea is to study the dynamical behaviour of a cellu…
On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures
Laurent Boyer, Victor Poupet, Guillaume Theyssier
We study the notion of limit sets of cellular automata associated with probability measures (mu-limit sets). This notion was introduced by P. Kurka and A. Maass. It is a refinement…