Advanced search
1 file | 1.51 MB Add to list

Two-dimensional rotation-symmetric number-conserving cellular automata

(2021) INFORMATION SCIENCES. 577. p.599-621
Author
Organization
Abstract
We present a novel method to study two-dimensional rotation-symmetric number conserving multi-state cellular automata with the von Neumann neighborhood with radius one. This method enables a succinct and easy enumeration in all cases examined so far in literature, i.e., cellular automata with at most five states. Moreover, it allows to find all such cellular automata with six and seven states, while so far, even enumerating six-state rules was beyond the reach of computing machines. Such enumeration allows us to revisit some unresolved questions in the field. Furthermore, we give some rough estimates of the asymptotic growth of the number of such cellular automata with n states, as n tends to infinity. The results are obtained for finite square grids with periodic boundary conditions, but they are also valid in the case of the infinite square grid.
Keywords
Control and Systems Engineering, Theoretical Computer Science, Software, Information Systems and Management, Artificial Intelligence, Computer Science Applications, Cellular automata, Two-dimensional, Rotation symmetry, Number conservation, Multi-state, Logical universality

Downloads

  • (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 1.51 MB

Citation

Please use this url to cite or link to this publication:

MLA
Dzedzej, Adam, et al. “Two-Dimensional Rotation-Symmetric Number-Conserving Cellular Automata.” INFORMATION SCIENCES, vol. 577, 2021, pp. 599–621, doi:10.1016/j.ins.2021.06.041.
APA
Dzedzej, A., Wolnik, B., Nenca, A., Baetens, J., & De Baets, B. (2021). Two-dimensional rotation-symmetric number-conserving cellular automata. INFORMATION SCIENCES, 577, 599–621. https://doi.org/10.1016/j.ins.2021.06.041
Chicago author-date
Dzedzej, Adam, Barbara Wolnik, Anna Nenca, Jan Baetens, and Bernard De Baets. 2021. “Two-Dimensional Rotation-Symmetric Number-Conserving Cellular Automata.” INFORMATION SCIENCES 577: 599–621. https://doi.org/10.1016/j.ins.2021.06.041.
Chicago author-date (all authors)
Dzedzej, Adam, Barbara Wolnik, Anna Nenca, Jan Baetens, and Bernard De Baets. 2021. “Two-Dimensional Rotation-Symmetric Number-Conserving Cellular Automata.” INFORMATION SCIENCES 577: 599–621. doi:10.1016/j.ins.2021.06.041.
Vancouver
1.
Dzedzej A, Wolnik B, Nenca A, Baetens J, De Baets B. Two-dimensional rotation-symmetric number-conserving cellular automata. INFORMATION SCIENCES. 2021;577:599–621.
IEEE
[1]
A. Dzedzej, B. Wolnik, A. Nenca, J. Baetens, and B. De Baets, “Two-dimensional rotation-symmetric number-conserving cellular automata,” INFORMATION SCIENCES, vol. 577, pp. 599–621, 2021.
@article{8716883,
  abstract     = {{We present a novel method to study two-dimensional rotation-symmetric number conserving multi-state cellular automata with the von Neumann neighborhood with radius one. This method enables a succinct and easy enumeration in all cases examined so far in literature, i.e., cellular automata with at most five states. Moreover, it allows to find all such cellular automata with six and seven states, while so far, even enumerating six-state rules was beyond the reach of computing machines. Such enumeration allows us to revisit some unresolved questions in the field. Furthermore, we give some rough estimates of the asymptotic growth of the number of such cellular automata with n states, as n tends to infinity. The results are obtained for finite square grids with periodic boundary conditions, but they are also valid in the case of the infinite square grid.}},
  author       = {{Dzedzej, Adam and Wolnik, Barbara and Nenca, Anna and Baetens, Jan and De Baets, Bernard}},
  issn         = {{0020-0255}},
  journal      = {{INFORMATION SCIENCES}},
  keywords     = {{Control and Systems Engineering,Theoretical Computer Science,Software,Information Systems and Management,Artificial Intelligence,Computer Science Applications,Cellular automata,Two-dimensional,Rotation symmetry,Number conservation,Multi-state,Logical universality}},
  language     = {{eng}},
  pages        = {{599--621}},
  title        = {{Two-dimensional rotation-symmetric number-conserving cellular automata}},
  url          = {{http://doi.org/10.1016/j.ins.2021.06.041}},
  volume       = {{577}},
  year         = {{2021}},
}

Altmetric
View in Altmetric
Web of Science
Times cited: