Showing 2026Show all
3 papers · 1 filter
cs.CC2026
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…
cs.CC2026
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…
cs.CC2026
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…