On two combinatorial problems arising from automata theory

Jean-Éric Pin



Résumé : On donne des résultats partiels sur les conjectures suivantes, issues de la théorie des automates. La première conjecture est la conjecture du triangle, due à Perrin et Schützenberger. Soit A = {a, b} un alphabet à deux lettres, d un entier positif et soit Bd = {aibaj | 0 ≤ i+j ≤ d}. Si X Bd est un code, alors |X| ≤ d+1. La seconde conjecture est due à Cerný et à l'auteur. Soit A un automate à n états. S'il existe un mot de rang ≤ k dans A, il en existe un de longueur ≤ (n-k)2.

Abstract : We present some partial results on the following conjectures arising from automata theory. The first conjecture is the triangle conjecture due to Perrin and Schützenberger. Let A = {a, b} be a two-letter alphabet, d a positive integer and let Bd = {aibaj | 0 ≤ i+j ≤ d}. If X Bd is a code, then |X| ≤ d+1. The second conjecture is due to Cerný and the author. Let A be an automaton with n states. If there exists a word of rank ≤ k in A, there exists such a word with length ≤ (n-k)2.

PostScript gzipped file, PDF file

Valid HTML 4.01!