Automates synchronisant et théorie du codage
Andrew Ryzhikov · HAL (Le Centre pour la Communication Scientifique Directe) · 2020
Cette thèse est consacrée a l’étude des mots synchronisant pour les automates finis et les codes. Intuitivement, un mot synchronisant est tel que son application amène le système dans un état indépendant de l'état initial. Un code ou un automate est synchronisant s’il admet un mot synchronisant. Il existe une forte relation entre l’utilisation de cette notion pour les automates ou les codes et son usage est l’un des leitmotifs de cette thèse.Un des principaux outils pour traiter les codes est l’usage d’un automate particulier préservant ses propriétés de synchronisation. Pour les codes préfixes, ceci est obtenu en utilisant un automate déterministe.Nous avons exploré deux problèmes principaux concernant la synchronisation. Le premier consiste à mesurer la longueur du plus court mot synchronisant pour un automate ou un code. Dans le cas d’un automate fini complet et déterministe, un des problèmes les plus anciens de la théorie combinatoire des automates propose une borne quadratique en termes du nombre d'états de l’automate. Nous étendons cette conjecture aux automates partiels non-déterministes. Nous établissons des bornes polynomiales pour ces classes en présence de la forte connexité, et nous discutons leur lien avec la conjecture originale de Černý.La relation avec les codes finis nous permet de prouver l’existence de bornes similaires en termes de la somme des longueurs des mots du code, et aussi de la longueur du plus long mot. Le deuxième cas est lié à une autre importante conjecture, proposée par Restivo. Elle concerne les mots mortels plutôt que synchronisant. Dans la plupart de ces cas, nous examinons aussi la complexité de calcul d’un mot synchronisant court, un deuxième aspect fondamental de cette thèse. Au-delà, nous étudions plusieurs généralisations de la notion de mot synchronisant, qui permettent d’utiliser une information partielle sur sur l’état dans lequel se trouve l’automate. Pour plusieurs de ces généralisations, nous prouvons des bornes inférieures de complexité, même dans ce cas très particuliers