Searching for chaos in cellular automata Compositional approach.pdf

Searching for Chaos in Cellular Automata Comp ositional Approach P Flo cchini and F Geurts DSI Via Comelico Milano Italy UCL INFO Place Sainte Barb e LouvainlaNeuve Belgium o cchinghostdsiunimiit gfinfouclacb e Abstract We prop ose comp osition op erators allowing to study simple cellular automata and to extend individual results to global ones This comp ositional approach can b e used to reach a b etter understanding of chaos in discretetime multidimensional systems Intro duction The notion of chaos is still unprecise in discretetime discretespace multidimensional dynamical systems like for example cellular automata CA Recently many authors have tried to formalize it Classication of CA wrt their asymptotic b ehavior is a central theme in the eld and should lead to a b etter understanding of chaotic and related b ehaviors However many problems have to b e tackled the asymptotic b ehavior is easy to study theoretically for very few simple cases only in general simulation is used to get results for complex b ehaviors Our purp ose is to move the rst steps towards a denition of chaos in cellular automata using a comp ositional approach We consider elementary cellular automata ie b o olean onedimensional biinnite lattices of cells the evolution of each cell b eing inuenced by its direct neighb ors In order to understand their dynamics the idea is to nd a set of CA whose asymptotic b ehavior is easy to analyze basis CA and to consider all other CA as the comp osition using appropriate op erators of these basis CA Comp ositional approaches have b een prop osed in for diere