5 papers · 1 filter
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…
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…