Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102296
Title: Synchronizing automata with random inputs (Short Paper)
Authors: Gusev, V. V.
Issue Date: 2014
Publisher: Springer Verlag
Citation: Gusev V. V. Synchronizing automata with random inputs (Short Paper) / V. V. Gusev. — DOI 10.1007/978-3-319-09698-8_7 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2014. — Vol. 8633 LNCS. — P. 68-75.
Abstract: We study the problem of synchronization of automata with random inputs. We present a series of automata such that the expected number of steps until synchronization is exponential in the number of states. At the same time, we show that the expected number of letters to synchronize any pair of the famous Černý automata is at most cubic in the number of states. © 2014 Springer International Publishing Switzerland.
Keywords: ARTIFICIAL INTELLIGENCE
COMPUTER SCIENCE
COMPUTERS
NUMBER OF STATE
RANDOM INPUT
SYNCHRONIZING AUTOMATA
AUTOMATA THEORY
URI: http://hdl.handle.net/10995/102296
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84958536428
PURE ID: 367007
6d53ccfe-5891-4355-a374-e1a45463656c
ISSN: 3029743
ISBN: 9783319096971
DOI: 10.1007/978-3-319-09698-8_7
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84958536428.pdf138,61 kBAdobe PDFView/Open


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