{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T18:01:10Z","timestamp":1710266470452},"reference-count":24,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T00:00:00Z","timestamp":1219795200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2008,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate computable subshifts and the connection with effective symbolic dynamics. It is shown that a decidable \u03a0<jats:sup>0<\/jats:sup><jats:sub>1<\/jats:sub> class <jats:italic>P<\/jats:italic> is a subshift if and only if there exists a computable function <jats:italic>F<\/jats:italic> mapping 2<jats:sup>\u2115<\/jats:sup> to 2<jats:sup>\u2115<\/jats:sup> such that <jats:italic>P<\/jats:italic> is the set of itineraries of elements of 2<jats:sup>\u2115<\/jats:sup>. \u03a0<jats:sup>0<\/jats:sup><jats:sub>1<\/jats:sub> subshifts are constructed in 2<jats:sup>\u2115<\/jats:sup> and in 2<jats:sup>\u2124<\/jats:sup> which have no computable elements. We also consider the symbolic dynamics of maps on the unit interval. (\u00a9 2008 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200710066","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T09:57:26Z","timestamp":1219831046000},"page":"460-469","source":"Crossref","is-referenced-by-count":11,"title":["Computable symbolic dynamics"],"prefix":"10.1002","volume":"54","author":[{"given":"Douglas","family":"Cenzer","sequence":"first","affiliation":[]},{"given":"S. Ali","family":"Dashti","sequence":"additional","affiliation":[]},{"given":"Jonathan L. F.","family":"King","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2008,8,27]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"318","article-title":"Computing over the reals: foundations for scientific computing","volume":"53","author":"Braverman M.","year":"2006","journal-title":"Notices Amer. Math. Soc."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-05-00516-3"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"D.Cenzer Effective dynamics. In: Logical Methods in Honor of Anil Nerode's Sixtieth Birthday (J. Crossley J. Remmel R. Shore and M. Sweedler eds.) pp. 162\u2013177 (Birkh\u00e4user 1993).","DOI":"10.1007\/978-1-4612-0325-4_5"},{"key":"e_1_2_1_5_2","unstructured":"D.Cenzer \u03a001classes in computability theory. In: Handbook of Recursion Theory (E. Griffor ed.). Studies in Logic and Foundations of Mathematics 140 pp. 37\u201385 (North\u2010Holland 1999)."},{"key":"e_1_2_1_6_2","unstructured":"D.Cenzer S. A.Dashti andJ. L. F.King Effective symbolic dynamics. In: CCA 2007 (Computability and Complexity in Analysis Siena June 2007) (R. Dillhage T. Grubb A. Sorbi K. Weihrauch and N. Zhong eds.). Informatik Berichte Universit\u00e4t Hagen 79\u201389 (2007)and"},{"key":"e_1_2_1_6_3","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.03.010"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00069-X"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"D.Cenzer andJ. B.Remmel \u03a001classes in mathematics. In: Recursive Mathematics (Y. Ersov S. Goncharov A. Nerode and J. B. Remmel eds.). Studies in Logic and Foundations of Mathematics 138 pp. 623\u2013821 (North\u2010Holland 1998).","DOI":"10.1016\/S0049-237X(98)80046-3"},{"key":"e_1_2_1_9_2","unstructured":"D.Cenzer andJ. B.Remmel Effectively closed sets. To appear in Association for Symbolic Logic Lecture Notes."},{"key":"e_1_2_1_10_2","unstructured":"P.Collet andJ. P.Eckmann Iterated Maps On The Interval As Dynamical Systems (Birkh\u00e4user 1980)."},{"key":"e_1_2_1_11_2","unstructured":"J.\u2010C.Delvenne Dynamics information and computation. Ph. D. thesis Universit\u00e9 Catholique de Louvain (2005)."},{"key":"e_1_2_1_12_2","first-page":"463","article-title":"Decidability and universality in symbolic dynamical systems","volume":"74","author":"Delvenne J.\u2010C.","year":"2006","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_1_13_2","unstructured":"R. L.Devaney An Introduction to Chaotic Dynamical Systems (Addison\u2010Wesley 1995)."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.4064\/fm-44-1-61-71","article-title":"On the definitions of computable real continuous functions","volume":"44","author":"Grzegorczyk A.","year":"1957","journal-title":"Fund. Math."},{"key":"e_1_2_1_15_2","first-page":"625","article-title":"Applications of pure recursion theory to recursive analysis","volume":"28","author":"Huang W.","year":"1985","journal-title":"Acta Sinica"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"K.Ko Complexity Theory of Real Functions (Birkh\u00e4user 1991).","DOI":"10.1007\/978-1-4684-6802-1"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00060-2"},{"key":"e_1_2_1_18_2","first-page":"2478","article-title":"Extension de la notion de fonction r\u00e9cursive aux fonctions d'une ou plusieurs variables r\u00e9elles","volume":"241","author":"Lacombe D.","year":"1955","journal-title":"Comptes Rendus Acad. Sci. Paris"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","unstructured":"D.Lind andB.Marcus An Introduction to Symbolic Dynamics and Coding (Cambridge University Press 1995).","DOI":"10.1017\/CBO9780511626302"},{"key":"e_1_2_1_20_2","unstructured":"M.Lothaire Combinatorics on Words (Addison\u2010Wesley 1983)."},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(73)90033-2"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","unstructured":"R.Rettinger andK.Weihrauch The computational complexity of some Julia sets. In: Proc. 35th ACM Symposium on Theory of Computing (San Diego June 2003) (M. X. Goemans ed.) pp. 177\u2013185 (ACM Press 2003).","DOI":"10.1145\/780542.780570"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"K.Weihrauch Computable Analysis (Springer 2000).","DOI":"10.1007\/978-3-642-56999-9"},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","unstructured":"H.Xie Grammatical Complexity and One\u2010Dimensional Dynamical Systems (World Scientific 1996).","DOI":"10.1142\/2877"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200710066","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200710066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,14]],"date-time":"2023-09-14T00:05:36Z","timestamp":1694649936000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200710066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,27]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,9]]}},"alternative-id":["10.1002\/malq.200710066"],"URL":"https:\/\/doi.org\/10.1002\/malq.200710066","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8,27]]}}}