Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/101952
Title: Synchronizing Random Almost-Group Automata
Authors: Berlinkov, M. V.
Nicaud, C.
Issue Date: 2018
Publisher: Springer Verlag
Citation: Berlinkov M. V. Synchronizing Random Almost-Group Automata / M. V. Berlinkov, C. Nicaud. — DOI 10.1007/978-3-319-94812-6_8 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2018. — Vol. 10977 LNCS. — P. 84-96.
Abstract: In this paper we address the question of synchronizing random automata in the critical settings of almost-group automata. Group automata are automata where all letters act as permutations on the set of states, and they are not synchronizing (unless they have one state). In almost-group automata, one of the letters acts as a permutation on n- 1 states, and the others as permutations. We prove that this small change is enough for automata to become synchronizing with high probability. More precisely, we establish that the probability that a strongly connected almost-group automaton is not synchronizing is [Formula Present], for a k-letter alphabet. © 2018, Springer International Publishing AG, part of Springer Nature.
Keywords: SYNCHRONIZATION
HIGH PROBABILITY
STRONGLY CONNECTED
AUTOMATA THEORY
URI: http://hdl.handle.net/10995/101952
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 85051135914
PURE ID: 7766296
1a5efb81-3c70-4d89-b458-5ad2f2fb5499
ISSN: 3029743
ISBN: 9783319948119
DOI: 10.1007/978-3-319-94812-6_8
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-85051135914.pdf201,41 kBAdobe PDFView/Open


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