License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.46
URN: urn:nbn:de:0030-drops-144869
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14486/
Go to the corresponding LIPIcs Volume Portal

Ferens, Robert ; Szykuła, Marek ; Vorel, Vojtěch

Lower Bounds on Avoiding Thresholds

pdf-format:
LIPIcs-MFCS-2021-46.pdf (0.7 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2021/14486},
  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}
}

Keywords: avoiding word, Černý conjecture, rank conjecture, reset threshold, reset word, synchronizing automaton, synchronizing word
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

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