Gadouleau, Maximilien and Richard, Adrien (2016) 'Simple dynamics on graphs.', Theoretical computer science., 628 . pp. 62-77.
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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (347Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/j.tcs.2016.03.013|
|Publisher statement:||© 2016 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|Date accepted:||08 March 2016|
|Date deposited:||30 August 2016|
|Date of first online publication:||10 March 2016|
|Date first made open access:||10 March 2017|
Save or Share this output
|Look up in GoogleScholar|