When we focus on finite dynamical systems from both the computability/complexity and the modelling standpoints, automata networks seem to be a particularly appropriate mathematical model on which theory shall be developed. In this paper, automata networks are finite collections of entities (the automata), each automaton having its own set of possible states, which interact with each other over discrete time, interactions being defined as local functions allowing the automata to change their state according to the states of their neighbourhoods. The studies on this model of computation have underlined the very importance of the way (i.e. the schedule) according to which the automata update their states, namely the update modes which can be deterministic, periodic, fair, or not. Indeed, a given network may admit numerous underlying dynamics, these latter depending highly on the update modes under which we let the former evolve. In this paper, we pay attention to a new kind of deterministic, periodic and fair update mode family introduced recently in a modelling framework, called the block-parallel update modes by duality with the well-known and studied block-sequential update modes. More precisely, in the general context of automata networks, this work aims at presenting what distinguish block-parallel update modes from block-sequential ones, and at counting and enumerating them: in absolute terms, by keeping only representatives leading to distinct dynamics, and by keeping only representatives giving rise to distinct isomorphic limit dynamics. Put together, this paper constitutes a first theoretical analysis of these update modes and their impact on automata networks dynamics.
翻译:当我们从计算机可计算性和复杂性以及建模的角度来关注有限动态系统时,自动机网络似乎是一种特别适合的数学模型,其上可以开展理论研究。在本文中,自动机网络是由实体(自动机)组成的有限集合,每个自动机都有其自身可能的状态,它们在离散的时间内彼此交互,这些交互定义为局部函数,允许自动机根据它们邻居的状态更改自身状态。对这个计算模型的研究强调了自动机更新状态的方式(即时间表)的极其重要性,即更新模式可以是确定性的、周期性的、公平的、或者不公平的。事实上,给定的网络可能具有许多底层动态,这些底层动态高度取决于让其演化的更新模式。在本文中,我们关注最近在建模框架中引入的新型确定性、周期性和公平的更新模式家族,称之为块并行更新模式,这与著名的、广为人知的块顺序更新模式形成对偶。更具体地,本文在自动机网络的一般背景下,旨在阐述块并行更新模式与块顺序更新模式之间的区别,并对其进行计数和枚举:在绝对意义上,仅保留导致不同动态的代表,以及仅保留产生不同同构极限动态的代表。综合起来,本文构成了这些更新模式及其对自动机网络动态的影响的第一次理论分析。