Minimality conjecture for the smallest Garside-shadow automaton

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.

Sources & referencesView supporting material

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.