6 citations · 11 across the 9 of their papers we have counts for
5 papers · 1 filter
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…
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…