On Boolean Automata Networks (de)Composition¹

Issue title: Special Issue on Machines, Computations and Universality (MCU 2018)

Guest editors: Jérôme Durand-Lose, Jarkko Kari and Sergey Verlan

Article type: Research Article

Authors: Perrot, Kévin^a | Perrotin, Pacôme^{b; †} | Sené, Sylvain^c

Affiliations: [a] Université publique, France. kevin.perrot@lis-lab.fr | [b] Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France. pacome.perrotin@lis-lab.fr | [c] Université publique, France. sylvain.sene@lis-lab.fr

Correspondence: [†] Address for correspondence: LIS, BP5, Parc scientifique et technologique de Luminy, 163 avenue de Luminy - Case 901, 13288 Marseille cedex 9, France

Note: [*] This article is an extended version of [1].

Abstract: Boolean automata networks (BANs) are a generalisation of Boolean cellular automata. In such, any theorem describing the way BANs compute information is a strong tool that can be applied to a wide range of models of computation. In this paper we explore a way of working with BANs which involves adding external inputs to the base model (via modules), and more importantly, a way to link networks together using the above mentioned inputs (via wirings). Our aim is to develop a powerful formalism for BAN (de)composition. We formulate three results: the first one shows that our modules/wirings definition is complete; the second one uses modules/wirings to prove simulation results amongst BANs; the final one expresses the complexity of the relation between modularity and the dynamics of modules.

Keywords: Boolean automata networks, modules, wirings, simulation

DOI: 10.3233/FI-2021-2055

Journal: Fundamenta Informaticae, vol. 181, no. 2-3, pp. 163-188, 2021