research
∙
04/19/2023
On countings and enumerations of block-parallel automata networks
When we focus on finite dynamical systems from both the computability/co...
share
research
∙
02/09/2023
Hardness of monadic second-order formulae over succinct graphs
Our main result is a succinct counterpoint to Courcelle's meta-theorem a...
research
∙
01/05/2023
Interaction graphs of isomorphic automata networks I: complete digraph and minimum in-degree
An automata network with n components over a finite alphabet Q of size q...
research
∙
01/22/2021
Rikudo is NP-complete
Rikudo is a number-placement puzzle, where the player is asked to comple...
research
∙
12/04/2020
Complexity of fixed point counting problems in Boolean Networks
A Boolean network (BN) with n components is a discrete dynamical system ...
research
∙
05/29/2020
Optimising attractor computation in Boolean automata networks
This paper details a method for optimising the size of Boolean automata ...
research
∙
04/05/2020
#P-completeness of counting update digraphs, cacti, and a series-parallel decomposition method
Automata networks are a very general model of interacting entities, with...
research
∙
01/21/2020
Complexity of limit-cycle problems in Boolean networks
Boolean networks are a general model of interacting entities, with appli...
research
∙
10/16/2019
On the complexity of acyclic modules in automata networks
Modules were introduced as an extension of Boolean automata networks. Th...
research
∙
09/26/2019
How hard is it to predict sandpiles on lattices? A survey
Since their introduction in the 80s, sandpile models have raised interes...
research
∙
09/07/2019
On the complexity of counting feedback arc sets
In this note we study the computational complexity of feedback arc set c...
research
∙
09/06/2019
NP-completeness of the game Kingdomino
Kingdomino is a board game designed by Bruno Cathala and edited by Blue ...
research
∙
03/14/2018
Computational complexity of the avalanche problem on one dimensional Kadanoff sandpiles
In this paper we prove that the general avalanche problem AP is in NC, f...
research
∙
03/14/2018
Linearity is Strictly More Powerful than Contiguity for Encoding Graphs
Linearity and contiguity are two parameters devoted to graph encoding. L...
research
∙
02/28/2018