Cornering Robots to Synchronize a DFA
<|reference_start|>Cornering Robots to Synchronize a DFA: This paper considers the existence of short synchronizing words in deterministic finite automata (DFAs). In particular, we define a general strategy, which we call the \emph{cornering strategy}, for generating short synchronizing words in well-structured DFAs. We show that a DFA is synchronizable if and only if this strategy can be applied.   Using the cornering strategy, we prove that all DFAs consisting of $n$ points in $\mathbb{R}^d$ with bidirectional connected edge sets in which each edge $(\mb x, \mb y)$ is labeled $\mb y - \mb x$ are synchronizable. We also give sufficient conditions for such DFAs to have synchronizing words of length at most $(n-1)^2$ and thereby satisfy \v{C}ern\'y's conjecture. Using similar ideas, we generalise a result of Ananichev and Volkov \cite{ananichev2004synchronizing} from monotonic automata to a wider class of DFAs admitting well-behaved partial orders. Finally, we consider how the cornering strategy can be applied to the problem of simultaneously synchronizing a DFA $G$ to an initial state $u$ and a DFA $H$ to an initial state $v$. We do not assume that DFAs $G$ and $H$ or states $u$ and $v$ are related beyond sharing the same edge labels.<|reference_end|>
@article{bradshaw2024cornering,
    title={Cornering Robots to Synchronize a DFA},
    author={Peter Bradshaw, Alexander Clow, Ladislav Stacho},
    journal={arXiv preprint arXiv:2405.00826},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.00826},
    primaryClass={cs.FL math.CO}
}