Search results for "Sturmian"

Sturmian words and overexponential codimension growth

2018

Abstract Let A be a non necessarily associative algebra over a field of characteristic zero satisfying a non-trivial polynomial identity. If A is a finite dimensional algebra or an associative algebra, it is known that the sequence c n ( A ) , n = 1 , 2 , … , of codimensions of A is exponentially bounded. If A is an infinite dimensional non associative algebra such sequence can have overexponential growth. Such phenomenon is present also in the case of Lie or Jordan algebras. In all known examples the smallest overexponential growth of c n ( A ) is ( n ! ) 1 2 . Here we construct a family of algebras whose codimension sequence grows like ( n ! ) α , for any real number α with 0 α 1 .

On Balancing of a Direct Product

2009

A direct product of two sequences is a naturally defined sequence on the alphabet of pairs of symbols. By taking inspiration from [Pavel Salimov. On uniform recurrence of a direct product. In AutoMathA, 2009], where the author investigates the case of uniformly recurrent words, here, we study when the product of two balanced sequences on binary alphabet is also balanced.

Burrows–Wheeler transform and Sturmian words

2003

Balance Properties and Distribution of Squares in Circular Words

2008

We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalised to non periodic infinite words as well.

A Characterization of Bispecial Sturmian Words

2012

A finite Sturmian word w over the alphabet {a,b} is left special (resp. right special) if aw and bw (resp. wa and wb) are both Sturmian words. A bispecial Sturmian word is a Sturmian word that is both left and right special. We show as a main result that bispecial Sturmian words are exactly the maximal internal factors of Christoffel words, that are words coding the digital approximations of segments in the Euclidean plane. This result is an extension of the known relation between central words and primitive Christoffel words. Our characterization allows us to give an enumerative formula for bispecial Sturmian words. We also investigate the minimal forbidden words for the set of Sturmian wo…

STURMIAN WORDS AND AMBIGUOUS CONTEXT-FREE LANGUAGES

1990

If x is a rational number, 0<x≤1, then A(x)c is a context-free language, where A(x) is the set of factors of the infinite Sturmian words with asymptotic density of 1’s smaller than or equal to x. We also prove a “gap” theorem i.e. A(x) can never be an unambiguous co-context-free language. The “gap” theorem is established by proving that the counting generating function of A(x) is transcendental. We show some links between Sturmian words, combinatorics and number theory.

Words and forbidden factors

2002

AbstractGiven a finite or infinite word v, we consider the set M(v) of minimal forbidden factors of v. We show that the set M(v) is of fundamental importance in determining the structure of the word v. In the case of a finite word w we consider two parameters that are related to the size of M(w): the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. We derive sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of the word w. We are further interested to the algorithmic point of view. Indeed, we design linear time algorithm for the following two p…

A Note on a Conjecture of Duval and Sturmian Words

2002

We prove a long standing conjecture of Duval in the special case of Sturmian words. Mathematics Subject Classication. ??????????????. Let U be a nonempty word on a nite alphabet A: A nonempty word B dierent from U is called a border of U if B is both a prex and sux of U: We say U is bordered if U admits a border, otherwise U is said to be unbordered. For example, U = 011001011 is bordered by the factor 011; while 00010001001 is unbordered. An integer 1 k n is a period of a word U = U1 :::U n if and only if for all 1 i n k we have Ui = Ui+k. It is easy to see that k is a period of U if and only if the prex B of U of length n k is a border of U or is empty. Let (U) denote the smallest period …

Characteristic Sturmian words are extremal for the Critical Factorization Theorem

2012

We prove that characteristic Sturmian words are extremal for the Critical Factorization Theorem (CFT) in the following sense. If p x ( n ) denotes the local period of an infinite word x at point n , we prove that x is a characteristic Sturmian word if and only if p x ( n ) is smaller than or equal to n + 1 for all n ≥ 1 and it is equal to n + 1 for infinitely many integers n . This result is extremal with respect to the \{CFT\} since a consequence of the \{CFT\} is that, for any infinite recurrent word x, either the function p x is bounded, and in such a case x is periodic, or p x ( n ) ≥ n + 1 for infinitely many integers n . As a byproduct of the techniques used in the paper we extend a r…

On Sturmian Graphs

2007

AbstractIn this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.