A directed graph allowing for the exploration of the set of number-conserving non-uniform one-dimensional binary cellular automata with radius one and half
- Author
- Barbara Wolnik (UGent) , Maciej Dziemiańczuk, Bartosz Makuracki and Bernard De Baets (UGent)
- Organization
- Abstract
- The main obstacle in the quest for non-uniform cellular automata that meet the often desired property of number conservation is the vast size of the search space, going far beyond the capabilities of today's computers. In this paper, we expound the construction of a directed graph II related to the set of all number-conserving non-uniform one-dimensional binary cellular automata with radius one and half (i.e., the neighborhood of a cell consists of four cells). We show that there is a one-to-one correspondence between the set of all such cellular automata on a finite grid with n cells and the set of all length-n closed directed walks in II. This provides us with a powerful tool to investigate non-uniform cellular automata of this type.
- Keywords
- Non-uniform cellular automata, Number conservation, Finite grids, COMPLEXITY
Downloads
-
s11047-025-10015-y.pdf
- full text (Published version)
- |
- open access
- |
- |
- 719.62 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU-01K58WD4RYXDS7VTTTZJX1T3E6
- MLA
- Wolnik, Barbara, et al. “A Directed Graph Allowing for the Exploration of the Set of Number-Conserving Non-Uniform One-Dimensional Binary Cellular Automata with Radius One and Half.” NATURAL COMPUTING, vol. 24, no. 3, 2025, pp. 469–82, doi:10.1007/s11047-025-10015-y.
- APA
- Wolnik, B., Dziemiańczuk, M., Makuracki, B., & De Baets, B. (2025). A directed graph allowing for the exploration of the set of number-conserving non-uniform one-dimensional binary cellular automata with radius one and half. NATURAL COMPUTING, 24(3), 469–482. https://doi.org/10.1007/s11047-025-10015-y
- Chicago author-date
- Wolnik, Barbara, Maciej Dziemiańczuk, Bartosz Makuracki, and Bernard De Baets. 2025. “A Directed Graph Allowing for the Exploration of the Set of Number-Conserving Non-Uniform One-Dimensional Binary Cellular Automata with Radius One and Half.” NATURAL COMPUTING 24 (3): 469–82. https://doi.org/10.1007/s11047-025-10015-y.
- Chicago author-date (all authors)
- Wolnik, Barbara, Maciej Dziemiańczuk, Bartosz Makuracki, and Bernard De Baets. 2025. “A Directed Graph Allowing for the Exploration of the Set of Number-Conserving Non-Uniform One-Dimensional Binary Cellular Automata with Radius One and Half.” NATURAL COMPUTING 24 (3): 469–482. doi:10.1007/s11047-025-10015-y.
- Vancouver
- 1.Wolnik B, Dziemiańczuk M, Makuracki B, De Baets B. A directed graph allowing for the exploration of the set of number-conserving non-uniform one-dimensional binary cellular automata with radius one and half. NATURAL COMPUTING. 2025;24(3):469–82.
- IEEE
- [1]B. Wolnik, M. Dziemiańczuk, B. Makuracki, and B. De Baets, “A directed graph allowing for the exploration of the set of number-conserving non-uniform one-dimensional binary cellular automata with radius one and half,” NATURAL COMPUTING, vol. 24, no. 3, pp. 469–482, 2025.
@article{01K58WD4RYXDS7VTTTZJX1T3E6,
abstract = {{The main obstacle in the quest for non-uniform cellular automata that meet the often desired property of number conservation is the vast size of the search space, going far beyond the capabilities of today's computers. In this paper, we expound the construction of a directed graph II related to the set of all number-conserving non-uniform one-dimensional binary cellular automata with radius one and half (i.e., the neighborhood of a cell consists of four cells). We show that there is a one-to-one correspondence between the set of all such cellular automata on a finite grid with n cells and the set of all length-n closed directed walks in II. This provides us with a powerful tool to investigate non-uniform cellular automata of this type.}},
author = {{Wolnik, Barbara and Dziemiańczuk, Maciej and Makuracki, Bartosz and De Baets, Bernard}},
issn = {{1567-7818}},
journal = {{NATURAL COMPUTING}},
keywords = {{Non-uniform cellular automata,Number conservation,Finite grids,COMPLEXITY}},
language = {{eng}},
number = {{3}},
pages = {{469--482}},
title = {{A directed graph allowing for the exploration of the set of number-conserving non-uniform one-dimensional binary cellular automata with radius one and half}},
url = {{http://doi.org/10.1007/s11047-025-10015-y}},
volume = {{24}},
year = {{2025}},
}
- Altmetric
- View in Altmetric
- Web of Science
- Times cited: