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.MFCS.2017.40
URN: urn:nbn:de:0030-drops-81220
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8122/
Dzyga, Michalina ;
Ferens, Robert ;
Gusev, Vladimir V. ;
Szykula, Marek
Attainable Values of Reset Thresholds
Abstract
An automaton is synchronizing if there exists a word that sends all states of the automaton to a single state. The reset threshold is the length of the shortest such word. We study the set RT_n of attainable reset thresholds by automata with n states. Relying on constructions of digraphs with known local exponents we show that the intervals [1, (n^2-3n+4)/2] and
[(p-1)(q-1), p(q-2)+n-q+1], where 2 <= p < q <= n, p+q > n, gcd(p,q)=1, belong to RT_n, even if restrict our attention to strongly connected automata. Moreover, we prove that in this case the smallest value that does not belong to RT_n is at least n^2 - O(n^{1.7625} log n / log log n).
This value is increased further assuming certain conjectures about the gaps between consecutive prime numbers.
We also show that any value smaller than n(n-1)/2 is attainable by an automaton with a sink state and any value smaller than n^2-O(n^{1.5}) is attainable in general case.
Furthermore, we solve the problem of existence of slowly synchronizing automata over an arbitrarily large alphabet, by presenting for every fixed size of the alphabet an infinite series of irreducibly synchronizing automata with the reset threshold n^2-O(n).
BibTeX - Entry
@InProceedings{dzyga_et_al:LIPIcs:2017:8122,
author = {Michalina Dzyga and Robert Ferens and Vladimir V. Gusev and Marek Szykula},
title = {{Attainable Values of Reset Thresholds}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {40:1--40:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-046-0},
ISSN = {1868-8969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8122},
URN = {urn:nbn:de:0030-drops-81220},
doi = {10.4230/LIPIcs.MFCS.2017.40},
annote = {Keywords: Cerny conjecture, exponent, primitive digraph, reset word, synchronizing automaton}
}
|
Keywords: |
|
Cerny conjecture, exponent, primitive digraph, reset word, synchronizing automaton |
|
Collection: |
|
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.12.2017 |
