Recently, a series of papers have started to look at Cerný‘s conjecture, and in general at synchronizing automata, from the point of view of the theory of ideals of free monoids. The starting point of such an approach is a simple observation: the set of reset words of an automaton is a two-sided ideal of the free monoid on its alphabet that is also a regular language. We study the relationship between a synchronizing automaton and the sets of (minimal) generators of its reset words. We show that if such set does not contain a word of a certain length, then Cerný‘s conjecture holds.

Missing factors of ideals and synchronizing automata

Frigeri A.;Rodaro E.
2019-01-01

Abstract

Recently, a series of papers have started to look at Cerný‘s conjecture, and in general at synchronizing automata, from the point of view of the theory of ideals of free monoids. The starting point of such an approach is a simple observation: the set of reset words of an automaton is a two-sided ideal of the free monoid on its alphabet that is also a regular language. We study the relationship between a synchronizing automaton and the sets of (minimal) generators of its reset words. We show that if such set does not contain a word of a certain length, then Cerný‘s conjecture holds.
2019
Cerný‘s conjecture
Ideals of free monoid
Minimal reset word
Strongly connected automaton
Synchronizing automaton
File in questo prodotto:
File Dimensione Formato  
Missing factors of ideals.pdf

Accesso riservato

: Publisher’s version
Dimensione 518.95 kB
Formato Adobe PDF
518.95 kB Adobe PDF   Visualizza/Apri

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: https://hdl.handle.net/11311/1141856
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact