Simple dynamics on graphs

DOI10.1016/J.TCS.2016.03.013MaRDI QIDQ266275zbMATH OpenOpenAlexFDO

Authors Maximilien Gadouleau, Adrien Richard

Publication date 13 April 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04688

zbMATH Keywords

fixed pointBoolean networkdiscrete dynamical systeminteraction graph

Mathematics Subject Classification ID

Applications of graph theory (05C90) Combinatorics in computer science (68R05) Dynamical systems involving maps of trees and graphs (37E25)

Abstract: Does the interaction graph of a finite dynamical system can 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^{n}o{A}^n$ with $G$ as interaction graph has a "complex" dynamics ? If $|A|geq3$ we prove that no such signed digraph exists. More precisely, we prove that for every signed digraph $G$ there exists a system $f:A^{n}o{A}^n$ with $G$ as interaction graph that converges toward a unique fixed point in at most $lfloorlo{g}_{2}nfloor+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.

Recommendations

• Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules
• Parallel dynamical systems over special digraph classes
• Equivalence relations on finite dynamical systems
• On the rank and periodic rank of finite dynamical systems
• Boolean monomial dynamical systems

Cites work

• scientific article; zbMATH DE number 4042465 (Why is no real title available?)
• scientific article; zbMATH DE number 45557 (Why is no real title available?)
• scientific article; zbMATH DE number 50840 (Why is no real title available?)
• A combinatorial analogue of the Jacobian problem in automata networks
• A logical calculus of the ideas immanent in nervous activity
• Boolean monomial dynamical systems
• Combinatorics of Boolean automata circuits dynamics
• Disjunctive networks and update schedules
• Dynamics of positive automata networks
• Fixed points of Boolean networks, guessing graphs, and coding theory
• Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework
• Iterative behaviour of generalized majority functions
• Maximum number of fixed points in regulatory Boolean networks
• Minimal strong digraphs
• Multistationarity, the basis of cell differentiation and memory. II: Logical analysis of regulatory networks in terms of feedback circuits
• Neural networks and physical systems with emergent collective computational abilities
• On Powers of Non-Negative Matrices
• On periodical behaviour in societies with symmetric influences
• On the Sequence of Consecutive Powers of a Matrix in a Boolean Algebra
• Sequential operator for filtering cycles in Boolean networks
• The dynamics of conjunctive and disjunctive Boolean network models
• Topological fixed points in Boolean networks

Cited in

(15)

• On the rank and periodic rank of finite dynamical systems
• On simulation in automata networks
• Cold dynamics in cellular automata: a tutorial
• On the dynamics of semilattice networks
• Expansive automata networks
• Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules
• Equivalence relations on finite dynamical systems
• scientific article; zbMATH DE number 4122019 (Why is no real title available?)
• scientific article; zbMATH DE number 5778718 (Why is no real title available?)
• On the stability and instability of finite dynamical systems with prescribed interaction graphs
• Attractors and cyclic states in finite dynamic systems of complete graphs orientations
• On the influence of the interaction graph on a finite dynamical system
• On the parameterized complexity of freezing dynamics
• On the impact of treewidth in the computational complexity of freezing dynamics
• The hardness of local certification of finite-state dynamics

This page was built for publication: Simple dynamics on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266275)