Sturmian morphisms. (Morphismes de Sturm.)
Substitutions, abstract number systems and the space filling property
In this paper we study multi-dimensional words generated by fixed points of substitutions by projecting the integer points on the corresponding broken halfline. We show for a large class of substitutions that the resulting word is the restriction of a linear function modulo and that it can be decided whether the resulting word is space filling or not. The proof uses lattices and the abstract number system associated with the substitution.
Suites algébriques, automates et substitutions
Superiority of one-way and realtime quantum machines∗∗∗
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic...
Superiority of one-way and realtime quantum machines
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic acceptance mode: Each quantum model...
Superiority of one-way and realtime quantum machines∗∗∗
In automata theory, quantum computation has been widely examined for finite state machines, known as quantum finite automata (QFAs), and less attention has been given to QFAs augmented with counters or stacks. In this paper, we focus on such generalizations of QFAs where the input head operates in one-way or realtime mode, and present some new results regarding their superiority over their classical counterparts. Our first result is about the nondeterministic...
Sur des notions algébriques liées à l'analyse syntaxique
Sur la classification syntaxique.
Sur la complexité de mots infinis engendrés par des -automates dénombrables
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 .
Sur la structure des automates probabilistes
Sur l'auto-stabilisation dans un réseau d'ordinateurs
Sur le noyau d'un homomorphisme du monoïde libre dans un groupe libre
Sur le produit avec compteur modulo un nombre premier
Sur les automates qui reconnaissent une famille de langages.
Sur les centres de DOL-langages
Sur les ensembles de mots infinis engendrés par une grammaire algébrique
Sur les ensembles linéaires
Sur les groupes syntaxiques d'un langage
Sur les monoïdes finis dont les groupes sont commutatifs
Sur les TOL - Systèmes unaires