Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102327
Title: Representation of (Left) ideal regular languages by synchronizing automata
Authors: Maslennikova, M.
Rodaro, E.
Issue Date: 2015
Publisher: Springer Verlag
Citation: Maslennikova M. Representation of (Left) ideal regular languages by synchronizing automata / M. Maslennikova, E. Rodaro. — DOI 10.1007/978-3-319-20297-6_21 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2015. — Vol. 9139. — P. 325-338.
Abstract: We follow language theoretic approach to synchronizing automata and Černý’s conjecture initiated in a series of recent papers. We find a precise lower bound for the reset complexity of a principal ideal language. Also we show a strict connection between principal left ideals and synchronizing automata. Actually, it is proved that all strongly connected synchronizing automata are homomorphic images of automata recognizing languages which are left quotients of principal left ideal languages. This result gives a restatement of Černý’s conjecture in terms of length of the shortest reset words of special quotients of automata in this class. Also in the present paper we characterize regular languages whose minimal deterministic finite automaton is synchronizing and possesses a reset word belonging to the recognized language. This characterization shows a connection with the notion of constant of a language introduced by Schützenberger. © Springer International Publishing Switzerland 2015.
Keywords: IDEAL LANGUAGE
RESET COMPLEXITY
RESET LEFT REGULAR DECOMPOSITION
RESET WORD
STRONGLY CONNECTED AUTOMATON
SYNCHRONIZING AUTOMATON
AUTOMATA THEORY
SYNCHRONIZATION
IDEAL LANGUAGE
REGULAR DECOMPOSITION
RESET COMPLEXITY
RESET WORDS
STRONGLY CONNECTED AUTOMATONS
SYNCHRONIZING AUTOMATA
COMPUTATIONAL LINGUISTICS
URI: http://hdl.handle.net/10995/102327
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84950129706
PURE ID: 567528
b1916737-bcc3-4a8f-a453-039e27313b82
ISSN: 3029743
ISBN: 9783319202969
DOI: 10.1007/978-3-319-20297-6_21
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84950129706.pdf260,81 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.