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.