{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T18:06:36Z","timestamp":1710266796133},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,9,13]],"date-time":"2011-09-13T00:00:00Z","timestamp":1315872000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1007\/s00224-011-9358-z","type":"journal-article","created":{"date-parts":[[2011,9,12]],"date-time":"2011-09-12T04:21:39Z","timestamp":1315801299000},"page":"352-371","source":"Crossref","is-referenced-by-count":5,"title":["Computability of Countable Subshifts in One Dimension"],"prefix":"10.1007","volume":"51","author":[{"given":"Douglas","family":"Cenzer","sequence":"first","affiliation":[]},{"given":"Ali","family":"Dashti","sequence":"additional","affiliation":[]},{"given":"Ferit","family":"Toska","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Wyman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,9,13]]},"reference":[{"key":"9358_CR1","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1016\/S0304-3975(96)00086-2","volume":"168","author":"O. Bournez","year":"1996","unstructured":"Bournez, O., Cosnard, M.: On the computational power of dynamical systems and hybrid systems. Theor. Comput. Sci. 168, 417\u2013459 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"9358_CR2","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1090\/S0894-0347-05-00516-3","volume":"19","author":"M. Braverman","year":"2006","unstructured":"Braverman, M., Yampolsky, M.: Non-computable Julia sets. J. Am. Math. Soc. 19, 551\u2013578 (2006)","journal-title":"J. Am. Math. Soc."},{"key":"9358_CR3","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/978-1-4612-0325-4_5","volume-title":"Logical Methods in Honor of Anil Nerode\u2019s Sixtieth Birthday","author":"D. Cenzer","year":"1993","unstructured":"Cenzer, D.: Effective dynamics. In: Crossley, J., Remmel, J., Shore, R., Sweedler, M. (eds.) Logical Methods in Honor of Anil Nerode\u2019s Sixtieth Birthday, pp. 162\u2013177. Birkh\u00e4user, Basel (1993)"},{"key":"9358_CR4","series-title":"Elsevier Studies in Logic","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/S0049-237X(99)80018-4","volume-title":"Handbook of Computability Theory","author":"D. Cenzer","year":"1999","unstructured":"Cenzer, D.: $\\Pi^{0}_{1}$ classes in computability theory. In: Griffor, E. (ed.) Handbook of Computability Theory. Elsevier Studies in Logic, vol. 140, pp. 37\u201385 (1999)"},{"key":"9358_CR5","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0168-0072(86)90067-9","volume":"31","author":"D. Cenzer","year":"1986","unstructured":"Cenzer, D., Clote, P., Smith, R., Soare, R., Wainer, S.: Members of countable $\\Pi^{0}_{1}$ classes. Ann. Pure Appl. Log. 31, 145\u2013163 (1986)","journal-title":"Ann. Pure Appl. Log."},{"key":"9358_CR6","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1002\/malq.200710066","volume":"54","author":"D. Cenzer","year":"2008","unstructured":"Cenzer, D., Dashti, A., King, J.L.F.: Computable symbolic dynamics. Math. Log. Q. 54, 524\u2013533 (2008)","journal-title":"Math. Log. Q."},{"key":"9358_CR7","series-title":"Springer Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/978-3-642-13962-8_10","volume-title":"Programs, Proofs and Processes, CIE 2010","author":"D. Cenzer","year":"2010","unstructured":"Cenzer, D., Dashti, A., Toska, F., Wyman, S.: Computability of countable shifts. In: Ferreira, F., et al. (eds.) Programs, Proofs and Processes, CIE 2010. Springer Lecture Notes in Computer Science, vol. 6158, pp. 88\u201397 (2010)"},{"key":"9358_CR8","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0168-0072(93)90001-T","volume":"59","author":"D. Cenzer","year":"1993","unstructured":"Cenzer, D., Downey, R., Jockusch, C.G., Shore, R.: Countable thin $\\Pi^{0}_{1}$ classes. Ann. Pure Appl. Log. 59, 79\u2013139 (1993)","journal-title":"Ann. Pure Appl. Log."},{"key":"9358_CR9","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1007\/s00153-007-0058-y","volume":"45","author":"D. Cenzer","year":"2008","unstructured":"Cenzer, D., Hinman, P.G.: Degrees of difficulty of generalized r.e. separating classes. Arch. Math. Log. 45, 629\u2013647 (2008)","journal-title":"Arch. Math. Log."},{"key":"9358_CR10","series-title":"Elsevier Studies in Logic and the Foundations of Mathematics","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1016\/S0049-237X(98)80046-3","volume-title":"Handbook of Recursive Mathematics, Vol. 2: Recursive Algebra, Analysis and Combinatorics","author":"D. Cenzer","year":"1998","unstructured":"Cenzer, D., Remmel, J.B.: $\\Pi^{0}_{1}$ classes. In: Ersov, Y., Goncharov, S., Marek, V., Nerode, A., Remmel, J. (eds.) Handbook of Recursive Mathematics, Vol. 2: Recursive Algebra, Analysis and Combinatorics. Elsevier Studies in Logic and the Foundations of Mathematics, vol. 139, pp. 623\u2013821 (1998)"},{"key":"9358_CR11","doi-asserted-by":"crossref","first-page":"975","DOI":"10.2307\/2274757","volume":"54","author":"D. Cenzer","year":"1989","unstructured":"Cenzer, D., Smith, R.: The ranked points of a $\\Pi^{0}_{1}$ set. J. Symb. Log. 54, 975\u2013991 (1989)","journal-title":"J. Symb. Log."},{"key":"9358_CR12","first-page":"463","volume":"74","author":"J.-C. Delvenne","year":"2006","unstructured":"Delvenne, J.-C., Kurka, P., Blondel, V.: Decidability and universality in symbolic dynamical systems. Fundam. Inform. 74, 463\u2013490 (2006)","journal-title":"Fundam. Inform."},{"key":"9358_CR13","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s00222-008-0161-7","volume":"176","author":"M. Hochman","year":"2009","unstructured":"Hochman, M.: On the dynamics and recursive properties of multidimensional symbolic systems. Invent. Math. 176, 131\u2013167 (2009)","journal-title":"Invent. Math."},{"key":"9358_CR14","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0168-0072(97)00060-2","volume":"93","author":"K. Ko","year":"1998","unstructured":"Ko, K.: On the computability of fractal dimensions and Julia sets. Ann. Pure Appl. Log. 93, 195\u2013216 (1998)","journal-title":"Ann. Pure Appl. Log."},{"key":"9358_CR15","series-title":"Encyclopedia of Math. and its Appl.","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M. Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Math. and its Appl., vol.\u00a090. Cambridge University Press, Cambridge (2002)"},{"key":"9358_CR16","first-page":"501","volume":"104","author":"Y. Medvedev","year":"1955","unstructured":"Medvedev, Y.: Degrees of difficulty of the mass problem. Dokl. Akad. Nauk SSSR 104, 501\u2013504 (1955)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"9358_CR17","unstructured":"Miller, J.: Two notes on subshifts. Proc. Am. Math. Soc. (to appear)"},{"key":"9358_CR18","first-page":"177","volume-title":"Proc. 35th ACM Symposium on Theory of Computing","author":"R. Rettinger","year":"2003","unstructured":"Rettinger, R., Weihrauch, K.: The computational complexity of some Julia sets. In: Goemans, M.X. (ed.) Proc. 35th ACM Symposium on Theory of Computing, San Diego, June 2003, pp. 177\u2013185. ACM, New York (2003)"},{"key":"9358_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2178\/bsl\/1107959497","volume":"11","author":"S.G. Simpson","year":"2005","unstructured":"Simpson, S.G.: Mass problems and randomness. Bull. Symb. Log. 11, 1\u201327 (2005)","journal-title":"Bull. Symb. Log."},{"key":"9358_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581007","volume-title":"Subsystems of Second Order Arithmetic","author":"S.G. Simpson","year":"2009","unstructured":"Simpson, S.G.: Subsystems of Second Order Arithmetic, 2nd edn. Cambridge University Press, Cambridge (2009)","edition":"2"},{"key":"9358_CR21","unstructured":"Simpson, S.G.: Medvedev degrees of two-dimensional subshifts of finite type. Ergod. Theory Dyn. Syst. (to appear)"},{"key":"9358_CR22","series-title":"London Mathematical Society Lecture Notes","isbn-type":"print","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1017\/CBO9780511629167.015","volume-title":"Computability, Enumerability, Unsolvability: Directions in Recursion Theory","author":"A. Sorbi","year":"1996","unstructured":"Sorbi, A.: The Medvedev lattice of degrees of difficulty. In: Cooper, S.B., et al. (eds.) Computability, Enumerability, Unsolvability: Directions in Recursion Theory. London Mathematical Society Lecture Notes, vol. 224, pp. 289\u2013312. Cambridge University Press, Cambridge (1996). ISBN 0-521-55736-4","ISBN":"http:\/\/id.crossref.org\/isbn\/0521557364"},{"key":"9358_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56999-9","volume-title":"Computable Analysis","author":"K. Weihrauch","year":"2000","unstructured":"Weihrauch, K.: Computable Analysis. Springer, Berlin (2000)"},{"key":"9358_CR24","unstructured":"Jeandal, E., Vanier, P.: Turing degrees of multidimensional SFTs. arXiv:1108.1012v1"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9358-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9358-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9358-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,15]],"date-time":"2019-06-15T09:58:20Z","timestamp":1560592700000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9358-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,13]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["9358"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9358-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,13]]}}}