Paper Info
Title
Strongly connected synchronizing automata and the language of minimal reset words
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).
Year
DOI
Venue
2018
10.1016/j.aam.2018.04.006
Advances in Applied Mathematics
Keywords
Field
DocType
68Q70,68Q45,20M30,16D25,68R15
Homomorphic encryption,Combinatorics,Synchronizing automaton,Regular ideal,Automaton,Strongly connected component,Mathematics,Alphabet
Journal
Volume
ISSN
Citations 
99
0196-8858
0
PageRank 
References 
Authors
0.34
11
1
Name
Order
Citations
PageRank
Emanuele Rodaro15515.63