{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:41:05Z","timestamp":1725795665625},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439500"},{"type":"electronic","value":"9783662439517"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_7","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"74-85","source":"Crossref","is-referenced-by-count":1,"title":["Turing Degrees of Limit Sets of Cellular Automata"],"prefix":"10.1007","author":[{"given":"Alex","family":"Borello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julien","family":"Cervelle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Vanier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"7_CR1","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1147\/rd.176.0525","volume":"17","author":"C.H. Bennett","year":"1973","unstructured":"Bennett, C.H.: Logical Reversibility of Computation. IBM J. Res. Dev.\u00a017(6), 525\u2013532 (1973)","journal-title":"IBM J. Res. Dev."},{"issue":"1-4","key":"7_CR2","doi-asserted-by":"crossref","first-page":"45","DOI":"10.3233\/FI-2011-527","volume":"110","author":"A. Ballier","year":"2011","unstructured":"Ballier, A., Guillon, P., Kari, J.: Limit Sets of Stable and Unstable Cellular Automata. Fundam. Inform.\u00a0110(1-4), 45\u201357 (2011)","journal-title":"Fundam. Inform."},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Cenzer, D., Remmel, J.: $\\Pi_1^0$ classes in mathematics. In: Handbook of Recursive Mathematics - Volume 2: Recursive Algebra, Analysis and Combinatorics. Studies in Logic and the Foundations of Mathematics, ch. 13, vol.\u00a0139, pp. 623\u2013821 (1998)","DOI":"10.1016\/S0049-237X(98)80046-3"},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1088\/0951-7715\/20\/1\/007","volume":"20","author":"E. Formenti","year":"2007","unstructured":"Formenti, E., K\u016frka, P.: Subshift attractors of cellular automata. Nonlinearity\u00a020, 105\u2013117 (2007)","journal-title":"Nonlinearity"},{"issue":"2","key":"7_CR5","doi-asserted-by":"publisher","first-page":"219","DOI":"10.2307\/2269811","volume":"31","author":"P.K. Hooper","year":"1966","unstructured":"Hooper, P.K.: The Undecidability of the Turing Machine Immortality Problem. Journal of Symbolic Logic\u00a031(2), 219\u2013234 (1966)","journal-title":"Journal of Symbolic Logic"},{"issue":"1","key":"7_CR6","first-page":"69","volume":"1","author":"L.P. Hurd","year":"1987","unstructured":"Hurd, L.P.: Formal Language Characterization of Cellular Automaton Limit Sets. Complex Systems\u00a01(1), 69\u201380 (1987)","journal-title":"Complex Systems"},{"issue":"2","key":"7_CR7","first-page":"131","volume":"4","author":"L.P. Hurd","year":"1990","unstructured":"Hurd, L.P.: Nonrecursive Cellular Automata Invariant Sets. Complex Systems\u00a04(2), 131\u2013138 (1990)","journal-title":"Complex Systems"},{"issue":"2","key":"7_CR8","first-page":"131","volume":"4","author":"L.P. Hurd","year":"1990","unstructured":"Hurd, L.P.: Recursive Cellular Automata Invariant Sets. Complex Systems\u00a04(2), 131\u2013138 (1990)","journal-title":"Complex Systems"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Jockusch, C.G., Soare, R.I.: Degrees of members of classes $\\Pi_1^0$ . Pacific J. Math.\u00a040(3), 605\u2013616 (1972)","DOI":"10.2140\/pjm.1972.40.605"},{"key":"7_CR10","unstructured":"Jeandel, E., Vanier, P.: Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type. In: STACS. LIPIcs, vol.\u00a020, pp. 490\u2013501 (2013)"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Jeandel, E., Vanier, P.: Turing degrees of multidimensional SFTs. In: Theoretical Computer Science 505.0. Theory and Applications of Models of Computation, pp. 81\u201392 (2011)","DOI":"10.1016\/j.tcs.2012.08.027"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Kari, J.: Reversibility of 2D cellular automata is undecidable. Physica D: Nonlinear Phenomena\u00a045(1-3), 379\u2013385 (1990)","DOI":"10.1016\/0167-2789(90)90195-U"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"Kari, J.: The Nilpotency Problem of One-Dimensional Cellular Automata. SIAM Journal on Computing\u00a021(3), 571\u2013586 (1992)","DOI":"10.1137\/0221036"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"Kari, J.: Reversibility and surjectivity problems of cellular automata. Journal of Computer and System Sciences\u00a048(1), 149\u2013182 (1994)","DOI":"10.1016\/S0022-0000(05)80025-X"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Kari, J.: Rice\u2019s theorem for the limit sets of cellular automata. Theoretical Computer Science\u00a0127(2), 229\u2013254 (1994)","DOI":"10.1016\/0304-3975(94)90041-8"},{"key":"7_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-540-85238-4_34","volume-title":"Mathematical Foundations of Computer Science 2008","author":"J. Kari","year":"2008","unstructured":"Kari, J., Ollinger, N.: Periodicity and Immortality in Reversible Computing. In: Ochma\u0144ski, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol.\u00a05162, pp. 419\u2013430. Springer, Heidelberg (2008)"},{"key":"7_CR17","unstructured":"Lena, P.D., Margara, L.: Undecidable Properties of Limit Set Dynamics of Cellular Automata. In: 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a03, pp. 337\u2013348 (2009)"},{"issue":"04","key":"7_CR18","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1017\/S0143385700008609","volume":"15","author":"A. Maass","year":"1995","unstructured":"Maass, A.: On the sofic limit sets of cellular automata. Ergodic Theory and Dynamical Systems\u00a015(04), 663\u2013684 (1995)","journal-title":"Ergodic Theory and Dynamical Systems"},{"issue":"04","key":"7_CR19","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1017\/S0143385707000855","volume":"28","author":"T. Meyerovitch","year":"2008","unstructured":"Meyerovitch, T.: Finite entropy for multidimensional cellular automata. Ergodic Theory and Dynamical Systems\u00a028(04), 1243\u20131260 (2008)","journal-title":"Ergodic Theory and Dynamical Systems"},{"issue":"4","key":"7_CR20","doi-asserted-by":"publisher","first-page":"489","DOI":"10.2748\/tmj\/1325886278","volume":"63","author":"S.G. Simpson","year":"2011","unstructured":"Simpson, S.G.: Mass problems associated with effectively closed sets. Tohoku Mathematical Journal\u00a063(4), 489\u2013517 (2011)","journal-title":"Tohoku Mathematical Journal"},{"issue":"4","key":"7_CR21","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/0218057","volume":"18","author":"K. \u010culik","year":"1989","unstructured":"\u010culik, K., Pachl, J., Yu, S.: On the limit sets of cellular automata. SIAM Journal on Computing\u00a018(4), 831\u2013842 (1989)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T21:48:39Z","timestamp":1597960119000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}