DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2017.40

Attainable Values of Reset Thresholds

Authors: Michalina Dzyga, Robert Ferens, Vladimir V. Gusev, and Marek Szykula

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

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).

Cite as

Michalina Dzyga, Robert Ferens, Vladimir V. Gusev, and Marek Szykula. Attainable Values of Reset Thresholds. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dzyga_et_al:LIPIcs.MFCS.2017.40,
  author =	{Dzyga, Michalina and Ferens, Robert and Gusev, Vladimir V. and Szykula, Marek},
  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 =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.40},
  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}
}

Search Results

Documents authored by Dzyga, Michalina

Attainable Values of Reset Thresholds

Abstract

Cite as

Thanks for your feedback!

Could not send message