Quick Convergence to a Fixed Point: A Note on Asynchronous Elementary Cellular Automata

详细信息    查看全文

• 作者：Nazim Fat猫s (18)
  
• 关键词：Asynchronous cellular automata ; stochastic process ; Markov chain analysis ; fast convergence
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8751
• 期：1
• 页码：586-595
• 全文大小：245 KB
• 参考文献：1. Dennunzio, A., Formenti, E., Manzoni, L.: Computing issues of asynchronous CA. Fundamenta Informaticae聽120(2), 165鈥?80 (2012)
  2. Fat猫s, N.: A guided tour of asynchronous cellular automata. In: Kari, J., Kutrib, M., Malcher, A. (eds.) AUTOMATA 2013. LNCS, vol.聽8155, pp. 15鈥?0. Springer, Heidelberg (2013) CrossRef
  3. Fat猫s, N.: A note on the classification of the most simple asynchronous cellular automata. In: Kari, J., Kutrib, M., Malcher, A. (eds.) AUTOMATA 2013. LNCS, vol.聽8155, pp. 31鈥?5. Springer, Heidelberg (2013) CrossRef
  4. Fat猫s, N., Morvan, M., Schabanel, N., Thierry, E.: Fully asynchronous behavior of double-quiescent elementary cellular automata. Theoretical Computer Science聽362, 1鈥?6 (2006) CrossRef
  5. Sethi, B., Fat猫s, N., Das, S.: Reversibility of elementary cellular automata under fully asynchronous update. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol.聽8402, pp. 39鈥?9. Springer, Heidelberg (2014) CrossRef
  6. Sethi, B., Roy, S., Das, S.: Experimental study on convergence time of elementary cellular automata under asynchronous update. In: Kari, J., Kutrib, M., Malcher, A. (eds.) Proceedings of AUTOMATA 2013 - Exploratory Papers. Giessen University - IFIG Research Report 1302 (2013)
  7. Worsch, T.: (Intrinsically?) universal asynchronous CA. In: Sirakoulis, G.C., Bandini, S. (eds.) ACRI 2012. LNCS, vol.聽7495, pp. 689鈥?98. Springer, Heidelberg (2012) CrossRef
  
• 作者单位：Nazim Fat猫s (18)
  
  18. Inria Nancy Grand-Est, LORIA UMR 7503, F-54 600, Villers-l猫s-Nancy, France
  
• ISSN：1611-3349

文摘

This note describes a small step in the analysis of the fully asynchronous cellular automata (i.e., the cells are updated uniformly at random at each time step). We establish the rapid convergence of fifteen minimal Elementary Cellular Automata, showing that their average convergence time to a fixed point scales logarithmically with the size of the automaton. Techniques involve the use of Markov chain analysis and the construction of adequate potential functions. The problem is however left open for twelve other minimal rules, which shows the need to develop this analysis further.