{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T14:57:25Z","timestamp":1760799445957},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,10,28]],"date-time":"2009-10-28T00:00:00Z","timestamp":1256688000000},"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":[[2011,2]]},"DOI":"10.1007\/s00224-009-9245-z","type":"journal-article","created":{"date-parts":[[2009,10,27]],"date-time":"2009-10-27T13:35:15Z","timestamp":1256650515000},"page":"297-318","source":"Crossref","is-referenced-by-count":1,"title":["Beta-Shifts, Their Languages, and Computability"],"prefix":"10.1007","volume":"48","author":[{"given":"Jakob Grue","family":"Simonsen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,10,28]]},"reference":[{"key":"9245_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0143385707000223","volume":"27","author":"B. Adamczewski","year":"2007","unstructured":"Adamczewski, B., Bugeaud, Y.: Dynamics for \u03b2-shifts and diophantine approximation. Ergod. Theory Dyn. Syst. 27, 1\u201317 (2007)","journal-title":"Ergod. Theory Dyn. Syst."},{"key":"9245_CR2","volume-title":"Fractals Everywhere","author":"M. Barnsley","year":"1993","unstructured":"Barnsley, M.: Fractals Everywhere. Morgan Kaufmann, San Mateo (1993)"},{"key":"9245_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/11549345_13","volume-title":"Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201905)","author":"V. Berth\u00e9","year":"2005","unstructured":"Berth\u00e9, V., Rigo, M.: Abstract numeration systems and tilings. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201905). Lecture Notes in Computer Science, vol.\u00a03618, pp. 131\u2013143. Springer, Berlin (2005)"},{"key":"9245_CR4","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61667-9","volume-title":"Constructive Analysis","author":"E. Bishop","year":"1985","unstructured":"Bishop, E., Bridges, D.: Constructive Analysis. Grundlehren der mathematischen Wissenschaften, vol.\u00a0279. Springer, Berlin (1985)"},{"key":"9245_CR5","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(89)90038-8","volume":"65","author":"F. Blanchard","year":"1989","unstructured":"Blanchard, F.: \u03b2-expansions and symbolic dynamics. Theor. Comput. Sci. 65, 131\u2013141 (1989)","journal-title":"Theor. Comput. Sci."},{"key":"9245_CR6","series-title":"London Mathematical Society Lecture Notes Series","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511565663","volume-title":"Varieties of Constructive Mathematics","author":"D. Bridges","year":"1987","unstructured":"Bridges, D., Richman, F.: Varieties of Constructive Mathematics. London Mathematical Society Lecture Notes Series, vol.\u00a097. Cambridge University Press, Cambridge (1987)"},{"key":"9245_CR7","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4171\/JEMS\/21","volume":"1","author":"K. Dajani","year":"2005","unstructured":"Dajani, K., de Vries, M.: Measures of maximal entropy for random \u03b2-expansions. J.\u00a0Eur. Math. Soc. 1, 51\u201368 (2005)","journal-title":"J.\u00a0Eur. Math. Soc."},{"key":"9245_CR8","series-title":"The Carus Mathematical Monographs","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440277","volume-title":"Ergodic Theory of Numbers","author":"K. Dajani","year":"2002","unstructured":"Dajani, K., Kraaikamp, C.: Ergodic Theory of Numbers. The Carus Mathematical Monographs, vol.\u00a029. The Mathematical Association of America, Washington (2002)"},{"issue":"2\u20133","key":"9245_CR9","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1016\/S0304-3975(02)00503-0","volume":"303","author":"C. Frougny","year":"2003","unstructured":"Frougny, C., Gazeau, J.-P., Krejcar, R.: Additive and multiplicative properties of point sets based on beta-integers. Theor. Comput. Sci. 303(2\u20133), 491\u2013516 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9245_CR10","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1017\/S0143385700007057","volume":"12","author":"C. Frougny","year":"1992","unstructured":"Frougny, C., Solomyak, B.: Finite beta-expansions. Ergod. Theory Dyn. Syst. 12, 713\u2013723 (1992)","journal-title":"Ergod. Theory Dyn. Syst."},{"key":"9245_CR11","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1109\/ARITH.2003.1207681","volume-title":"Proceedings of the 16th IEEE Symposium on Computer Arithmetic (ARITH 16)","author":"C. Frougny","year":"2003","unstructured":"Frougny, C., Surarerks, A.: On-line multiplication in real and complex base. In: Proceedings of the 16th IEEE Symposium on Computer Arithmetic (ARITH 16), pp. 212\u2013219. IEEE Comput. Soc., Los Alamitos (2003)"},{"key":"9245_CR12","series-title":"Lecture Notes in Computer Science","first-page":"515","volume-title":"Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201992)","author":"G. Hansel","year":"1992","unstructured":"Hansel, G., Perrin, D., Simon, I.: Compression and entropy. In: Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201992). Lecture Notes in Computer Science, vol.\u00a0577, pp. 515\u2013528. Springer, Berlin (1992)"},{"issue":"1\u20132","key":"9245_CR13","first-page":"141","volume":"83","author":"P. Hertling","year":"2008","unstructured":"Hertling, P., Spandl, C.: Computability theoretic properties of the entropy of gap shifts. Fundam. Inform. 83(1\u20132), 141\u2013157 (2008)","journal-title":"Fundam. Inform."},{"key":"9245_CR14","doi-asserted-by":"crossref","unstructured":"Hochman, M., Meyerovitch, T.: A characterization of the entropies of multidimensional shifts of finite type. Ann. Math. (2009, to appear)","DOI":"10.4007\/annals.2010.171.2011"},{"key":"9245_CR15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF01534862","volume":"85","author":"F. Hofbauer","year":"1978","unstructured":"Hofbauer, F.: \u03b2-shifts have unique maximal measure. Mon.hefte Math. 85, 189\u2013198 (1978)","journal-title":"Mon.hefte Math."},{"key":"9245_CR16","doi-asserted-by":"crossref","first-page":"33","DOI":"10.2969\/jmsj\/02610033","volume":"26","author":"S. Ito","year":"1974","unstructured":"Ito, S., Takashi, Y.: Markov subshifts and realization of \u03b2-expansions. J.\u00a0Math. Soc. Jpn. 26, 33\u201355 (1974)","journal-title":"J.\u00a0Math. Soc. Jpn."},{"key":"9245_CR17","unstructured":"Johnson, K.: Beta-shift dynamical systems and their associated languages. Ph.D. Thesis, University of North Carolina (1999)"},{"key":"9245_CR18","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2003.001.0001","volume-title":"Computability and Complexity from a Programming Perspective","author":"N. Jones","year":"1997","unstructured":"Jones, N.: Computability and Complexity from a Programming Perspective. The MIT Press, Cambridge (1997)"},{"key":"9245_CR19","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Theory of Computational Complexity","author":"K.-I. Ko","year":"2000","unstructured":"Ko, K.-I., Du, D.-Z.: Theory of Computational Complexity. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (2000)"},{"key":"9245_CR20","series-title":"Graduate Texts in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Graduate Texts in Computer Science. Springer, Berlin (1997)"},{"key":"9245_CR21","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1017\/S0143385700002443","volume":"4","author":"D. Lind","year":"1984","unstructured":"Lind, D.: The entropies of topological Markov shifts and a related class of algebraic integers. Ergod. Theory Dyn. Syst. 4, 283\u2013300 (1984)","journal-title":"Ergod. Theory Dyn. Syst."},{"key":"9245_CR22","doi-asserted-by":"crossref","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, Cambridge (1995)"},{"key":"9245_CR23","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1090\/S0002-9947-1921-1501161-8","volume":"22","author":"M. Morse","year":"1921","unstructured":"Morse, M.: Recurrent geodesics on a surface of negative curvature. Trans. Am. Math. Soc. 22, 84\u2013110 (1921)","journal-title":"Trans. Am. Math. Soc."},{"key":"9245_CR24","series-title":"Studies in Logic and the Foundations of Mathematics","volume-title":"Classical Recursion Theory, vol.\u00a0I","author":"P. Odifreddi","year":"1989","unstructured":"Odifreddi, P.: Classical Recursion Theory, vol.\u00a0I. Studies in Logic and the Foundations of Mathematics, vol.\u00a0129. North-Holland, Amsterdam (1989)"},{"key":"9245_CR25","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/BF02020954","volume":"11","author":"W. Parry","year":"1960","unstructured":"Parry, W.: On the \u03b2-expansion of real numbers. Acta Math. Acad. Sci. Hung. 11, 401\u2013416 (1960)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"9245_CR26","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/BF02020331","volume":"8","author":"A. R\u00e9nyi","year":"1957","unstructured":"R\u00e9nyi, A.: Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hung. 8, 477\u2013493 (1957)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"9245_CR27","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1987","unstructured":"Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. The MIT Press, Cambridge (1987). Paperback edition"},{"key":"9245_CR28","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1112\/blms\/12.4.269","volume":"12","author":"K. Schmidt","year":"1980","unstructured":"Schmidt, K.: On periodic expansions of Pisot numbers and Salem numbers. Bull. Lond. Math. Soc. 12, 269\u2013278 (1980)","journal-title":"Bull. Lond. Math. Soc."},{"key":"9245_CR29","doi-asserted-by":"crossref","first-page":"838","DOI":"10.2307\/3647804","volume":"110","author":"N. Sidorov","year":"2003","unstructured":"Sidorov, N.: Almost every number has a continuum of beta-expansions. Am. Math. Mon. 110, 838\u2013842 (2003)","journal-title":"Am. Math. Mon."},{"key":"9245_CR30","series-title":"London Mathematical Society Lecture Notes Series","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1017\/CBO9780511546716.010","volume-title":"Topics in Dynamics and Ergodic Theory","author":"N. Sidorov","year":"2003","unstructured":"Sidorov, N.: Arithmetic dynamics. In: Topics in Dynamics and Ergodic Theory. London Mathematical Society Lecture Notes Series, vol.\u00a0310, pp. 145\u2013189. London Mathematical Society, London (2003)"},{"key":"9245_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/11549345_65","volume-title":"Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005)","author":"J. Simonsen","year":"2005","unstructured":"Simonsen, J.: On beta-shifts having arithmetical languages. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005). Lecture Notes in Computer Science, vol.\u00a03618, pp. 757\u2013768. Springer, Berlin (2005)"},{"key":"9245_CR32","doi-asserted-by":"crossref","first-page":"83","DOI":"10.46298\/dmtcs.365","volume":"8","author":"J. Simonsen","year":"2006","unstructured":"Simonsen, J.: On the computability of the topological entropy of subshifts. Discrete Math. Theor. Comput. Sci. 8, 83\u201396 (2006)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"9245_CR33","unstructured":"Simonsen, J.: Beta-shifts, their languages and computability. Technical Report, Department of Computer Science, University of Copenhagen (DIKU) (2008)"},{"key":"9245_CR34","doi-asserted-by":"crossref","first-page":"4878","DOI":"10.1016\/j.tcs.2009.06.037","volume":"410","author":"J. Simonsen","year":"2009","unstructured":"Simonsen, J.: On the computational complexity of languages of general symbolic dynamical systems and beta-shifts. Theor. Comput. Sci. 410, 4878\u20134891 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9245_CR35","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/j.entcs.2006.08.011","volume":"167","author":"C. Spandl","year":"2007","unstructured":"Spandl, C.: Computing the topological entropy of shifts. Electr. Notes Theor. Comput. Sci. 167, 131\u2013155 (2007)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"9245_CR36","doi-asserted-by":"crossref","first-page":"145","DOI":"10.2307\/2267043","volume":"14","author":"E. Specker","year":"1949","unstructured":"Specker, E.: Nicht konstruktiv beweisbare S\u00e4tze der\u00a0Analysis. J.\u00a0Symb. Log. 14, 145\u2013158 (1949)","journal-title":"J.\u00a0Symb. Log."},{"key":"9245_CR37","first-page":"599","volume":"20","author":"Y. Takahashi","year":"1983","unstructured":"Takahashi, Y.: Shift with free orbit basis and realization of one-dimensional maps. Osaka J. Math. 20, 599\u2013629 (1983)","journal-title":"Osaka J. Math."},{"issue":"2","key":"9245_CR38","first-page":"230","volume":"42","author":"A. Turing","year":"1936","unstructured":"Turing, A.: On computable numbers with an application to the \u201centscheidungsproblem\u201d. Proc. Lond. Math. Soc. 42(2), 230\u2013265 (1936)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"2","key":"9245_CR39","first-page":"544","volume":"43","author":"A. Turing","year":"1937","unstructured":"Turing, A.: On computable numbers with an application to the \u201centscheidungsproblem\u201d. A\u00a0correction. Proc. Lond. Math. Soc. 43(2), 544\u2013546 (1937)","journal-title":"Proc. Lond. Math. Soc."},{"key":"9245_CR40","series-title":"Graduate Texts in Mathematics","volume-title":"An Introduction to Ergodic Theory","author":"P. Walters","year":"1981","unstructured":"Walters, P.: An Introduction to Ergodic Theory. Graduate Texts in Mathematics, vol.\u00a079. Springer, Berlin (1981)"},{"key":"9245_CR41","volume-title":"Computable Analysis: An\u00a0Introduction","author":"K. Weihrauch","year":"1998","unstructured":"Weihrauch, K.: Computable Analysis: An\u00a0Introduction. Springer, Berlin (1998)"},{"issue":"1","key":"9245_CR42","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1002\/1521-3870(200101)47:1<51::AID-MALQ51>3.0.CO;2-W","volume":"47","author":"X. Zheng","year":"2001","unstructured":"Zheng, X., Weihrauch, K.: The arithmetical hierarchy of real numbers. Math. Log.\u00a0Q. 47(1), 51\u201365 (2001)","journal-title":"Math. Log.\u00a0Q."},{"key":"9245_CR43","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.tcs.2004.06.022","volume":"326","author":"M. Ziegler","year":"2004","unstructured":"Ziegler, M., Brattka, V.: Computability in linear algebra. Theor. Comput. Sci. 326, 187\u2013211 (2004)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9245-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9245-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9245-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,12]],"date-time":"2021-10-12T22:55:06Z","timestamp":1634079306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9245-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10,28]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9245"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9245-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,10,28]]}}}