SEPARATING WORDS WITH MACHINES AND GROUPS

摘要

Les automates, dont le monoïde syntaxique est un groupe, sont apparemment d'une importance centrale dans l'étude des petits automates capables de distinguer deux mots de la même longueur. On montre un majorant sur le nombre d'états d'un tel automate séparant deux mots de longueur N, qui n'est pas par trop supérieur au majorant connu dans le cas d'un automate général.%In the study of small automata which separate pairs of strings of a given length, those automata whose syntactic monoids are groups, appear to be of central importance. We show an upper bound on the number of states required for such a restricted automaton to separate two words of length N, not too much larger than the corresponding bound in the general case.