@article { ,
title = {Simple dynamics on graphs},
abstract = {Can the interaction graph of a finite dynamical system force this system to have a “complex” dynamics? In other words, given a finite interval of integers A, which are the signed digraphs G such that every finite dynamical system f:An→An with G as interaction graph has a “complex” dynamics? If |A|≥3 we prove that no such signed digraph exists. More precisely, we prove that for every signed digraph G there exists a system f:An→An with G as interaction graph that converges toward a unique fixed point in at most ⌊log2n⌋+2 steps. The boolean case |A|=2 is more difficult, and we provide partial answers instead. We exhibit large classes of unsigned digraphs which admit boolean dynamical systems which converge toward a unique fixed point in polynomial, linear or constant time.},
doi = {10.1016/j.tcs.2016.03.013},
issn = {0304-3975},
journal = {Theoretical Computer Science},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {62-77},
publicationstatus = {Published},
publisher = {Elsevier},
volume = {628},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2016},
author = {Gadouleau, Maximilien and Richard, Adrien}
}