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.