We follow language theoretic approach to synchronizing automata and Černý’s conjecture initiated in a series of recent papers. We find a precise lower bound for the reset complexity of a principal ideal language. Also we show a strict connection between principal left ideals and synchronizing automata. Actually, it is proved that all strongly connected synchronizing automata are homomorphic images of automata recognizing languages which are left quotients of principal left ideal languages. This result gives a restatement of Černý’s conjecture in terms of length of the shortest reset words of special quotients of automata in this class. Also in the present paper we characterize regular languages whose minimal deterministic finite automaton is synchronizing and possesses a reset word belonging to the recognized language. This characterization shows a connection with the notion of constant of a language introduced by Schützenberger.

Representation of (Left) ideal regular languages by synchronizing automata

Rodaro E.
2015

Abstract

We follow language theoretic approach to synchronizing automata and Černý’s conjecture initiated in a series of recent papers. We find a precise lower bound for the reset complexity of a principal ideal language. Also we show a strict connection between principal left ideals and synchronizing automata. Actually, it is proved that all strongly connected synchronizing automata are homomorphic images of automata recognizing languages which are left quotients of principal left ideal languages. This result gives a restatement of Černý’s conjecture in terms of length of the shortest reset words of special quotients of automata in this class. Also in the present paper we characterize regular languages whose minimal deterministic finite automaton is synchronizing and possesses a reset word belonging to the recognized language. This characterization shows a connection with the notion of constant of a language introduced by Schützenberger.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
978-3-319-20296-9
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/1141912
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact