6 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…