Simple dynamics on graphs

详细信息    查看全文

• 作者：Maximilien Gadouleau^a ; ¹ ; ^{m.r.gadouleau@durham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Adrien Richard^b ; ¹ ; ^{richard@unice.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Discrete dynamical system ; Boolean network ; Interaction graph ; Fixed point
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：16 May 2016
• 年：2016
• 卷：628
• 期：Complete
• 页码：62-77
• 全文大小：484 K

文摘

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:Aⁿ→Aⁿ$f:A^n\to A^n$ with G   as interaction graph has a “complex” dynamics? If |A|≥3$|A|\ge 3$ we prove that no such signed digraph exists. More precisely, we prove that for every signed digraph G   there exists a system f:Aⁿ→Aⁿ$f:A^n\to A^n$ with G   as interaction graph that converges toward a unique fixed point in at most ⌊log₂⁡n⌋+2$\lfloor {\log }_{2}n\rfloor +2$ steps. The boolean case |A|=2$|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.