On extremal properties of the Fibonacci word
We survey several quantitative problems on infinite words related to repetitions, recurrence, and palindromes, for which the Fibonacci word often exhibits extremal behaviour.
On the decidability of semigroup freeness
This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset ⊆ , decide whether each element of has at most one factorization over . To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In 1991, Klarner, Birget and Satterfield proved the undecidability...
On the decidability of semigroup freeness
This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset ⊆ , decide whether each element of has at most one factorization over . To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In...
Fonctions de récurrence des suites d’Arnoux-Rauzy et réponse à une question de Morse et Hedlund
La fonction de récurrence d’une suite symbolique compte au bout de combien de temps on voit tous les mots de longueur . Nous la calculons explicitement pour les suites d’Arnoux-Rauzy, définies par des conditions combinatoires qui en font une généralisation naturelle des suites sturmiennes. Puis nous répondons à une question de Morse et Hedlund (1940) en montrant que ne peut avoir une limite finie pour aucune suite non ultimement périodique.
On the decidability of semigroup freeness
This paper deals with the decidability of semigroup freeness. More precisely, the freeness problem over a semigroup is defined as: given a finite subset ⊆ , decide whether each element of has at most one factorization over . To date, the decidabilities of the following two freeness problems have been closely examined. In 1953, Sardinas and Patterson proposed a now famous algorithm for the freeness problem over the free monoids. In...
On conjugacy of languages
We say that two languages and are conjugates if they satisfy the conjugacy equation for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
On finite pseudorandom binary sequences VII: The measures of pseudorandomness
Weak mixing and eigenvalues for Arnoux-Rauzy sequences
We define by simple conditions two wide subclasses of the so-called Arnoux-Rauzy systems; the elements of the first one share the property of (measure-theoretic) weak mixing, thus we generalize and improve a counter-example to the conjecture that these systems are codings of rotations; those of the second one have eigenvalues, which was known hitherto only for a very small set of examples.
Infinite periodic points of endomorphisms over special confluent rewriting systems
We consider endomorphisms of a monoid defined by a special confluent rewriting system that admit a continuous extension to the completion given by reduced infinite words, and study from a dynamical viewpoint the nature of their infinite periodic points. For prefix-convergent endomorphisms and expanding endomorphisms, we determine the structure of the set of all infinite periodic points in terms of adherence values, bound the periods and show that all regular periodic points are attractors.
Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables
Nous étudions dans cet article deux familles d’ensembles d’entiers reconnaissables par des automates finis ou dénombrables. Les résultats concernant ces deux notions de reconnaissabilité qui sont présentés ici étendent de manière naturelle les résultats structurels usuels de la famille des ensembles -reconnaissables. Le cas particulier de l’ensemble des nombres premiers est également abordé.
On Conjugacy of Languages
We say that two languages and are conjugates if they satisfy the for some language . We study several problems associated with this equation. For example, we characterize all sets which are conjugated a two-element biprefix set , as well as all two-element sets which are conjugates.
Complexity and special factors. (Complexité et facteurs spéciaux.)
On finite pseudorandom binary sequences IV: The Liouville function, II
On finite pseudorandom binary sequences III: The Liouville function, I
Imbalances in Arnoux-Rauzy sequences
In a 1982 paper Rauzy showed that the subshift generated by the morphism , and is a natural coding of a rotation on the two-dimensional torus , i.e., is measure-theoretically conjugate to an exchange of three fractal domains on a compact set in each domain being translated by the same vector modulo a lattice. It was believed more generally that each sequence of block complexity satisfying a combinatorial criterion known as the condition of Arnoux and Rauzy codes the orbit of a point...
Sequences of low arithmetical complexity
Arithmetical complexity of a sequence is the number of words of length that can be extracted from it according to arithmetic progressions. We study uniformly recurrent words of low arithmetical complexity and describe the family of such words having lowest complexity.
A class of 1-additive sequences and quadratic recurrences.
Page 1