In this article, we study the complexity of drunken man infinite words. We show that these infinite words, generated by a deterministic and complete countable automaton, or equivalently generated by a substitution over a countable alphabet of constant length, have complexity functions equivalent to n(log2n)2 when n goes to infinity.
This survey aims at giving a consistent presentation of numeration from a dynamical viewpoint: we focus on numeration systems, their associated compactification, and dynamical systems that can be naturally defined on them. The exposition is unified by the fibred numeration system concept. Many examples are discussed. Various numerations on rational integers, real or complex numbers are presented with special attention paid to -numeration and its generalisations, abstract numeration systems and...
On appelle échange d’intervalles l’application qui consiste à réordonner les intervalles d’une partition de suivant une permutation donnée. Dans le cas des partitions en trois intervalles, nous donnons une caractérisation combinatoire des suites codant, d’après la partition définissant l’échange, l’orbite d’un point de sous l’action de cette transformation.
We present an on-line linear time and space algorithm to check if an integer array is the border array of at least one string built on a bounded or unbounded size alphabet . First of all, we show a bijection between the border array of a string and the skeleton of the DFA recognizing , called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a skeleton of SMA...
We present an on-line linear time and space algorithm to check if an integer array f is the border array of at least one string w built on a bounded or unbounded size alphabet Σ. First of all, we show a bijection between the border array of a string w and the skeleton of the DFA recognizing Σ*ω, called a string matching automaton (SMA). Different strings can have the same border array but the originality of the presented method is that the correspondence between a border array and a...
We associate with a word on a finite alphabet an episturmian (or Arnoux-Rauzy) morphism and a palindrome. We study their relations with the similar ones for the reversal of . Then when we deduce, using the sturmian words that are the fixed points of the two morphisms, a proof of a Galois theorem on purely periodic continued fractions whose periods are the reversal of each other.
We associate with a word w on a finite alphabet A an episturmian (or Arnoux-Rauzy) morphism and a palindrome. We study their relations with the similar ones for the reversal of w. Then when |A|=2 we deduce, using the Sturmian words that are the fixed points of the two morphisms, a proof of a Galois theorem on purely periodic continued fractions whose periods are the reversal of each other.
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...
It is well-known that some of the most basic properties of words, like the commutativity () and the conjugacy (), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation has only periodic solutions in a free monoid, that is, if holds with integers , then there exists a word such that are powers of . This result, which received a lot of attention, was first proved by Lyndon and...
It is well-known that some of the most basic properties of words, like the commutativity (xy = yx) and the conjugacy (xz = zy), can be expressed as solutions of word equations. An important problem is to decide whether or not a given equation on words has a solution. For instance, the equation xMyN = zP has only periodic solutions in a free monoid, that is, if xMyN = zP holds with integers m,n,p ≥ 2, then there exists a word w such that x, y, z are powers of w. This result, which received a lot...
We consider a recently defined notion of k-abelian equivalence of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length k for a fixed natural number k and the prefix of the word. We have shown earlier that over a ternary alphabet k-abelian squares cannot be avoided in pure morphic words for any natural number k. Nevertheless, computational experiments support the conjecture that even 3-abelian squares can...
Ramsey theory for words over a finite alphabet was unified in the work of Carlson, who also presented a method to extend the theory to words over an infinite alphabet, but subject to a fixed dominating principle. In the present work we establish an extension of Carlson's approach to countable ordinals and Schreier-type families developing an extended Ramsey theory for dominated words over a doubly infinite alphabet (in fact for ω-ℤ*-located words), and we apply this theory, exploiting the Budak-Işik-Pym...