zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Sturmian graphs and integer representations over numeration systems. (English) Zbl 1237.68134
Summary: We consider a numeration system, originally due to Ostrowski, based on the continued fraction expansion of a real number α. We prove that this system has deep connections with the Sturmian graph associated with α. We provide several properties of the representations of the natural integers in this system. In particular, we prove that the set of lazy representations of the natural integers in this numeration system is regular if and only if the continued fraction expansion of α is eventually periodic. The main result of the paper is that for any number i the unique path weighted i in the Sturmian graph associated with α represents the lazy representation of i in the Ostrowski numeration system associated with α.

MSC:
11A67Representation systems for integers and rationals
05C75Structural characterization of families of graphs
05C90Applications of graph theory
68R15Combinatorics on words
References:
[1]Allouche, J. -P.; Shallit, J.: Automatic sequences: theory, applications, generalizations, (2003)
[2]Baturo, P.; Piatkowski, M.; Rytter, W.: Usefulness of directed acyclic subword graphs in problems related to standard Sturmian words, The international journal of foundations of computer science 20, No. 6, 1005-1023 (2009) · Zbl 1187.68357 · doi:10.1142/S0129054109007017
[3]Berstel, J.: Sturmian and episturmian words (a survey of some recent results), Lecture notes in computer science 4728, 23-47 (2007) · Zbl 1149.68065 · doi:10.1007/978-3-540-75414-5_2
[4]Berthé, V.: Autour du système de numération d’ostrowski, Bulletin of the belgian mathematical society–Simon stevin 8, 209-239 (2001) · Zbl 0994.68100
[5]Brezinski, C.: History of continued fractions and Padé approximants, Springer series in computational mathematics 12 (1991) · Zbl 0714.01001
[6]Dajani, K.; Kraaikamp, C.: From greedy to lazy expansions and their driving dynamics, Expositiones mathematicae 20, 315-327 (2002) · Zbl 1030.11035 · doi:10.1016/S0723-0869(02)80010-X
[7]De Luca, A.; Mignosi, F.: Some combinatorial properties of Sturmian words, Theoretical computer science 136, 361-385 (1994) · Zbl 0874.68245 · doi:10.1016/0304-3975(94)00035-H
[8]Epifanio, C.; Mignosi, F.; Shallit, J.; Venturini, I.: On Sturmian graphs, Discrete applied mathematics 155, No. 8, 1014-1030 (2007) · Zbl 1115.68121 · doi:10.1016/j.dam.2006.11.003
[9]Erdos, P.; Joó, I.; Komornik, V.: Characterization of the unique expansions 1=i=1q-ni, and related problems, Bulletin de la société mathématique de France 118, 377-390 (1990) · Zbl 0721.11005 · doi:numdam:BSMF_1990__118_3_377_0
[10]Frougny, Ch.; Sakarovitch, J.: Number representation and finite automata, Encyclopedia of mathematics and its applications 135 (2010) · Zbl 1216.68142
[11]Hardy, G. H.; Wright, E. M.: An introduction to the theory of numbers, (1989)
[12]Klette, R.; Rosenfeld, A.: Digital straightness–a review, Discrete applied mathematics 139, No. 1–3, 197-230 (2004) · Zbl 1093.68656 · doi:10.1016/j.dam.2002.12.001
[13]Loraud, N.: β-shift, systèmes de numération et automates, Journal de théorie des nombres de Bordeaux 7, 473-498 (1995) · Zbl 0843.11013 · doi:10.5802/jtnb.153 · doi:emis:journals/JTNB/1995-2/jtnb7-2.html · doi:numdam:JTNB_1995__7_2_473_0
[14]Lothaire, M.: Algebraic combinatorics on words, Encyclopedia of mathematics and its applications 90 (2002) · Zbl 1001.68093
[15]Ostrowski, A.: Bemerkungen zur theorie der diophantischen approximationen I, II, Abhandlungen aus dem mathematischen seminar der universität Hamburg 1, 77-98 (1922) · Zbl 48.0197.04
[16]Perron, O.: Die lehre von den kettenbrüchen, (1954) · Zbl 0056.05901
[17]Rauzy, G.: Mots infinis en arithmétique, Lecture notes in computer science 192, 165-171 (1985) · Zbl 0613.10044
[18]Rytter, W.: The structure of subword graphs and suffix trees of Fibonacci words, Theoretical computer science 363, No. 2, 211-223 (2006) · Zbl 1153.68044 · doi:10.1016/j.tcs.2006.07.025
[19]Shallit, J.: Real numbers with bounded partial quotients, L’enseignement mathématique 38, 151-187 (1992) · Zbl 0753.11006
[20]Shallit, J.: Numeration systems, linear recurrences, and regular sets, Information and computation 113, 331-347 (1994) · Zbl 0810.11006 · doi:10.1006/inco.1994.1076