{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T21:19:22Z","timestamp":1771103962018,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T00:00:00Z","timestamp":1746403200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T00:00:00Z","timestamp":1746403200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>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\u2019s computers. In this paper, we expound the construction of a directed graph <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Pi $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03a0<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> 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\u00a0finite grid with <jats:italic>n<\/jats:italic> cells and the set of all length-<jats:italic>n<\/jats:italic> closed directed walks in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Pi $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03a0<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. This provides us with a powerful tool to investigate non-uniform cellular automata of this type.<\/jats:p>","DOI":"10.1007\/s11047-025-10015-y","type":"journal-article","created":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T11:20:31Z","timestamp":1746444031000},"page":"469-482","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"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"],"prefix":"10.1007","volume":"24","author":[{"given":"Barbara","family":"Wolnik","sequence":"first","affiliation":[]},{"given":"Maciej","family":"Dziemia\u0144czuk","sequence":"additional","affiliation":[]},{"given":"Bartosz","family":"Makuracki","sequence":"additional","affiliation":[]},{"given":"Bernard","family":"De Baets","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,5]]},"reference":[{"issue":"28","key":"10015_CR1","doi-asserted-by":"publisher","first-page":"6007","DOI":"10.1088\/0305-4470\/31\/28\/014","volume":"31","author":"N Boccara","year":"1998","unstructured":"Boccara N, Fuk\u015b H (1998) Cellular automaton rules conserving the number of active sites. J Phys A: Math Gen 31(28):6007\u20136018. https:\/\/doi.org\/10.1088\/0305-4470\/31\/28\/014","journal-title":"J Phys A: Math Gen"},{"key":"10015_CR2","doi-asserted-by":"crossref","unstructured":"Cattaneo G, Dennunzio A, Formenti E, Provillard J (2009) Non-uniform cellular automata. In: Proceedings of the 3rd international conference language and automata theory and applications. LATA, pp 302\u2013313","DOI":"10.1007\/978-3-642-00982-2_26"},{"key":"10015_CR3","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.ic.2012.02.008","volume":"215","author":"A Dennunzio","year":"2012","unstructured":"Dennunzio A, Formenti E, Provillard J (2012) Non-uniform cellular automata: classes, dynamics, and decidability. Inf Comput 215:32\u201346. https:\/\/doi.org\/10.1016\/j.ic.2012.02.008","journal-title":"Inf Comput"},{"key":"10015_CR4","doi-asserted-by":"publisher","unstructured":"Dennunzio A, Formenti E, Provillard J (2013) Local rule distributions, language complexity and non-uniform cellular automata. Theoret Comput Sci 504:38\u201351. https:\/\/doi.org\/10.1016\/j.tcs.2012.05.013","DOI":"10.1016\/j.tcs.2012.05.013"},{"key":"10015_CR5","first-page":"195","volume":"6","author":"S El Yacoubi","year":"2011","unstructured":"El Yacoubi S, Mingarelli A (2011) An algebraic characterization of fuzzy cellular automata. J Cell Autom 6:195\u2013206","journal-title":"J Cell Autom"},{"key":"10015_CR6","unstructured":"Hazari R, Das S (2016) On number conservation of non-uniform cellular automata. arXiv:1604.06600"},{"issue":"10","key":"10015_CR7","doi-asserted-by":"publisher","first-page":"1466","DOI":"10.1109\/12.35843","volume":"38","author":"PD Hortensius","year":"1989","unstructured":"Hortensius PD, McLeod RD, Card HC (1989) Parallel random number generation for VLSI systems using cellular automata. IEEE Trans Comput C 38(10):1466\u20131473","journal-title":"IEEE Trans Comput C"},{"issue":"05","key":"10015_CR8","doi-asserted-by":"publisher","first-page":"2150072","DOI":"10.1142\/S0218127421500723","volume":"31","author":"S Pal","year":"2021","unstructured":"Pal S, Sahoo S, Nayak BK (2021) Construction of one-dimensional nonuniform number conserving elementary cellular automata rules. Int J Bifurc Chaos 31(05):2150072. https:\/\/doi.org\/10.1142\/S0218127421500723","journal-title":"Int J Bifurc Chaos"},{"issue":"12","key":"10015_CR9","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1109\/TC.1986.1676709","volume":"35","author":"W Pries","year":"1986","unstructured":"Pries W, Thanailakis A, Card HC (1986) Group properties of cellular automata and VLSI applications. IEEE Trans Comput C 35(12):1013\u20131024","journal-title":"IEEE Trans Comput C"},{"key":"10015_CR10","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.tcs.2014.07.031","volume":"559","author":"V Salo","year":"2014","unstructured":"Salo V (2014) Realization problems for nonuniform cellular automata. Theoret Comput Sci 559:91\u2013107. https:\/\/doi.org\/10.1016\/j.tcs.2014.07.031","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"10015_CR11","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1142\/S012918319600017X","volume":"7","author":"M Sipper","year":"1996","unstructured":"Sipper M, Tomassini M (1996) Generating parallel random number generators by cellular programming. Int J Mod Phys C 7(2):180\u2013190","journal-title":"Int J Mod Phys C"},{"key":"10015_CR12","doi-asserted-by":"crossref","unstructured":"Ulam S (1962) On some mathematical problems connected with patterns of growth of figures. In: Proceedings of symposia in applied mathematics, vol 14, pp 215\u2013224","DOI":"10.1090\/psapm\/014\/9947"},{"key":"10015_CR13","unstructured":"von Neumann J (1966) Theory of self-reproducing automata. University of Illinois Press, Champaign. completed and edited by Burks, Arthur W"},{"issue":"1\u20132","key":"10015_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-2789(84)90245-8","volume":"10","author":"S Wolfram","year":"1984","unstructured":"Wolfram S (1984) Universality and complexity in cellular automata. Physica D 10(1\u20132):1\u201335. https:\/\/doi.org\/10.1016\/0167-2789(84)90245-8","journal-title":"Physica D"},{"key":"10015_CR15","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1016\/j.ins.2023.01.033","volume":"626","author":"B Wolnik","year":"2023","unstructured":"Wolnik B, Dziemia\u0144czuk M, De Baets B (2023) Non-uniform number-conserving elementary cellular automata. Inf Sci 626:851\u2013866. https:\/\/doi.org\/10.1016\/j.ins.2023.01.033","journal-title":"Inf Sci"},{"key":"10015_CR16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2023.119680","volume":"649","author":"B Wolnik","year":"2023","unstructured":"Wolnik B, Dziemia\u0144czuk M, De Baets B (2023) Non-uniform number-conserving elementary cellular automata on the infinite grid: a tale of the unexpected. Inf Sci 649:119680. https:\/\/doi.org\/10.1016\/j.ins.2023.119680","journal-title":"Inf Sci"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10015-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-025-10015-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10015-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T19:19:47Z","timestamp":1757531987000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-025-10015-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,5]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10015"],"URL":"https:\/\/doi.org\/10.1007\/s11047-025-10015-y","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,5]]},"assertion":[{"value":"2 April 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}