Paper Info
Title
Ideal regular languages and strongly connected synchronizing automata.
Abstract
We introduce the notion of a reset left regular decomposition of an ideal regular language, and we prove that the category formed by these decompositions with the adequate set of morphisms is equivalent to the category of strongly connected synchronizing automata. We show that every ideal regular language has at least one reset left regular decomposition. As a consequence, every ideal regular language is the set of synchronizing words of some strongly connected synchronizing automaton. Furthermore, this one-to-one correspondence allows us to introduce the notion of reset decomposition complexity of an ideal from which follows a reformulation of Černý's conjecture in purely language theoretic terms. Finally, we present and characterize a subclass of ideal regular languages for which a better upper bound for the reset decomposition complexity holds with respect to the general case.
Year
DOI
Venue
2016
10.1016/j.tcs.2016.09.026
Theoretical Computer Science
Keywords
Field
DocType
Strongly connected synchronizing automaton,Černý's conjecture,Reset word,Ideal regular language
Discrete mathematics,Combinatorics,Nondeterministic finite automaton,Upper and lower bounds,Synchronizing automaton,Synchronizing,Regular language,Strongly connected component,Conjecture,Mathematics,Morphism
Journal
Volume
ISSN
Citations 
653
0304-3975
1
PageRank 
References 
Authors
0.36
8
2
Name
Order
Citations
PageRank
Rogério Reis114025.74
Emanuele Rodaro25515.63