Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

Sur la complexité de mots infinis engendrés par des q -automates dénombrables

Marion Le Gonidec — 2006

Annales de l’institut Fourier

On étudie, dans cet article, les propriétés combinatoires de mots engendrés à l’aide de q -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 n ( log n ) p .

Drunken man infinite words complexity

Marion Le Gonidec — 2008

RAIRO - Theoretical Informatics and Applications

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.


Propriétés et limites de la reconnaissance d’ensembles d’entiers par automates dénombrables

Julien CassaigneMarion Le Gonidec — 2010

Journal de Théorie des Nombres de Bordeaux

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 k -reconnaissables. Le cas particulier de l’ensemble des nombres premiers est également abordé.

Page 1

Download Results (CSV)