The Journal of the Korea institute of electronic communication sciences (한국전자통신학회논문지)

Korea Institute of Electronic Communication Science (한국전자통신학회)
권호 표지
DOI QR코드

DOI QR Code

Reachable table of nonlinear cellular automata

비선형 셀룰라오토마타의 도달가능표

  • 권숙희 (부경대학교 응용수학과) ;
  • 조성진 (부경대학교 응용수학과) ;
  • 최언숙 (동명대학교 정보통신공학과) ;
  • 김한두 (인제대학교 응용수학과)
  • Received : 2015.01.19
  • Accepted : 2015.05.23
  • Published : 2015.05.31
Download PDF
⟨ Previous Next ⟩

Abstract

Non-linear cellular automata is difficult to analyze mathematically than linear cellular automata. So it is difficult to identify reachable states and attractors of nongroup non-linear cellular automata than nongroup linear cellular automata. In this paper, we propose a new reachable table to overcome these problems. We can see the next state for all the states of the non-linear cellular automata by the proposed reachable table. In addition, we can identify reachable states and attractors by the reachable table.

비선형 셀룰라오토마타는 선형 셀룰라오토마타에 비해서 수학적 분석이 어렵다. 그렇기 때문에 비선형 셀룰라오토마타는 비그룹 셀룰라오토마타에 대하여 도달가능상태와 끌개를 식별하기 어렵다. 본 논문에서는 이러한 문제점을 보완하기 위해 도달가능표를 제안한다. 제안한 도달가능표에 의하여 비선형 셀룰라오토마타의 모든 상태에 대한 다음 상태를 알 수 있다. 또한 도달가능표에 의하여 도달가능상태와 끌개를 식별할 수 있다.

Keywords

References

  1. J. Von Neumann, Theory of self-reproducing automata. Urbana and London: University of Illinois Press, 1966. pp. 63-87.
  2. S. Chattopadhyay, S. Adhikari, S. Sengupta, and M. Pal, "Highly Regular, Modular, and Cascadable Design of Cellular Automata-Based Pattern Classifier," IEEE Trans. on VLSI Systems, vol. 8, no. 6, 2000, pp. 724-735. https://doi.org/10.1109/92.902267
  3. P. Maji, C. Shaw, N. Ganguly, B. K. Sikdar, and P. P. Chaudhuri, "Theory and application of cellular automata for pattern classification," Fundamenta Informaticae, vol. 58, 2003, pp. 321-354.
  4. Y. Hwang, S. Cho, and U. Choi, "Multiple Attractor CA Based Pattern Classifier," J. of the Korea Institute of Electronic Communication Sciences, vol. 5, no. 3, 2010, pp. 315-320.
  5. Y. Hwang, U. Choi, and S. Cho, "D1-MACA based two-class Pattern Classifier," J. of the Korea Institute of Electronic Communication Sciences, vol. 3, no. 4, 2008, pp. 254-259.
  6. S. Kwon, S. Cho, U. Choi, H. Kim, and N. Kim "Generation of Pattern Classifier using LFSRs," J. of the Korea Institute of Electronic Communication Sciences, vol. 9, no. 6, 2014, pp. 673-679. https://doi.org/10.13067/JKIECS.2014.9.6.673
  7. S. Cho, H. Kim, U. Choi, S. Kim, J. Kim, S. Kwon, and G. Gong, "Generation of TPMACA for Pattern Classification," Cellular Automata Lecture Notes in Computer Science vol. 8751, 2014, pp. 408-416.
  8. S. Wolfram, "Theory and application of cellular automata(including selected papers 1983-1986)," World Scientific, Advanced series on complex systems, vol. 1. 1986, pp. 67-82.
  9. S. Cho, U. Choi, H. Kim, Y. Hwang, J. Kim, and S. Heo, "New synthesis of one-dimensional 90/150 linear hybrid group cellular automata," IEEE Trans. Comput-Aided Design Integr. Circuits Syst., vol. 26, no. 9, 2007, pp. 1720-1724. https://doi.org/10.1109/TCAD.2007.895784
  10. S. Cho, U. Choi, H. Kim, Y. Hwang, and J. Kim, "Analysis of 90/150 Two Predecessor Nongroup Cellular Automata," Cellular Automata Lecture Notes in Computer Science, vol. 5191, 2008, pp. 128-135.
  11. U. Choi, S. Cho, and J. Yim "Synthesis of 90/150 Uniform CA and Computation of Characteristic Polynomial corresponding to uniform CA," J. of the Korea Institute of Electronic Communication Sciences, vol. 5, no. 1, 2010, pp. 10-16.
  12. S. Das, B. K. Sikdar and P. P. Chaudhuri, "Characterization of Reachable / Non-reachable Cellular Automata States," Cellular Automata Lecture Notes in Computer Science, vol. 3305, 2004, pp. 813-822.