Sur la longueur des mots de rang donné d'un automate fini

Jean-Éric Pin



Résumé : A étant un automate fini à n états, nous montrons que s'il existe un mot de rang inférieur ou égal à (n-k) dans A, il en existe en particulier un de longueur inférieure ou égale à P(k), où P est un polynôme de degré 4.

Abstract : Let A be a finite automaton with n states. We prove that if there exists a word of rank ≤ (n-k) in A, then there exists such a word with length ≤ P(k), where P is a polynomial of degree 4.

PostScript gzipped file, PDF file

Valid HTML 4.01!