m-Asynchronous cellular automata: from fairness to quasi-fairness

被引:0
作者
Alberto Dennunzio
Enrico Formenti
Luca Manzoni
Giancarlo Mauri
机构
[1] Università degli Studi di Milano-Bicocca,Dipartimento di Informatica, Sistemistica e Comunicazione
[2] Université Nice Sophia Antipolis,Laboratoire I3S
来源
Natural Computing | 2013年 / 12卷
关键词
Cellular automata; Asynchronous cellular automata; Dynamical behavior; Decidability;
D O I
暂无
中图分类号
学科分类号
摘要
A new model for the study of asynchronous cellular automata dynamical behavior is introduced with the main purpose of unifying several existing paradigms. The main idea is to measure the set of updating sequences to quantify the dependency of the properties under investigation from them. We propose to use the class of quasi-fair measures, namely measures that satisfy some fairness conditions on the updating sequences. Basic set properties like injectivity and surjectivity are adapted to the new setting and studied. In particular, we prove that they are dimensions sensitive properties (i.e., they are decidable in dimension 1 and undecidable in higher dimensions). A first exploration of dynamical properties is also started, some results about equicontinuity and expansivity behaviors are provided.
引用
收藏
页码:561 / 572
页数:11
相关论文
共 66 条
[1]  
Acerbi L(2009)Conservation of some dynamical properties for operations on cellular automata Theor Comput Sci 410 3685-3693
[2]  
Dennunzio A(2013)Surjective multidimensional cellular automata are non-wandering: a combinatorial proof Inf Process Lett 113 156-159
[3]  
Formenti E(1972)Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures J Comput Syst Sci 6 448-464
[4]  
Acerbi L(2005)Some results about the chaotic behavior of cellular automata Theor Comput Sci 349 318-336
[5]  
Dennunzio A(1984)Structure in asynchronous cellular automata Phys D 1 59-68
[6]  
Formenti E(1917)Sulla probabilità come limite della frequenza Rend Accad Lincei 24 39-45
[7]  
Amoroso S(2002)Chaotic subshifts and related languages applications to one-dimensional cellular automata Fundam Inform 52 39-80
[8]  
Patt YN(2004)Solution of some conjectures about topological properties of linear cellular automata Theor Comput Sci 325 249-271
[9]  
Blanchard F(2012)From one-dimensional to two-dimensional cellular automata Fundam Inform 115 87-105
[10]  
Cervelle J(2009)On the directional dynamics of additive cellular automata Theor Comput Sci 410 4823-4833