Parallel dynamical systems over special digraph classes

Abstract

In a previous work, for parallel dynamical systems over digraphs corresponding to the simplest Boolean functions AND and OR, we proved that only fixed or eventually fixed points appear, as it occurs over undirected dependency graphs. Nevertheless, for general Boolean functions, it was shown that any period can appear, depending on the Boolean function that infers the global evolution operator of the system and on the structure of the dependency digraph. Motivated by these results, in this work, we analyse the orbit structure of parallel discrete dynamical systems over some special digraph classes.

Keywords:

• parallel discrete dynamical systems
• periodic orbits
• cellular automata
• dependency digraphs
• Boolean functions

2000 AMS Subject Classifications:

• 37B99
• 37E15
• 37N99
• 68R10
• 94C10

Acknowledgements

This work has been partially supported by the Grants MTM2011-23221, PEII11-0132-7661 and PEII09-0184-7802.