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.ICALP.2023.59
URN: urn:nbn:de:0030-drops-181110
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18111/
Go to the corresponding LIPIcs Volume Portal

Ferens, Robert ; Szykuła, Marek

Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds

pdf-format:
LIPIcs-ICALP-2023-59.pdf (0.8 MB)

Abstract

A complete deterministic finite (semi)automaton (DFA) with a set of states Q is completely reachable if every non-empty subset of Q can be obtained as the image of the action of some word applied to Q. The concept of completely reachable automata appeared several times, in particular, in connection with synchronizing automata; the class contains the Černý automata and covers a few separately investigated subclasses. The notion was introduced by Bondar and Volkov (2016), who also raised the question about the complexity of deciding if an automaton is completely reachable. We develop a polynomial-time algorithm for this problem, which is based on a new complement-intersecting technique for finding an extending word for a subset of states. The algorithm works in ?(|Σ|⋅ n³) time, where n = |Q| is the number of states and |Σ| is the size of the input alphabet. Finally, we prove a weak Don’s conjecture for this class of automata: a subset of size k is reachable with a word of length smaller than 2n(n-k). This implies a quadratic upper bound in n on the length of the shortest synchronizing words (reset threshold) for the class of completely reachable automata and generalizes earlier upper bounds derived for its subclasses.

BibTeX - Entry

@InProceedings{ferens_et_al:LIPIcs.ICALP.2023.59,
  author =	{Ferens, Robert and Szyku{\l}a, Marek},
  title =	{{Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18111},
  URN =		{urn:nbn:de:0030-drops-181110},
  doi =		{10.4230/LIPIcs.ICALP.2023.59},
  annote =	{Keywords: \v{C}ern\'{y} conjecture, complete reachability, DFA, extending word, reachability, reset threshold, reset word, simple idempotent, synchronizing automaton, synchronizing word}
}

Keywords: Černý conjecture, complete reachability, DFA, extending word, reachability, reset threshold, reset word, simple idempotent, synchronizing automaton, synchronizing word
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

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