This paper mainly concerns the property of strong local transitivity of finite automata. We will survey some results on this property in the context of the synchronization problem. Further aspects and results relating this problem with the Road coloring problem of finite directed graphs and the Restivo conjecture on the minimal length of an incompletable word of a finite language, are also analyzed.

Locally strongly transitive automata in the Černý conjecture and related problems

Carpi A.;
2019

Abstract

This paper mainly concerns the property of strong local transitivity of finite automata. We will survey some results on this property in the context of the synchronization problem. Further aspects and results relating this problem with the Road coloring problem of finite directed graphs and the Restivo conjecture on the minimal length of an incompletable word of a finite language, are also analyzed.
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: https://hdl.handle.net/11391/1459974
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact