2013/10/21 by Tarek Melliti, Mathilde Noual, Melliti, Tarek +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1310.5747
openalex publication_date 2013/10/21 · arxiv created 2014/02/18 · arxiv updated 2014/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The understanding of Boolean automata networks dynamics takes an important place in various domains of computer science such as computability, complexity and discrete dynamical systems. In this paper, we make a step further in this understanding by focusing on their cycles, whose necessity in networks is known as the brick of their complexity. We present new results that provide a characterisation of the transient and asymptotic dynamics, i.e. of the computational abilities, of asynchronous Boolean automata networks composed of two cycles that intersect at one automaton, the so-called double-cycles. To do so, we introduce an efficient formalism inspired by algorithms to define long sequences of updates, that allows a better description of their dynamics than previous works in this area.