Synchronizability of products of at least three cornered DFAs

At least 1 year old · documented by

Let k≥3k\geq 3, let Σ\Sigma be an alphabet, and let f:Σ∗→{−1,1}f:\Sigma^*\rightarrow\{-1,1\} satisfy f(ε)=1f(\varepsilon)=1. For DFAs M1,…,MkM_1,\ldots,M_k over Σ\Sigma, suppose that each MiM_i has an ff-corner ziz_i. Their direct product is

M=M1×⋯×Mk.M=M_1\times\cdots\times M_k.

A word is (z1,…,zk)(z_1,\ldots,z_k)-synchronizing if it maps every product state to (z1,…,zk)(z_1,\ldots,z_k).

Product-corner conjecture. If M1,…,MkM_1,\ldots,M_k are distinct and each contains an ff-corner ziz_i, then MM is (z1,…,zk)(z_1,\ldots,z_k)-synchronizable. The conjecture extends the paper's product results from two factors to at least three factors. The source supplies no resolution, so it remains open.

References

Primary source

Peter Bradshaw, Alexander Clow and Ladislav Stacho, “A cornering strategy for synchronizing a DFA”, arXiv:2405.00826 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.