{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:27Z","timestamp":1725490227619},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_22","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:32:38Z","timestamp":1188336758000},"page":"248-260","source":"Crossref","is-referenced-by-count":2,"title":["Algorithmic Information Theory and Cellular Automata Dynamics"],"prefix":"10.1007","author":[{"given":"Julien","family":"Cervelle","sequence":"first","affiliation":[]},{"given":"Bruno","family":"Durand","sequence":"additional","affiliation":[]},{"given":"Enrico","family":"Formenti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"22_CR1","unstructured":"P. K\u016frka A. Maass. Stability of subshifts in cellular automata. to appaer in Fondamenta informatic\u00e6, 2000."},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(72)80013-8","volume":"6","author":"S. Amoroso","year":"1972","unstructured":"S. Amoroso and Y. N. Patt. Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures. J. Comp. Syst. Sci., 6:448\u2013464, 1972.","journal-title":"J. Comp. Syst. Sci."},{"issue":"4","key":"22_CR3","doi-asserted-by":"publisher","first-page":"1407","DOI":"10.1109\/18.681318","volume":"44","author":"C. H. Bennet","year":"1998","unstructured":"C. H. Bennet, P. G\u00e1cs, M. Li, P. M. B. Vit\u00e1nyi, and W. H. Zurek. Information distance. IEEE Trans. Inform. Theory, 44(4):1407\u20131423, 1998.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"22_CR4","unstructured":"F. Blanchard, E. Formenti, and P. K\u016frka. Cellular automata in Cantor, Besicovitch and Weyl topological spaces. Complex Systems, 11\u20132, 1999."},{"key":"22_CR5","first-page":"127","volume":"2","author":"A. A. Brudno","year":"1983","unstructured":"A. A. Brudno. Entropy and complexity of the trajectories of a dynamical system. Trans. Moscow Math. Soc., 2:127\u2013151, 1983.","journal-title":"Trans. Moscow Math. Soc."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"C. Calude. Information and Randomness. Springer-Verlag, 1994.","DOI":"10.1007\/978-3-662-03049-3"},{"key":"22_CR7","first-page":"1","volume":"1","author":"C. Calude","year":"2000","unstructured":"C. Calude, P. Hertling, H. J\u00fcrgensen, and K. Weihrauch. Randomness on full shift spaces. Chaos, Solitons & Fractals, 1:1\u201313, 2000.","journal-title":"Chaos, Solitons & Fractals"},{"issue":"1-2","key":"22_CR8","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0304-3975(98)00005-X","volume":"233","author":"G. Cattaneo","year":"1999","unstructured":"G. Cattaneo, E. Formenti, G. Manzini, and L. Margara. Ergodicity and regularity for cellular automata over Z m . Theoretical Computer Science, 233(1-2):147\u2013164, 1999.","journal-title":"Zm. Theoretical Computer Science"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"G. J. Chaitin","year":"1966","unstructured":"G. J. Chaitin. On the length of programs for computing finite binary sequences. J. of ACM, 13:547\u2013569, 1966.","journal-title":"J. of ACM"},{"issue":"1-2","key":"22_CR10","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0304-3975(00)00012-8","volume":"259","author":"J.-C. Dubacq","year":"2001","unstructured":"J.-C. Dubacq, B. Durand, and E. Formenti. Kolmogorov complexity and cellular automata classification. Theor. Comp. Sci., 259(1-2):271\u2013285, 2001.","journal-title":"Theor. Comp. Sci."},{"issue":"3","key":"22_CR11","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1016\/S0022-0000(05)80077-7","volume":"49","author":"B. Durand","year":"1994","unstructured":"B. Durand. The surjectivity problem for 2D cellular automata. Journal of Computer and Systems Science, 49(3):718\u2013725, 1994.","journal-title":"Journal of Computer and Systems Science"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"B. Durand. Global properties of cellular automata. In E. Goles and S. Martinez, editors, Cellular Automata and Complex Systems. Kluwer, 1998.","DOI":"10.1007\/978-94-015-9223-9_1"},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80025-X","volume":"48","author":"J. Kari","year":"1994","unstructured":"J. Kari. Reversibility and surjectivity problems of cellular automata. Journal of Computer and System Sciences, 48:149\u2013182, 1994.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR14","first-page":"3","volume":"1","author":"A. N. Kolmogorov","year":"1965","unstructured":"A. N. Kolmogorov. Three approaches to the definition of the concept \u201cquantity of information\u201d. Problems of information transmission, 1:3\u201311, 1965.","journal-title":"Problems of information transmission"},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"M. Li and P. Vit\u00e1nyi. An Introduction to Kolmogorov complexity and its applications. Springer-Verlag, second edition, 1997.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"22_CR16","unstructured":"B. Martin. Apparent entropy of cellular automata. Complex Systems, 12, 2000."},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"P. Martin-L\u00f6f. The definition of a random sequence. Information & Control, 9:602\u2013619, 1966.","journal-title":"Information & Control"},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/S0019-9958(76)90195-9","volume":"32","author":"A. Maruoka","year":"1976","unstructured":"A. Maruoka and M. Kimura. Conditions for injectivity of global maps for tessellation automata. Information & control, 32:158\u2013162, 1976.","journal-title":"Information & control"},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/0022-0000(79)90051-5","volume":"18","author":"A. Maruoka","year":"1979","unstructured":"A. Maruoka and M. Kimura. Injectivity and surjectivity of parallel maps for cellular automata. Journal of Computer and System Sciences, 18:158\u2013162, 1979.","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR20","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1090\/psapm\/014\/9961","volume":"14","author":"E. F. Moore","year":"1963","unstructured":"E. F. Moore. Machine models of self-reproduction. Proc. Symp. Appl. Math., AMS Rep., 14:17\u201334, 1963.","journal-title":"Proc. Symp. Appl. Math., AMS Rep."},{"key":"22_CR21","doi-asserted-by":"publisher","first-page":"685","DOI":"10.2307\/2034301","volume":"14","author":"J. Myhill","year":"1963","unstructured":"J. Myhill. The converse of Moore\u2019s Garden of Eden theorem. Proc. Amer. Math. Soc., 14:685\u2013686, 1963.","journal-title":"Proc. Amer. Math. Soc."},{"key":"22_CR22","first-page":"19","volume":"5","author":"K. Sutner","year":"1991","unstructured":"K. Sutner. De Bruijn graphs and linear cellular automata. Complex Systems, 5:19\u201330, 1991.","journal-title":"Complex Systems"},{"key":"22_CR23","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1070\/RM1990v045n01ABEH002321","volume":"45","author":"V. A. Uspensky","year":"1990","unstructured":"V. A. Uspensky, A. L. Semenov, and A. Kh. Shen. Can individual sequences of zeros and ones be random? Russ. Math. Surveys, 45:121\u2013189, 1990.","journal-title":"Russ. Math. Surveys"},{"issue":"3","key":"22_CR24","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/BF01201280","volume":"29","author":"V. A. Uspensky","year":"1996","unstructured":"V. A. Uspensky and A. Kh. Shen. Relations between varieties of Kolmogorov complexities. Math. Syst. Theory, 29(3):270\u2013291, 1996.","journal-title":"Math. Syst. Theory"},{"key":"22_CR25","doi-asserted-by":"publisher","first-page":"807","DOI":"10.1017\/S0143385700007653","volume":"13","author":"H. S. White","year":"1993","unstructured":"H. S. White. Algorithmic complexity of points in dynamical systems. Ergod. Th. & Dynam. Sys., 13:807\u2013830, 1993.","journal-title":"Ergod. Th. & Dynam. Sys."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:27:51Z","timestamp":1556803671000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}