{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T12:28:08Z","timestamp":1784291288379,"version":"3.55.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["296018"],"award-info":[{"award-number":["296018"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"name":"SPARC, Government of India","award":["P189"],"award-info":[{"award-number":["P189"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Nilpotent cellular automata have the simplest possible dynamics: all initial configurations lead in bounded time into the unique fixed point of the system. We investigate nilpotency in the setup of one-dimensional non-uniform cellular automata (NUCA) where different cells may use different local rules. There are infinitely many cells in NUCA but only a finite number of different local rules. Changing the distribution of the local rules in the system may drastically change the dynamics. We prove that if the available local rules are such that every periodic distribution of the rules leads to nilpotent behavior then so do also all eventually periodic distributions. However, in some cases there may be non-periodic distributions that are not nilpotent even if all periodic distributions are nilpotent. We demonstrate such a possibility using aperiodic Wang tile sets. We also investigate temporally periodic points in NUCA. In contrast to classical uniform cellular automata, there are NUCA\u2014even reversible equicontinuous ones\u2014that do not have any temporally periodic points. We prove the undecidability of this property: there is no algorithm to determine if a NUCA with a given finite distribution of local rules has a periodic point.<\/jats:p>","DOI":"10.1007\/s00236-020-00390-7","type":"journal-article","created":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T09:05:06Z","timestamp":1626685506000},"page":"319-333","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Nilpotency and periodic points in non-uniform cellular automata"],"prefix":"10.1007","volume":"58","author":[{"given":"Supreeti","family":"Kamilya","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0670-6138","authenticated-orcid":false,"given":"Jarkko","family":"Kari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"issue":"3","key":"390_CR1","doi-asserted-by":"publisher","first-page":"519","DOI":"10.2307\/2272894","volume":"39","author":"S Aanderaa","year":"1974","unstructured":"Aanderaa, S., Lewis, H.: Linear sampling and the $$\\forall \\exists \\forall $$ case of the decision problem. J. Symb. Log. 39(3), 519\u2013548 (1974)","journal-title":"J. Symb. Log."},{"key":"390_CR2","volume-title":"The Undecidability of the Domino Problem. Memoirs of the American Mathematical Society","author":"R Berger","year":"1966","unstructured":"Berger, R.: The Undecidability of the Domino Problem. Memoirs of the American Mathematical Society. American Mathematical Society, Providence (1966)"},{"key":"390_CR3","doi-asserted-by":"crossref","unstructured":"Boyle, M.: Open problems in symbolic dynamics. In: Brin, M., Burns, K., Dolgopyat, D., Pesin, Y. (eds.) Geometric and Probabilistic Structures in Dynamics, Contemporary Mathematics, vol. 469, pp. 69\u2013118. American Mathematical Society, Providence (2008)","DOI":"10.1090\/conm\/469\/09161"},{"issue":"4","key":"390_CR4","doi-asserted-by":"publisher","first-page":"725","DOI":"10.2969\/jmsj\/05240725","volume":"52","author":"M Boyle","year":"2000","unstructured":"Boyle, M., Maass, A.: Expansive invertible onesided cellular automata. J. Math. Soc. Jpn. 52(4), 725\u2013740 (2000)","journal-title":"J. Math. Soc. Jpn."},{"key":"390_CR5","series-title":"Springer Monographs in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14034-1","volume-title":"Cellular Automata and Groups","author":"T Ceccherini-Silberstein","year":"2010","unstructured":"Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Berlin (2010)"},{"key":"390_CR6","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.: Non-uniform cellular automata: classes, dynamics, and decidability. Inf. Comput. 215, 32\u201346 (2012)","journal-title":"Inf. Comput."},{"key":"390_CR7","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.tcs.2012.05.013","volume":"504","author":"A Dennunzio","year":"2013","unstructured":"Dennunzio, A., Formenti, E., Provillard, J.: Local rule distributions, language complexity and non-uniform cellular automata. Theor. Comput. Sci. 504, 38\u201351 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"390_CR8","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.tcs.2014.06.046","volume":"559","author":"A Dennunzio","year":"2014","unstructured":"Dennunzio, A., Formenti, E., Provillard, J.: Three research directions in non-uniform cellular automata. Theor. Comput. Sci. 559, 73\u201390 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"390_CR9","volume-title":"An Introduction to Chaotic Dynamical Systems","author":"R Devaney","year":"1989","unstructured":"Devaney, R.: An Introduction to Chaotic Dynamical Systems. Addison-Wesley, Boston (1989)"},{"key":"390_CR10","doi-asserted-by":"crossref","unstructured":"Durand, B., Formenti, E., Varouchas, G.: On undecidability of equicontinuity classification for cellular automata. In: Morvan, M., R\u00e9mila, E. (eds.) Discrete Models for Complex Systems, DMCS\u201903, DMTCS Proceedings, vol. AB, pp. 117\u2013128. DMTCS (2003)","DOI":"10.46298\/dmtcs.2302"},{"key":"390_CR11","doi-asserted-by":"crossref","unstructured":"Guillon, P., Richard, G.: Nilpotency and limit sets of cellular automata. In: Ochma\u0144ski, E., Tyszkiewicz J. (eds.) Mathematical Foundations of Computer Science 2008, MFCS 2008, Lecture Notes in Computer Science, vol. 5162, pp. 375\u2013386. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-85238-4_30"},{"key":"390_CR12","unstructured":"Jeandel, E., Rao, M.: An aperiodic set of 11 Wang tiles (2015). arXiv preprint arXiv:1506.06492"},{"issue":"3","key":"390_CR13","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1137\/0221036","volume":"21","author":"J Kari","year":"1992","unstructured":"Kari, J.: The nilpotency problem of one-dimensional cellular automata. SIAM J. Comput. 21(3), 571\u2013586 (1992)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"390_CR14","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0304-3975(94)90041-8","volume":"127","author":"J Kari","year":"1994","unstructured":"Kari, J.: Rice\u2019s theorem for the limit sets of cellular automata. Theor. Comput. Sci. 127(2), 229\u2013254 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"390_CR15","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1017\/S014338579706985X","volume":"17","author":"P K\u016frka","year":"1997","unstructured":"K\u016frka, P.: Languages, equicontinuity and attractors in cellular automata. Ergod. Theory Dyn. Syst. 17(2), 417\u2013433 (1997)","journal-title":"Ergod. Theory Dyn. Syst."},{"key":"390_CR16","unstructured":"K\u016frka, P.: Topological and Symbolic Dynamics. Collection SMF, Soci\u00e9t\u00e9 math\u00e9matique de France (2003)"},{"issue":"1\u20133","key":"390_CR17","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0012-365X(98)00203-9","volume":"199","author":"J Mazoyer","year":"1999","unstructured":"Mazoyer, J., Rapaport, I.: Global fixed point attractors of circular cellular automata and periodic tilings of the plane: undecidability results. Discret. Math. 199(1\u20133), 103\u2013122 (1999)","journal-title":"Discret. Math."},{"key":"390_CR18","unstructured":"Perrin, D., Pin, J.\u00c9.: Infinite Words: Automata, Semigroups, Logic and Games. Pure and Applied Mathematics Series, vol. 141. Elsevier Morgan Kaufmann, Burlington (2004)"},{"issue":"3","key":"390_CR19","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/BF01418780","volume":"12","author":"RM Robinson","year":"1971","unstructured":"Robinson, R.M.: Undecidability and nonperiodicity for tilings of the plane. Invent. Math. 12(3), 177\u2013209 (1971)","journal-title":"Invent. Math."},{"key":"390_CR20","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1103\/RevModPhys.55.601","volume":"55","author":"S Wolfram","year":"1983","unstructured":"Wolfram, S.: Statistical mechanics of cellular automata. Rev. Mod. Phys. 55, 601\u2013644 (1983)","journal-title":"Rev. Mod. Phys."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-020-00390-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-020-00390-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-020-00390-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,4]],"date-time":"2023-01-04T21:45:40Z","timestamp":1672868740000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-020-00390-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,19]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["390"],"URL":"https:\/\/doi.org\/10.1007\/s00236-020-00390-7","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,19]]},"assertion":[{"value":"29 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}