Černý’s conjecture and the generation of slowly synchronizing automata

Details

Supervisors

Jungers, Raphaël M.

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en mathématiques appliquées, à finalité spécialisée

Abstract

enThis master’s thesis explores the longstanding conjecture proposed by Ján Černý in 1964, stating that (n−1)*(n-1) is the upper bound for the length of the shortest synchronizing word for any n-state complete deterministic DFA. In this thesis, we present a novel approach to generating slowly synchronizing automata, aiming to find automata that challenge the conjectured bound. The new approach involves the reformulation of our problem into an optimization problem, intending to relax the problem of reaching slowly synchronizing automata with the use of conventional optimization schemes working on real input matrices. To do so, we define heuristics adapted to this new formulation, and we prove that those heuristics are relevant in the task of generating slowly synchronizing automata. We present promising results in this direction as the generated automata have high average reset threshold values. This thesis develops this novel idea step by step, from the link between matrices and automata to the creation of an adequate objective function and its usage in a maximization problem. We also confirm empirically results from the literature about the rarity of slowly synchronizing automata with a high number of states.