We approach the problem of finding strongly connected synchronizing automata with a given ideal I that serves as the set of reset words, by studying the set of minimal words M of the ideal I (no proper factor is a reset word). We first show the existence of an infinite strongly connected synchronizing automaton A having I as the set of reset words and such that every other strongly connected synchronizing automaton having I as the set of reset words is an homomorphic image of A. Finally, we show that for any non-unary regular ideal I there is a strongly connected synchronizing automaton having I as the set of reset words with at most (kmk)2kmkn states, where k is the dimension of the alphabet, m is twice the length of a shortest word in I, and n is the number of states of the smallest automaton recognizing M. This synchronizing automaton is computable and we exhibit an algorithm to compute it in time O((k2mk)2kmkn).

Strongly connected synchronizing automata and the language of minimal reset words

Rodaro, Emanuele
2018

Abstract

We approach the problem of finding strongly connected synchronizing automata with a given ideal I that serves as the set of reset words, by studying the set of minimal words M of the ideal I (no proper factor is a reset word). We first show the existence of an infinite strongly connected synchronizing automaton A having I as the set of reset words and such that every other strongly connected synchronizing automaton having I as the set of reset words is an homomorphic image of A. Finally, we show that for any non-unary regular ideal I there is a strongly connected synchronizing automaton having I as the set of reset words with at most (kmk)2kmkn states, where k is the dimension of the alphabet, m is twice the length of a shortest word in I, and n is the number of states of the smallest automaton recognizing M. This synchronizing automaton is computable and we exhibit an algorithm to compute it in time O((k2mk)2kmkn).
File in questo prodotto:
File Dimensione Formato  
Strongly connected synchronizing automata and ideals.pdf

Accesso riservato

: Publisher’s version
Dimensione 388.06 kB
Formato Adobe PDF
388.06 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: http://hdl.handle.net/11311/1078157
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact