Paper Info
Title
Trim Strongly Connected Synchronizing Automata and Ideal Languages.
Abstract
We follow language theoretic approach to synchronizing automata and Cerny's conjecture initiated in a series of recent papers. We prove that for every ideal language there exists a strongly connected synchronizing automaton from some special class for which given language serves as the language of reset words. This class is formed by trim automata recognizing left quotients of principal left ideal languages. We show that the minimal automaton recognizing a left quotient of a principal left ideal can be viewed as a synchronizing automaton for which given finitely generated ideal serves as the language of reset words.
Year
DOI
Venue
2018
10.3233/FI-2018-1720
FUNDAMENTA INFORMATICAE
Keywords
Field
DocType
ideal language,synchronizing automaton,reset word,reset complexity,reset left regular decomposition,strongly connected automaton
Discrete mathematics,Trim,Synchronizing automaton,Strongly connected component,Mathematics
Journal
Volume
Issue
ISSN
162
2-3
0169-2968
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Marina I. Maslennikova1182.94
Emanuele Rodaro25515.63