Distribution modulo 1 and the lexicographic world
We give a complete description of the minimal intervals containing all fractional parts $\{ξ2^n\}$, for some positive real number $ξ$, and for all $n \geq 0$.
Researcher profile
Amy Glen
Amy Glen contributes to research discovery and scholarly infrastructure.
ResearcherAffiliation not importedOpen to collaborate
Trust snapshot
Quick read
Trust 21 - EmergingVerification L1Unclaimed author
16works
0followers
3topics
4close collaborators
Actions
Decide how to stay connected
Identity and collaboration
How to connect with this researcher
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Open a focused conversation when the fit is right
Claim this author entity first to unlock direct invitations.
Research graph
See the researcher in context
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
Building this graph slice
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
16 published item(s)
preprint2009arXiv
Extremal properties of (epi)Sturmian sequences and distribution modulo 1
Starting from a study of Y. Bugeaud and A. Dubickas (2005) on a question in distribution of real numbers modulo 1 via combinatorics on words, we survey some combinatorial properties of (epi)Sturmian sequences and distribution modulo 1 in connection to their work. In particular we focus on extremal properties of (epi)Sturmian sequences, some of which have been rediscovered several times.
0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv
A connection between palindromic and factor complexity using return words
In this paper we prove that for any infinite word W whose set of factors is closed under reversal, the following conditions are equivalent: (I) all complete returns to palindromes are palindromes; (II) P(n) + P(n+1) = C(n+1) - C(n) + 2 for all n, where P (resp. C) denotes the palindromic complexity (resp. factor complexity) function of W, which counts the number of distinct palindromic factors (resp. factors) of each length in W.
0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv
A new characteristic property of rich words
Originally introduced and studied by the third and fourth authors together with J. Justin and S. Widmer in arXiv:0801.1656, rich words constitute a new class of finite and infinite words characterized by containing the maximal number of distinct palindromes. Several characterizations of rich words have already been established. A particularly nice characteristic property is that all 'complete returns' to palindromes are palindromes. In this note, we prove that rich words are also characterized by the property that each factor is uniquely determined by its longest palindromic prefix and its longest palindromic suffix.
0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv
Crucial words for abelian powers
A word is "crucial" with respect to a given set of "prohibited words" (or simply "prohibitions") if it avoids the prohibitions but it cannot be extended to the right by any letter of its alphabet without creating a prohibition. A "minimal crucial word" is a crucial word of the shortest length. A word W contains an "abelian k-th power" if W has a factor of the form X_1X_2...X_k where X_i is a permutation of X_1 for 2<= i <= k. When k=2 or 3, one deals with "abelian squares" and "abelian cubes", respectively. In 2004 (arXiv:math/0205217), Evdokimov and Kitaev showed that a minimal crucial word over an n-letter alphabet A_n = {1,2,..., n} avoiding abelian squares has length 4n-7 for n >= 3. In this paper we show that a minimal crucial word over A_n avoiding abelian cubes has length 9n-13 for n >= 5, and it has length 2, 5, 11, and 20 for n=1, 2, 3, and 4, respectively. Moreover, for n >= 4 and k >= 2, we give a construction of length k^2(n-1)-k-1 of a crucial word over A_n avoiding abelian k-th powers. This construction gives the minimal length for k=2 and k=3. For k >= 4 and n >= 5, we provide a lower bound for the length of crucial words over A_n avoiding abelian k-th powers.
0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv
Directive words of episturmian words: equivalences and normalization
Episturmian morphisms constitute a powerful tool to study episturmian words. Indeed, any episturmian word can be infinitely decomposed over the set of pure episturmian morphisms. Thus, an episturmian word can be defined by one of its morphic decompositions or, equivalently, by a certain directive word. Here we characterize pairs of words directing a common episturmian word. We also propose a way to uniquely define any episturmian word through a normalization of its directive words. As a consequence of these results, we characterize episturmian words having a unique directive word.
0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv
Episturmian words: a survey
In this paper, we survey the rich theory of infinite episturmian words which generalize to any finite alphabet, in a rather resembling way, the well-known family of Sturmian words on two letters. After recalling definitions and basic properties, we consider episturmian morphisms that allow for a deeper study of these words. Some properties of factors are described, including factor complexity, palindromes, fractional powers, frequencies, and return words. We also consider lexicographical properties of episturmian words, as well as their connection to the balance property, and related notions such as finite episturmian words, Arnoux-Rauzy sequences, and "episkew words" that generalize the skew words of Morse and Hedlund.
0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv
Palindromic Richness
In this paper, we study combinatorial and structural properties of a new class of finite and infinite words that are 'rich' in palindromes in the utmost sense. A characteristic property of so-called "rich words" is that all complete returns to any palindromic factor are themselves palindromes. These words encompass the well-known episturmian words, originally introduced by the second author together with X. Droubay and G. Pirillo in 2001. Other examples of rich words have appeared in many different contexts. Here we present the first unified approach to the study of this intriguing family of words. Amongst our main results, we give an explicit description of the periodic rich infinite words and show that the recurrent balanced rich infinite words coincide with the balanced episturmian words. We also consider two wider classes of infinite words, namely "weakly rich words" and almost rich words (both strictly contain all rich words, but neither one is contained in the other). In particular, we classify all recurrent balanced weakly rich words. As a consequence, we show that any such word on at least three letters is necessarily episturmian; hence weakly rich words obey Fraenkel's conjecture. Likewise, we prove that a certain class of almost rich words obeys Fraenkel's conjecture by showing that the recurrent balanced ones are episturmian or contain at least two distinct letters with the same frequency. Lastly, we study the action of morphisms on (almost) rich words with particular interest in morphisms that preserve (almost) richness. Such morphisms belong to the class of "P-morphisms" that was introduced by A. Hof, O. Knill, and B. Simon in 1995.
0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv
Quasiperiodic and Lyndon episturmian words
Recently the second two authors characterized quasiperiodic Sturmian words, proving that a Sturmian word is non-quasiperiodic if and only if it is an infinite Lyndon word. Here we extend this study to episturmian words (a natural generalization of Sturmian words) by describing all the quasiperiods of an episturmian word, which yields a characterization of quasiperiodic episturmian words in terms of their "directive words". Even further, we establish a complete characterization of all episturmian words that are Lyndon words. Our main results show that, unlike the Sturmian case, there is a much wider class of episturmian words that are non-quasiperiodic, besides those that are infinite Lyndon words. Our key tools are morphisms and directive words, in particular "normalized" directive words, which we introduced in an earlier paper. Also of importance is the use of "return words" to characterize quasiperiodic episturmian words, since such a method could be useful in other contexts.
0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv
Rich, Sturmian, and trapezoidal words
In this paper we explore various interconnections between rich words, Sturmian words, and trapezoidal words. Rich words, first introduced in arXiv:0801.1656 by the second and third authors together with J. Justin and S. Widmer, constitute a new class of finite and infinite words characterized by having the maximal number of palindromic factors. Every finite Sturmian word is rich, but not conversely. Trapezoidal words were first introduced by the first author in studying the behavior of the subword complexity of finite Sturmian words. Unfortunately this property does not characterize finite Sturmian words. In this note we show that the only trapezoidal palindromes are Sturmian. More generally we show that Sturmian palindromes can be characterized either in terms of their subword complexity (the trapezoidal property) or in terms of their palindromic complexity. We also obtain a similar characterization of rich palindromes in terms of a relation between palindromic complexity and subword complexity.
0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv
A characterization of fine words over a finite alphabet
To any infinite word w over a finite alphabet A we can associate two infinite words min(w) and max(w) such that any prefix of min(w) (resp. max(w)) is the lexicographically smallest (resp. greatest) amongst the factors of w of the same length. We say that an infinite word w over A is "fine" if there exists an infinite word u such that, for any lexicographic order, min(w) = au where a = min(A). In this paper, we characterize fine words; specifically, we prove that an infinite word w is fine if and only if w is either a "strict episturmian word" or a strict "skew episturmian word''. This characterization generalizes a recent result of G. Pirillo, who proved that a fine word over a 2-letter alphabet is either an (aperiodic) Sturmian word, or an ultimately periodic (but not periodic) infinite word, all of whose factors are (finite) Sturmian.
0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv
Characterizations of finite and infinite episturmian words via lexicographic orderings
In this paper, we characterize by lexicographic order all finite Sturmian and episturmian words, i.e., all (finite) factors of such infinite words. Consequently, we obtain a characterization of infinite episturmian words in a "wide sense" (episturmian and episkew infinite words). That is, we characterize the set of all infinite words whose factors are (finite) episturmian. Similarly, we characterize by lexicographic order all balanced infinite words over a 2-letter alphabet; in other words, all Sturmian and skew infinite words, the factors of which are (finite) Sturmian.
0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv
Conjugates of characteristic Sturmian words generated by morphisms
This article is concerned with characteristic Sturmian words of slope $α$ and $1-α$ (denoted by $c_α$ and $c_{1-α}$ respectively), where $α\in (0,1)$ is an irrational number such that $α= [0;1+d_1,\bar{d_2,...,d_n}]$ with $d_n \geq d_1 \geq 1$. It is known that both $c_α$ and $c_{1-α}$ are fixed points of non-trivial (standard) morphisms $σ$ and $\hatσ$, respectively, if and only if $α$ has a continued fraction expansion as above. Accordingly, such words $c_α$ and $c_{1-α}$ are generated by the respective morphisms $σ$ and $\hatσ$. For the particular case when $α= [0;2,\bar{r}]$ ($r\geq1$), we give a decomposition of each conjugate of $c_α$ (and hence $c_{1-α}$) into generalized adjoining singular words, by considering conjugates of powers of the standard morphism $σ$ by which it is generated. This extends a recent result of Levé and S\ee bold on conjugates of the infinite Fibonacci word.
0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv
Occurrences of palindromes in characteristic Sturmian words
This paper is concerned with palindromes occurring in characteristic Sturmian words $c_α$ of slope $α$, where $α\in (0,1)$ is an irrational. As $c_α$ is a uniformly recurrent infinite word, any (palindromic) factor of $c_α$ occurs infinitely many times in $c_α$ with bounded gaps. Our aim is to completely describe where palindromes occur in $c_α$. In particular, given any palindromic factor $u$ of $c_α$, we shall establish a decomposition of $c_α$ with respect to the occurrences of $u$. Such a decomposition shows precisely where $u$ occurs in $c_α$, and this is directly related to the continued fraction expansion of $α$.
0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv
On the critical exponent of generalized Thue-Morse words
For certain generalized Thue-Morse words t, we compute the "critical exponent", i.e., the supremum of the set of rational numbers that are exponents of powers in t, and determine exactly the occurrences of powers realizing it.
0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv
Powers in a class of A-strict standard episturmian words
This paper concerns a specific class of strict standard episturmian words whose directive words resemble those of characteristic Sturmian words. In particular, we explicitly determine all integer powers occurring in such infinite words, extending recent results of Damanik and Lenz (2003), who studied powers in Sturmian words. The key tools in our analysis are canonical decompositions and a generalization of singular words, which were originally defined for the ubiquitous Fibonacci word. Our main results are demonstrated via some examples, including the $k$-bonacci word: a generalization of the Fibonacci word to a $k$-letter alphabet ($k\geq2$).
0 citations0 reviewsNo code linkedOpen access