2026-07-21T12:35:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13657 2024-03-06T10:52:35Z ddc:004 open_access

Synchronizing Strongly Connected Partial DFAs Berlinkov, Mikhail V. Ferens, Robert Ryzhikov, Andrew Szykuła, Marek Černý conjecture literal automaton partial automaton prefix code rank conjecture reset threshold reset word synchronizing automaton synchronizing word We study synchronizing partial DFAs, which extend the classical concept of synchronizing complete DFAs and are a special case of synchronizing unambiguous NFAs. A partial DFA is called synchronizing if it has a word (called a reset word) whose action brings a non-empty subset of states to a unique state and is undefined for all other states. While in the general case the problem of checking whether a partial DFA is synchronizing is PSPACE-complete, we show that in the strongly connected case this problem can be efficiently reduced to the same problem for a complete DFA. Using combinatorial, algebraic, and formal languages methods, we develop techniques that relate main synchronization problems for strongly connected partial DFAs with the same problems for complete DFAs. In particular, this includes the Černý and the rank conjectures, the problem of finding a reset word, and upper bounds on the length of the shortest reset words of literal automata of finite prefix codes. We conclude that solving fundamental synchronization problems is equally hard in both models, as an essential improvement of the results for one model implies an improvement for the other. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikhail V. Berlinkov and Robert Ferens and Andrew Ryzhikov and Marek Szykuła 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.12 urn:nbn:de:0030-drops-136579 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.12 eng https://creativecommons.org/licenses/by/4.0/legalcode