Černý's conjecture is one of the most longstanding open problems in the theory of finite automata
Černý's conjecture is one of the most longstanding open problems in the theory of finite automata (stated by Černý in 1964). This conjecture claims that a deterministic finite automaton with n states and synchronizing, has always a synchronizing word of length (n-1)^2. In this seminar, I am going to show an approach to Černý 's conjecture using the Wedderburn-Artin theory. First I introduce the notion of a radical ideal of a synchronizing automaton, and then the natural notion of semisimple synchronizing automata. Semisimplicity gives the advantage of “factorizing” the problem of finding a synchronizing word into the sub-problems of finding words that are zeros into the projections of the simple components in the Wedderburn-Artin  decomposition. This situation is applied to prove that Černý 's conjecture holds for the class of strongly semisimple synchronizing automata: these are the automata whose sets of synchronizing words are cyclic ideals, or equivalently are ideal regular languages which are closed by takings roots. (This is a work in progress with J. Almeida)

Date and Venue

Start Date
Venue
Room FC1.030, DMat-FCUP

Speaker

Emanuele Rodaro (CMUP)

Area

Semigroups, Automata and Languages