Reversibility of Elementary Cellular Automata under Fully Asynchronous Update

被引：0
作者：
Sethi, Biswanath [1 ]
Fates, Nazim [2 ]
Das, Sukanta [3 ]
机构：
[1] Indira Gandhi Inst Technol, Dept Comp Sci Engn & Applicat, Dhenkanal 759146, Odisha, India
[2] Univ Lorraine, CNRS, LORIA UMR 7503, Inria Nancy Grand Est, F-54600 Nancy, France
[3] Bengal Engn & Sci Univ, Dept Informat Technol, Howrah 711103, India
来源：
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014) | 2014年 / 8402卷
关键词：
asynchronous cellular automata; reversibility; recurrence; Markov chain modelling; classification;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We investigate the dynamics of Elementary Cellular Automata (ECA) under fully asynchronous update with periodic boundary conditions. We tackle the reversibility issue, that is, we want to determine whether, starting from any initial condition, it is possible to go back to this initial condition with random updates. We present analytical tools that allow us to partition the ECA space into three classes: strongly irreversible, irreversible and recurrent.
引用
收藏
页码：39 / 49
页数：11
相关论文
共 14 条
  • [1] Amoroso S., 1972, Journal of Computer and System Sciences, V6, P448, DOI 10.1016/S0022-0000(72)80013-8
  • [2] [Anonymous], 1986, Theory and applications of cellular automata
  • [3] Das S, 2006, LECT NOTES COMPUT SC, V4173, P68
  • [4] Characterization of 1-d Periodic Boundary Reversible CA
    Das, Sukanta
    Sikdar, Biplab K.
    [J]. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2009, 252 : 205 - 227
  • [5] Das S, 2012, LECT NOTES COMPUT SC, V7495, P643, DOI 10.1007/978-3-642-33350-7_66
  • [6] Fatès N, 2013, LECT NOTES COMPUT SC, V8155, P15, DOI 10.1007/978-3-642-40867-0_2
  • [7] Fatès N, 2013, LECT NOTES COMPUT SC, V8155, P31, DOI 10.1007/978-3-642-40867-0_3
  • [8] On time-symmetry in cellular automata
    Gajardo, Anahi
    Kari, Jarkko
    Moreira, Andres
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2012, 78 (04) : 1115 - 1126
  • [9] Richardson D., 1972, Journal of Computer and System Sciences, V6, P373, DOI 10.1016/S0022-0000(72)80009-6
  • [10] Reversibility in Asynchronous Cellular Automata
    Sarkar, Anindita
    Mukherjee, Anindita
    Das, Sukanta
    [J]. COMPLEX SYSTEMS, 2012, 21 (01): : 71 - 84
12