DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2021.46

Lower Bounds on Avoiding Thresholds

Authors: Robert Ferens, Marek Szykuła, and Vojtěch Vorel

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract

For a DFA, a word avoids a subset of states, if after reading that word the automaton cannot be in any state from the subset regardless of its initial state. A subset that admits an avoiding word is avoidable. The k-avoiding threshold of a DFA is the smallest number such that every avoidable subset of size k can be avoided with a word no longer than that number. We study the problem of determining the maximum possible k-avoiding thresholds. For every fixed k ≥ 1, we show a general construction of strongly connected DFAs with n states and the k-avoiding threshold in Θ(n^k). This meets the known upper bound for k ≥ 3. For k = 1 and k = 2, the known upper bounds are respectively in 𝒪(n²) and in 𝒪(n³). For k = 1, we show that 2n-3 is attainable for every number of states n in the class of strongly connected synchronizing binary DFAs, which is supposed to be the best possible in the class of all DFAs for n ≥ 8. For k = 2, we show that the conjectured solution for k = 1 (an upper bound in 𝒪(n)) also implies a tight upper bound in 𝒪(n²) on 2-avoiding threshold. Finally, we discuss the possibility of using k-avoiding thresholds of synchronizing automata to improve upper bounds on the length of the shortest reset words.

Cite as

Robert Ferens, Marek Szykuła, and Vojtěch Vorel. Lower Bounds on Avoiding Thresholds. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ferens_et_al:LIPIcs.MFCS.2021.46,
  author =	{Ferens, Robert and Szyku{\l}a, Marek and Vorel, Vojt\v{e}ch},
  title =	{{Lower Bounds on Avoiding Thresholds}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.46},
  URN =		{urn:nbn:de:0030-drops-144869},
  doi =		{10.4230/LIPIcs.MFCS.2021.46},
  annote =	{Keywords: avoiding word, \v{C}ern\'{y} conjecture, rank conjecture, reset threshold, reset word, synchronizing automaton, synchronizing word}
}

Search Results

Documents authored by Vorel, Vojtěch

Lower Bounds on Avoiding Thresholds

Abstract

Cite as

Thanks for your feedback!

Could not send message