The Art Gallery Guardian

\(B_3\) is automatic, a simple proof

\(B_3\) is particularly nice to analyze due to the uniqueness of the Garside normal form.


The Garside normal form is unique in \(B_3\), and is in the form \(\Delta^m\sigma_{a_1}^{e_1}\ldots\sigma_{a_k}^{e_k}\), such that \(a_i \neq a_{i+1}\), \(e_1,e_k\geq 1\) and \(e_2,\ldots,e_{k-1} \geq 2\).


For any word \(w\in B_n\), the Garside normal form \(\Delta^m p\) is unique up to elements \(p\) in \(B_n^+\) and \(p\) does not have a factor of \(\Delta\). Now we show that there is only one way to write \(p\).

Every \(p\) must be in this form. If for some \(k>i>1\), \(e_i=1\), then \(a_{i-1}^{e_{i-1}}a_i^{e_i}a_{i+1}^{e_{i+1}} = a_{i-1}^{e_{i-1} -1}\Delta a_{i+1}^{e_{i+1}-1}\), which is a contradiction because \(p\) doesn't have a factor of \(\Delta\).

Every word in that form is also in \(B_n^+\), and without \(\Delta\) factor.

It's impossible to rewrite any word in this form with the relations \(\sigma_1\sigma_2\sigma_1 = \sigma_2\sigma_1\sigma_2\). Therefore this form is unique.


The Garside normal form of \(B_3\) is regular.


Let \(A=\{\Delta,\Delta^{-1},\sigma_1,\sigma_2\}\), then \(A\) generates \(G\). The Garside normal form is a regular language over \(A\) because they exist an explicit regular expression \(R\) that matches it.

\(R = (\Delta^*\cup(\Delta^{-1*}))(X\cup X')\) where \(X = \sigma_1^*(\sigma_2\sigma_2\sigma_2^*\sigma_1\sigma_1\sigma_1^*)^* ((\sigma_2\sigma_2\sigma_2^*\sigma_1^*)\cup \sigma_2^*))\) and \(X'\) is the same except the \(\sigma_2\) and \(\sigma_1\) are switched.

Let \(W\) be a FSA generated by the regular expression \(R\).

\(M_\epsilon\) exists, because the Garside normal form is unique, then \(M_\epsilon\) accepts all language of the form \(\{(w,w)|w\in L(W)\}\). It have the complete same structure as \(W\), but replacing every edge \(x\) with \((x,x)\).

Instead of construct \(M_x\) directly, we only need to prove the fellow traveler property is true. This can be done by checking it is true for every \(M_x\) independently.

Define \(R(\sigma_{a_1}\ldots\sigma_{a_k}) = \sigma_{3-a_1}\ldots\sigma_{3-a_k}\).

Note that every generator has a constant distance from another generator.

Consider \(x\) case by case:

The fellow traveler property is true for each generator.

We now have the theorem


\(B_3\) is automatic.

Posted by Chao Xu on 2011-07-11.
Tags: automatic group, braid group, BSU REU.