We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.
We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.
Cet article est probablement le dernier texte de mathématiques écrit en vue de sa publication par M. P. Schützenberger, décédé en juillet 1996. Il était offert par son auteur en hommage à André Lentin, à l'occasion d'un colloque tenu en l'honneur de celui-ci le 23 février 1996 ; M. P. Schützenberger, déjà très malade, n'avait pu participer à cette rencontre, mais avait tenu à rédiger, non sans souffrances, une contribution scientifique qui témoignât de son amitié pour A. Lentin. Lorsque je lui dis...
Let denote the set of real numbers whose base- digit expansion is ultimately primitive substitutive, i.e., contains a tail which is the image (under a letter to letter morphism) of a fixed point of a primitive substitution. We show that the set is closed under multiplication by rational numbers, but not closed under addition.
L’objet de ce travail est d’étudier les propriétés arithmétiques et statistiques des mots infinis et des suites de nombres entiers engendrés par des substitutions sur un alphabet infini ou par des automates déterministes ayant un nombre infini dénombrable d’états. En particulier, nous montrons que si est une suite de nombres entiers engendrée par un automate dont le graphe étiqueté associé représente une marche aléatoire de moyenne nulle sur un réseau de ( entier positif), alors la suite ...
Un mot sturmien est un mot infini, binaire, équilibré et non ultimement périodique. On détermine l’évolution de la pente et de l’intercept d’un mot sturmien, sous l’action du monoïde de Sturm. À l’aide des matrices de Raney, on énonce une condition que doivent satisfaire les pentes des mots laissés fixes par une substitution non triviale. Puis on prouve que cette condition est suffisante pour un ensemble particulier de mots dont l’intercept est une homographie de la pente.
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...
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.
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.
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...