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.STACS.2018.56
URN: urn:nbn:de:0030-drops-85160
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8516/
Go to the corresponding LIPIcs Volume Portal

Szykula, Marek

Improving the Upper Bound on the Length of the Shortest Reset Word

pdf-format:
LIPIcs-STACS-2018-56.pdf (0.4 MB)

Abstract

We improve the best known upper bound on the length of the shortest reset words of synchronizing automata. The new bound is slightly better than 114 n^3 / 685 + O(n^2). The Cerny conjecture states that (n-1)^2 is an upper bound. So far, the best general upper bound was (n^3-n)/6-1 obtained by J.-E. Pin and P. Frankl in 1982. Despite a number of efforts, it remained unchanged for about 35 years.

To obtain the new upper bound we utilize avoiding words.
A word is avoiding for a state q if after reading the word the automaton cannot be in q. We obtain upper bounds on the length of the shortest avoiding words, and using the approach of Trahtman from 2011 combined with the well-known Frankl theorem from 1982, we improve the general upper bound on the length of the shortest reset words.
For all the bounds, there exist polynomial algorithms finding a word of length not exceeding the bound.

BibTeX - Entry

@InProceedings{szykula:LIPIcs:2018:8516,
  author =	{Marek Szykula},
  title =	{{Improving the Upper Bound on the Length of the Shortest Reset Word}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{56:1--56:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8516},
  URN =		{urn:nbn:de:0030-drops-85160},
  doi =		{10.4230/LIPIcs.STACS.2018.56},
  annote =	{Keywords: avoiding word, Cerny conjecture, reset length, reset threshold, reset word, synchronizing automaton, synchronizing word}
}

Keywords: avoiding word, Cerny conjecture, reset length, reset threshold, reset word, synchronizing automaton, synchronizing word
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

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