{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:37:12Z","timestamp":1758274632702},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642283314"},{"type":"electronic","value":"9783642283321"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-28332-1_18","type":"book-chapter","created":{"date-parts":[[2012,2,29]],"date-time":"2012-02-29T14:45:36Z","timestamp":1330526736000},"page":"204-215","source":"Crossref","is-referenced-by-count":1,"title":["Computational Complexity of Rule Distributions of Non-uniform Cellular Automata"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Dennunzio","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enrico","family":"Formenti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julien","family":"Provillard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5","key":"18_CR1","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(72)80013-8","volume":"6","author":"S. Amoroso","year":"1972","unstructured":"Amoroso, S., Patt, Y.N.: Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J. Comput. Syst. Sci.\u00a06(5), 448\u2013464 (1972)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR2","unstructured":"Berstel, J., Perrin, D.: Theory of Codes. Academic Press (1985)"},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/978-3-642-00982-2_26","volume-title":"Language and Automata Theory and Applications","author":"G. Cattaneo","year":"2009","unstructured":"Cattaneo, G., Dennunzio, A., Formenti, E., Provillard, J.: Non-Uniform Cellular Automata. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol.\u00a05457, pp. 302\u2013313. Springer, Heidelberg (2009)"},{"key":"18_CR4","unstructured":"Chaudhuri, P., Chowdhury, D., Nandi, S., Chattopadhyay, S.: Additive Cellular Automata Theory and Applications, vol.\u00a01. IEEE Press (1997)"},{"key":"18_CR5","unstructured":"Dennunzio, A., Formenti, E., Provillard, J.: Local rule distributions, language complexity and non-uniform cellular automata. ArXiv e-prints (2011)"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Dennunzio, A., Formenti, E., Provillard, J.: Non-uniform cellular automata: classes, dynamics, and decidability. ArXiv e-prints (2011)","DOI":"10.1016\/j.ic.2012.02.008"},{"key":"18_CR7","unstructured":"Devaney, R.L.: An Introduction to Chaotic Dynamical Systems, 2nd edn. Westview Pr., Short Disc (2003)"},{"issue":"1-3","key":"18_CR8","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1016\/S0304-3975(02)00534-0","volume":"299","author":"B. Durand","year":"2003","unstructured":"Durand, B., Formenti, E., R\u00f3ka, Z.: Number-conserving cellular automata I: decidability. Theoretical Computer Science\u00a0299(1-3), 523\u2013535 (2003)","journal-title":"Theoretical Computer Science"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","first-page":"117","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"B. Durand","year":"2003","unstructured":"Durand, B., Formenti, E., Varouchas, G.: On Undecidability of Equicontinuity Classification for Cellular Automata. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) DMTCS 2003. LNCS, vol.\u00a02731, pp. 117\u2013128. Springer, Heidelberg (2003)"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/978-3-540-75867-9_71","volume-title":"Computer Aided Systems Theory \u2013 EUROCAST 2007","author":"A. F\u00faster-Sabater","year":"2007","unstructured":"F\u00faster-Sabater, A., Caballero-Gil, P., Pazo-Robles, M.E.: Application of Linear Hybrid Cellular Automata to Stream Ciphers. In: Moreno D\u00edaz, R., Pichler, F., Quesada Arencibia, A. (eds.) EUROCAST 2007. LNCS, vol.\u00a04739, pp. 564\u2013571. Springer, Heidelberg (2007)"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"51911","DOI":"10.1103\/PhysRevE.75.051911","volume":"75","author":"P. Gerlee","year":"2007","unstructured":"Gerlee, P., Anderson, A.R.A.: Stability analysis of a hybrid cellular automaton model of cell colony growth. Phys. Rev. E\u00a075, 051911 (2007)","journal-title":"Phys. Rev. E"},{"issue":"4","key":"18_CR12","first-page":"320","volume":"3","author":"G.A. Hedlund","year":"1969","unstructured":"Hedlund, G.A.: Endomorphisms and automorphisms of the shift dynamical system. Theory of Computing Systems\u00a03(4), 320\u2013375 (1969)","journal-title":"Theory of Computing Systems"},{"key":"18_CR13","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley (2006)"},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80025-X","volume":"48","author":"J. Kari","year":"1994","unstructured":"Kari, J.: Reversibility and surjectivity problems of cellular automata. Journal of Computer and System Sciences\u00a048, 149\u2013182 (1994)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"18_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. Ergodic Theory and Dynamical Systems\u00a017(2), 417\u2013433 (1997)","journal-title":"Ergodic Theory and Dynamical Systems"},{"key":"18_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626302","volume-title":"An introduction to symbolic dynamics and coding","author":"D. Lind","year":"1995","unstructured":"Lind, D., Marcus, B.: An introduction to symbolic dynamics and coding. Cambridge University Press, New York (1995)"},{"key":"18_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(96)00006-0","volume":"174","author":"I. Litovsky","year":"1997","unstructured":"Litovsky, I., Staiger, L.: Finite acceptance of infinite words. Theoretical Computer Science\u00a0174, 1\u201321 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"18_CR18","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0304-3975(99)00031-6","volume":"221","author":"G. Manzini","year":"1999","unstructured":"Manzini, G., Margara, L.: A complete and efficiently computable topological classification of d-dimensional linear cellular automata over Zm. Theoretical Computer Science\u00a0221(1-2), 157\u2013177 (1999)","journal-title":"Theoretical Computer Science"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Moore, E.F.: Machine models of self-reproduction. In: Proceedings of Symposia in Applied Mathematics, vol.\u00a014, pp. 17\u201333 (1962)","DOI":"10.1090\/psapm\/014\/9961"},{"issue":"4","key":"18_CR20","first-page":"685","volume":"14","author":"J. Myhill","year":"1963","unstructured":"Myhill, J.: The converse of Moore\u2019s garden-of-Eden theorem. Proceedings of the American Mathematical Society\u00a014(4), 685\u2013686 (1963)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"Nivat, M., Perrin, D.: Ensembles reconnaissables de mots biinfinis. In: STOC, pp. 47\u201359. ACM (1982)","DOI":"10.1145\/800070.802176"},{"key":"18_CR22","unstructured":"Perrin, D., Pin, J.E.: Infinite Words, Pure and Applied Mathematics, vol.\u00a0141. Elsevier (2004)"},{"key":"18_CR23","first-page":"19","volume":"5","author":"K. Sutner","year":"1991","unstructured":"Sutner, K.: De Bruijn graphs and linear cellular automata. Complex Systems\u00a05, 19\u201330 (1991)","journal-title":"Complex Systems"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28332-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T08:31:04Z","timestamp":1556440264000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28332-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642283314","9783642283321"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28332-1_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}