Lower Bounds on Avoiding Thresholds

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



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.46.pdf
  • Filesize: 0.67 MB
  • 14 pages

Document Identifiers

Author Details

Robert Ferens
  • Institute of Computer Science, University of Wrocław, Wrocław, Poland
Marek Szykuła
  • Institute of Computer Science, University of Wrocław, Wrocław, Poland
Vojtěch Vorel
  • Faculty of Informatics and Management, University of Hradec Králové, Czech Republic

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.MFCS.2021.46

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Mathematics of computing → Discrete mathematics
Keywords
  • avoiding word
  • Černý conjecture
  • rank conjecture
  • reset threshold
  • reset word
  • synchronizing automaton
  • synchronizing word

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. M. V. Berlinkov, R. Ferens, and M. Szykuła. Preimage problems for deterministic finite automata. Journal of Computer and System Sciences, 115:214-234, 2021. Google Scholar
  2. J. Černý. Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, 14(3):208-216, 1964. In Slovak. Google Scholar
  3. H. Don. The Černý Conjecture and 1-Contracting Automata. Electronic Journal of Combinatorics, 23(3):P3.12, 2016. Google Scholar
  4. F. Gonze and R. M. Jungers. Hardly Reachable Subsets and Completely Reachable Automata with 1-Deficient Words. Journal of Automata, Languages and Combinatorics, 24(2-4):321-342, 2019. Google Scholar
  5. F. Gonze, R. M Jungers, and A. N. Trahtman. A Note on a Recent Attempt to Improve the Pin-Frankl Bound. Discrete Mathematics and Theoretical Computer Science, 17(1):307-308, 2015. Google Scholar
  6. J. Kari. Synchronizing finite automata on Eulerian digraphs. Theoretical Computer Science, 295(1-3):223-232, 2003. Google Scholar
  7. A. Kisielewicz, J. Kowalski, and M. Szykuła. Experiments with Synchronizing Automata. In Implementation and Application of Automata, volume 9705 of LNCS, pages 176-188. Springer, 2016. Google Scholar
  8. J.-E. Pin. On two combinatorial problems arising from automata theory. In Proceedings of the International Colloquium on Graph Theory and Combinatorics, volume 75 of North-Holland Mathematics Studies, pages 535-548, 1983. Google Scholar
  9. I. K. Rystsov. Polynomial complete problems in automata theory. Information Processing Letters, 16(3):147-151, 1983. Google Scholar
  10. I. K. Rystsov. Quasioptimal Bound for the Length of Reset Words for Regular Automata. Acta Cybernetica, 12(2):145-152, 1995. Google Scholar
  11. Y. Shitov. An Improvement to a Recent Upper Bound for Synchronizing Words of Finite Automata. Journal of Automata, Languages and Combinatorics, 24(2-4):367-373, 2019. Google Scholar
  12. M. Szykuła. Improving the Upper Bound on the Length of the Shortest Reset Word. In STACS 2018, LIPIcs, pages 56:1-56:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  13. A. N. Trahtman. The Cerný conjecture for aperiodic automata. Discrete Mathematics and Theoretical Computer Science, 9(2):3-10, 2007. Google Scholar
  14. A. N. Trahtman. Modifying the upper bound on the length of minimal synchronizing word. In Fundamentals of Computation Theory, volume 6914 of LNCS, pages 173-180. Springer, 2011. Google Scholar
  15. M. V. Volkov. Synchronizing automata and the Cerný conjecture. In Language and Automata Theory and Applications, volume 5196 of LNCS, pages 11-27. Springer, 2008. Google Scholar
  16. M. V. Volkov. Synchronizing automata preserving a chain of partial orders. Theoretical Computer Science, 410(37):3513-3519, 2009. Google Scholar
  17. M. V. Volkov, editor. Special Issue: Essays on the Černý Conjecture, volume 24 (2-4) of Journal of Automata, Languages and Combinatorics, 2019. Google Scholar
  18. V. Vorel. Subset synchronization and careful synchronization of binary finite automata. Int. J. Found. Comput. Sci., 27(5):557-578, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail