We approach Černý's conjecture using the Wedderburn- Artin theory. We first introduce the radical ideal of a synchronizing automaton, and then the natural notion of semisimple synchronizing automata. This is a rather broad class since it contains simple synchronizing automata like those in Černý's series. Furthermore, semisimplicity gives the advantage of "factorizing" the problem of finding a synchronizing word into the sub-problems of finding words that are zeros in the projections into 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 automata whose sets of synchronizing words are cyclic ideals, or equivalently are ideal regular languages which are closed by takings roots. © 2014 Springer International Publishing Switzerland.

Semisimple synchronizing automata and the wedderburn-artin theory

Rodaro E.
2014

Abstract

We approach Černý's conjecture using the Wedderburn- Artin theory. We first introduce the radical ideal of a synchronizing automaton, and then the natural notion of semisimple synchronizing automata. This is a rather broad class since it contains simple synchronizing automata like those in Černý's series. Furthermore, semisimplicity gives the advantage of "factorizing" the problem of finding a synchronizing word into the sub-problems of finding words that are zeros in the projections into 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 automata whose sets of synchronizing words are cyclic ideals, or equivalently are ideal regular languages which are closed by takings roots. © 2014 Springer International Publishing Switzerland.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-3-319-09697-1
978-3-319-09698-8
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1141914
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact