Separating words with machines and groups
John Michael Robson · RAIRO - Theoretical Informatics and Applications · 1996
In the study ofsmall automata which separate pairs ofstrings ofa given length, those automata whose syntactic monoids are groups, appear to be of central importance.We show an upper bound on the number of state s requiredfor such a restricted automaton to separate two words of length N, not too much larger than the corresponding bound in the gênerai case.Résumé.-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érai (*)