7 papers
Non-Uniform and Weighted Crossing Gates in Two-Dimensional Sandpiles
Pablo Concha-Vega, Antonin Loubière, Kévin Perrot
Determining whether predicting two-dimensional sandpiles lies in or is -complete has been open for decades. Moore and Nilsson proved -complete…
Complexity of Fungal Automaton Prediction
Enrico Formenti, Eric Goles, Kévin Perrot +2
Fungal automata are a nature-inspired computational model, where a rule is alternatively applied verticaly and horizontaly. In this work we study the computational complexity of pr…
Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
Colin Geniet, Aliénor Goubault-Larrecq, Kévin Perrot
We present a Rice-like complexity lower bound for any MSO-definable problem on binary structures succinctly encoded by circuits. This work extends the framework recently developed…
Solving decision problems by distributed consensus with one-dimensional, binary, radius- cellular automata over cyclic configurations
Eurico Ruivo, Pedro Paulo Balbi, Kévin Perrot +2
Probing the ability of automata networks to solve decision problems has received a continuous attention in the literature, and specially with the automata reaching the answer by di…
Complexity of the Freezing Majority Rule with L-shaped Neighborhoods
Pablo Concha-Vega, Eric Goles, Pedro Montealegre +1
In this article we investigate the computational complexity of predicting two dimensional freezing majority cellular automata with states , where the local interactions…
Timed Prediction Problem for Sandpile Models
Pablo Concha-Vega, Kévin Perrot
We investigate the computational complexity of the timed prediction problem in two-dimensional sandpile models. This question refines the classical prediction problem, which asks w…
Polygonal corona limit on multigrid dual tilings
Victor Lutfalla, Kévin Perrot
The growth pattern of an invasive cell-to-cell propagation (called the successive coronas) on the square grid is a tilted square. On the triangular and hexagonal grids, it is an he…