On étudie, dans cet article, les propriétés combinatoires de mots engendrés à l’aide de -automates déterministes dénombrables de degré borné, ou de manière équivalente, engendrés par des substitutions de longueur constante uniformément bornées sur un alphabet dénombrable. En particulier, on montre que la complexité de tels mots est au plus polynomiale et que, sur plusieurs exemples, elle est au plus de l’ordre de grandeur de .
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 (log
) when goes to
infinity.
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é.
Download Results (CSV)