Minimality conjecture for the smallest Garside-shadow automaton

About 11 years old · traced to

Let (W,S)(W,S) be a Coxeter system, let S~\tilde S be its smallest Garside shadow, and let AS~(W,S)\mathcal A_{\tilde S}(W,S) be the associated finite deterministic automaton. Write Red⁡(W,S)\operatorname{Red}(W,S) for the language of reduced words of (W,S)(W,S). Minimality conjecture. The automaton AS~(W,S)\mathcal A_{\tilde S}(W,S) is the minimal automaton recognizing Red⁡(W,S)\operatorname{Red}(W,S). The main theorem shows that this automaton recognizes the language; the conjecture concerns whether it has the smallest possible number of states. The paper gives surjective morphisms from automata associated with larger Garside shadows, but does not establish minimality.

References

Primary source

Christophe Hohlweg, Philippe Nadeau and Nathan Williams, “Automata, reduced words, and Garside shadows in Coxeter groups”, arXiv:1510.01607 (2016).

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.