Mikhail V. Berlinkov ; Robert Ferens ; Andrew Ryzhikov ; Marek Szykuła - Synchronization of strongly connected partial DFAs and prefix codes

dmtcs:16465 - Discrete Mathematics & Theoretical Computer Science, June 21, 2026, vol. 28:2 - https://doi.org/10.46298/dmtcs.16465
Synchronization of strongly connected partial DFAs and prefix codesArticle

Authors: Mikhail V. Berlinkov ; Robert Ferens ; Andrew Ryzhikov ; Marek Szykuła

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 \emph{reset word}) whose action brings a non-empty subset of states to a unique state and is undefined for all other states. The class of strongly connected partial DFAs is precisely the class of DFAs recognizing the Kleene star of prefix codes. 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 to 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.

Extended version of STACS 2021 paper


Volume: vol. 28:2
Section: Automata, Logic and Semantics
Published on: June 21, 2026
Accepted on: June 1, 2026
Submitted on: September 4, 2025
Keywords: Formal Languages and Automata Theory, Combinatorics

Consultation statistics

This page has been seen 83 times.
This article's PDF has been downloaded 42 times.