Ranking and unranking of a generalized Dyck language and the application to the generation of random trees.
Rational approximations to algebraic Laurent series with coefficients in a finite field
We give a general upper bound for the irrationality exponent of algebraic Laurent series with coefficients in a finite field. Our proof is based on a method introduced in a different framework by Adamczewski and Cassaigne. It makes use of automata theory and, in our context, of a classical theorem due to Christol. We then introduce a new approach which allows us to strongly improve this general bound in many cases. As an illustration, we give a few examples of algebraic Laurent series for which...
Rationality, irrationality, and Wilf equivalence in generalized factor order.
Reconnaissabilité des substitutions et complexité des suites automatiques
Répartition des suites et substitutions
Repetition thresholds for subdivided graphs and trees
The repetition threshold introduced by Dejean and Brandenburg is the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.
Repetition thresholds for subdivided graphs and trees
The repetition threshold introduced by Dejean and Brandenburg is the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β-powers for all β > α. We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.
Repetitions in the Fibonacci infinite word
Représentation par automate de fonctions continues de tore
Soient et un sous-système. est une représentation en base d’une fonction du tore si pour tout point du tore, ses développements en base sont liés par le couplage aux développements en base de . On prouve que si est représentable en base alors , où . Réciproquement, toutes les fonctions de ce type sont représentables en base par un transducteur. On montre finalement que les fonctions du tore qui peuvent être représentées par automate cellulaire sont exclusivement les multiplications...
Representations of a free group of rank two by time-varying Mealy automata
In the group theory various representations of free groups are used. A representation of a free group of rank two by the so-calledtime-varying Mealy automata over the changing alphabet is given. Two different constructions of such automata are presented.
Restricted permutations from Catalan to Fine and back.
Return words in sturmian and episturmian words
Return words in Sturmian and episturmian words
Considering each occurrence of a word w in a recurrent infinite word, we define the set of return words of w to be the set of all distinct words beginning with an occurrence of w and ending exactly just before the next occurrence of w in the infinite word. We give a simpler proof of the recent result (of the second author) that an infinite word is Sturmian if and only if each of its factors has exactly two return words in it. Then, considering episturmian infinite words, which are a natural generalization...
Reversal distance for strings with duplicates: linear time approximation using hitting set.
Root clustering of words
Six kinds of both of primitivity and periodicity of words, introduced by Ito and Lischke [M. Ito and G. Lischke, Math. Log. Quart. 53 (2007) 91–106; Corrigendum in Math. Log. Quart. 53 (2007) 642–643], give rise to defining six kinds of roots of a nonempty word. For 1 ≤ k ≤ 6, a k-root word is a word which has exactly k different roots, and a k-cluster is a set of k-root words u where the roots of u fulfil a given prefix relationship. We show that out of the 89 different clusters that can be considered...