Synchronization of finite automata

20^th November 2019, 14:00
Dr Andrew Ryzhikov
Université Paris-Est Marne-la-Vallée

Abstract

Imagine a reactive system modeled by a complete DFA. We know the structure of this DFA and we can observe its input, but we don't know its current state. Our goal is to eventually discover in which state the DFA is. This is possible if and only if there exists a word (called a reset word) which sends all the states to one particular state. Automata which admit reset words are called synchronizing, and the minimum length of reset words is the subject of the ?erný conjecture, one of the oldest open problems in automata theory. I will explain the extensions of this concept to the more general classes of partial DFAs and unambiguous NFAs, describe some extremal and algorithmic results for the mentioned classes, and show their tight connection with variable length codes.