A Language Theoretic Approach to Strongly Connected Synchronizing Automata

Room M029, DMat-FCUP
Friday, 21 June, 2013 - 13:30

We present a recent attempt to place strongly connected synchronizing automata and Cerny's conjecture in a pure language theoretic framework. Crucial is the notion of reset left regular decomposition of an ideal regular language which gives an equivalence between the category of these decompositions and the category of strongly connected synchronizing automata. We sketch the proof that each ideal regular language has at least a reset left regular decomposition. As a consequence each ideal regular language serves as the set of synchronizing words of some strongly connected synchronizing automaton. This is a joint work with R. Reis.

Speaker: 

Emanuele Rodaro (CMUP)