Technical Report: DCC-2013-01
Ideal Regular Languages and Strongly Connected Synchronizing Automata
Rogério Reis and Emanuele Rodaro
Centro de Matemática da Universidade do Porto
R. Campo Alegre 687, 4169-007 Porto, Portugal
e-mail: rvr@dcc.fc.up.pt, emanuele.rodaro@fc.up.pt
February 2013
Abstract
We introduce the notion of reset left regular decomposition
of an ideal regular language and we prove that there is a one-to-one
correspondence between these decompositions and strongly connected
synchronizing automata. We show that each ideal regular language has
at least a reset left regular decomposition. As a consequence each
ideal regular language is the set of synchronizing words of some
strongly connected synchronizing automaton. Furthermore, this
one-to-one correspondence allows us to formulate C?erny ? conjecture
in a pure language theoretic framework.