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:

  • \(\Delta\): The words differ in 1 \(\Delta\) are \(\Delta^mp\) and \(\Delta^{m+1}R(p)\).Assume \(m\) is non-negative. At time \(|m|+1\), one encounters \(\Delta^m\sigma_{a_1}\) and \(\Delta^{m+1}\), which has a distance of \(2\). At time \(|m|+2\), \(\Delta^m\sigma_{a_1}\sigma_{a_2}\) and \(\Delta^{m+1}\sigma_{3-a_1} = \Delta^m\sigma_{a_1}\Delta\), which also has distance 2. By induction, the distance is 2 till the end, where one has \(\Delta^m\sigma_{a_1}\ldots\sigma_{a_k}\) and \(\Delta^m\sigma_{a_1}\ldots\sigma_{a_{k-1}}\Delta\). With one more step, it decrease the distance to \(1\). When \(m\) is negative, it's similar.
  • \(\Delta^{-1}\): Similar to \(\Delta\) case.
  • \(\sigma_1\): There are two cases. If the word end with \(\sigma_1\), or end with \(\sigma_2^b\), where \(b\geq 2\), then the two words are exactly the same until the end. Thus implies the fellow traveler property. If the word end with a single \(\sigma_2\), then the words are \(\Delta^mp\sigma_1^k\sigma_2\) and \(\Delta^mp\sigma_1^k\sigma_2\sigma_1\). The second word in normal form is \(\Delta^{m+1}R(p\sigma_1^{k-1})\). Note the first word is \(\Delta^mp\sigma_1^{k-1} \cdot \sigma_1\sigma_2\) We can use the fact that adding the \(\Delta\) have fellow traveler property to prove this also have that property.
  • \(\sigma_2\): Similar to \(\sigma_2\) 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.