A cornering strategy for synchronizing a DFA
Theoretical Computer Science · 2026-05 · 1073 · 115864
DOI: 10.1016/j.tcs.2026.115864 ↗Kurz gefasst
Fachartikel in der Zeitschrift Theoretical Computer Science, 2026-05. Verfasst von Peter Bradshaw und 2 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Natural Sciences and Engineering Research Council of Canada, National Science Foundation, National Science Foundation Directorate for Mathematical and Physical Sciences.
Abstract (Originalsprache)
This paper considers the existence of short synchronizing words in deterministic finite automata (DFAs). We define two general strategies for generating synchronizing words, and we show that each of these strategies can be applied if and only if a DFA is synchronizable. Furthermore, we show that if a synchronizable DFA is well-structured, then our strategies generate short synchronizing words. The first of our strategies, called the cornering strategy, takes advantage of states in a DFA with properties similar to those of a polytope vertex. The second of our strategies, similar to the cornering strategy and called the $f$-ordered strategy, takes advantage of a partial order defined on the states of a DFA. We apply our cornering strategy to the class of difference DFAs, whose states form subsets of $\mathbb R^d$ and whose input symbols correspond to translation vectors between states. We show that difference DFAs share many similarities with aperiodic DFAs, and in particular, a difference DFA $M$ has a synchronizing word if and only if it has a universally reachable state. Using the cornering strategy, we also show that under certain conditions, such an $n$-state DFA $M$ has a synchronizing word of length at most $(n-1)^2$ and thereby satisfies \v{C}ern\'y's conjecture. Using the $f$-ordered strategy, we also show that a synchronizable DFA whose states have a certain partial order that is preserved by a set of short words also has a short synchronizing word, and we consider several consequences of this result. Finally, we consider how the cornering strategy can be applied to the problem of synchronizing the product of two DFAs $M_1, M_2$ that share a common alphabet, and we show that the product $M_1 \times M_2$ often has a synchronizing word that is subquadratic in the number of states of $M_1 \times M_2$.
Förderung
- Natural Sciences and Engineering Research Council of Canada
- National Science Foundation
- National Science Foundation Directorate for Mathematical and Physical Sciences
Zitieren
APA
Bradshaw, P., Clow, A., & Stacho, L. (2026). A cornering strategy for synchronizing a DFA. Theoretical Computer Science, 1073, 115864. https://doi.org/10.1016/j.tcs.2026.115864
Vancouver
Bradshaw P, Clow A, Stacho L. A cornering strategy for synchronizing a DFA. Theoretical Computer Science. 2026;1073:115864. doi:10.1016/j.tcs.2026.115864
BibTeX
@article{Bradshaw2026,
author = {Bradshaw, Peter and Clow, Alexander and Stacho, Ladislav},
title = {A cornering strategy for synchronizing a DFA},
journal = {Theoretical Computer Science},
year = {2026},
volume = {1073},
pages = {115864},
doi = {10.1016/j.tcs.2026.115864}
}
EUVIMED