License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.43
URN: urn:nbn:de:0030-drops-66665
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6666/
Go to the corresponding LIPIcs Volume Portal

Nicaud, Cyril

Fast Synchronization of Random Automata

pdf-format:
LIPIcs-APPROX-RANDOM-2016-43.pdf (0.6 MB)

Abstract

A synchronizing word for an automaton is a word that brings that automaton into one and the same state, regardless of the starting position. Cerny conjectured in 1964 that if a $n$-state deterministic automaton has a synchronizing word, then it has a synchronizing word of length at most (n-1)^2. Berlinkov recently made a breakthrough in the probabilistic analysis of synchronization: he proved that, for the uniform distribution on deterministic automata with n states, an automaton admits a synchronizing word with high probability. In this article, we are interested in the typical length of the smallest synchronizing word, when such a word exists: we prove that a random automaton admits a synchronizing word of length O(n log^{3}n) with high probability. As a consequence, this proves that most automata satisfy the Cerny conjecture.

BibTeX - Entry

@InProceedings{nicaud:LIPIcs:2016:6666,
  author =	{Cyril Nicaud},
  title =	{{Fast Synchronization of Random Automata}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{43:1--43:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6666},
  URN =		{urn:nbn:de:0030-drops-66665},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.43},
  annote =	{Keywords: random automata, synchronization, the Čern{\'y} conjecture}
}

Keywords: random automata, synchronization, the Černý conjecture
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI