<figure><img src="image_1.png" /></figure>

HAL
open science

Local characterization and minimal automaton of the
alternating normal form in the standard braid monoid

June Roupin

► To cite this version:

June Roupin. Local characterization and minimal automaton of the alternating normal form in the standard braid monoid. 2025. hal-05035103

HAL Id: hal-05035103

https://hal.science/hal-05035103v1

Preprint submitted on 15 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
Local characterization and minimal automaton of the alternating normal form in the standard braid monoid

June Roupin

Univ Gustave Eiffel, CNRS, LIGM, Champs-sur-Marne, F-77454, France

Abstract

The alternating normal form of braids is a well-known normal form on the standard braid monoid. This normal form is regular: the language it identifies with is regular. We prove a new characterization of this normal form and its associated language using easily computable braid invariants. This allows us to build its minimal automaton, whose size we compute, both in terms of number of states and of transitions, depending on the number of generators of the monoid. This characterization is also a first step towards proving stronger results on the alternating normal form, in particular its automaticity.

Keywords: Standard braid monoid, Alternating normal form, Regular language, Minimal automata

1. Introduction

The group of braids with $n$ strands, commonly denoted by $B_n$, is the group of isotopy classes of geometric braids with $n$ strands. In [1], E. Artin proved that this group enjoys the following finite presentation:

$$B_n = \langle \sigma_1, \sigma_2, \dots, \sigma_{n-1} \mid \begin{array}{ll} \sigma_i\sigma_j \equiv \sigma_j\sigma_i & \text{if } |i-j| > 1 \\ \sigma_i\sigma_j\sigma_i \equiv \sigma_j\sigma_i\sigma_j & \text{if } |i-j| = 1 \end{array} \rangle.$$

The relations $\sigma_i\sigma_j \equiv \sigma_j\sigma_i$ are called *commutation relations*; the relations $\sigma_i\sigma_{i+1}\sigma_i \equiv \sigma_{i+1}\sigma_i\sigma_{i+1}$ are called *braid relations*, see Fig. 1.

<figure><img src="image_2.png" /><figcaption>Figure 1: Examples of relations in the braid monoid $B_n^+$</figcaption></figure>
These group come with the *simplification* relations $\sigma_i\sigma_i^{-1} \equiv \varepsilon$, where $\varepsilon$ denotes the neutral element of the group. Braid elements $\sigma_1, \dots, \sigma_{n-1}$ are called *Artin generators*.

Braid groups enjoy numerous algebraic, combinatorial and geometric properties, many of which are connected with the study of the (standard) braid monoid $B_n^+$: this is the monoid positively generated by the generators $\sigma_i$, i.e., the smallest subset of $B_n$ containing $\varepsilon$, the generators $\sigma_1, \dots, \sigma_{n-1}$ (but not their inverses) and stable by product:

$$ B_n^+ = \left\langle \sigma_1, \sigma_2, \dots, \sigma_{n-1} \;\middle|\; \begin{array}{ll} \sigma_i\sigma_j \equiv \sigma_j\sigma_i & \text{if } |i-j| > 1 \\ \sigma_i\sigma_j\sigma_i \equiv \sigma_j\sigma_i\sigma_j & \text{if } |i-j| = 1 \end{array} \right\rangle^+ . $$

The above presentation identifies each braid $\beta \in B_n^+$ with an equivalence class of words over the alphabet $A_n = \{\sigma_1, \dots, \sigma_{n-1}\}$, called positive words. In [1], it is proven that two positive words are equivalent in $B_n$ if and only if they are equivalent in $B_n^+$, so there exists a sequence of commutation and braid relations linking any two equivalent words in $B_n^+$. In this context, a normal form is a language containing exactly one word $\mathrm{NF}_n(\beta) \in A_n^*$ in each equivalence class $\beta$, which will be a preferred representative of $\beta$ and is called the normal form of $\beta$.

For a normal form to be useful, the following tasks should be as easy as possible [5]:

* deciding whether a word $w \in A_n^*$ is in normal form;

* transforming a word $w \in A_n^*$ representing a braid $\beta \in B_n^+$ into its normal form $\mathrm{NF}_n(\beta)$;

* computing, given two words in normal form $w = \mathrm{NF}_n(\beta)$ and $w' = \mathrm{NF}_n(\beta')$, the word $\mathrm{NF}_n(\beta\beta')$.

The first property can be measured by checking whether the language of words in normal form is *regular*, and computing the size of the minimal automaton recognizing this language. The two other questions are linked to the *right-automaticity* of the normal form, a property that ensures that computing the normal form of $\beta\sigma_i$ from the normal form of $\beta$ is easy.

To give context, let us mention three well-known normal forms on braids: the Garside normal form [7, 8], the lexicographically minimal normal form [9], and the *alternating normal form* [2, 3]. The Garside normal form is the most studied normal form on braid, and consists in cutting a braid into a sequence of maximal *simple blocks*, a notion we define in Section 2.2. This normal form is regular and is the only normal form known to be left or right-automatic, and is even bi-automatic (i.e., automatic when adding letters on either sides) [5]. The lexicographically minimal normal form, on the other hand, consists in choosing the minimal representative of a braid in the lexicographical order, using the order $\sigma_1 < \sigma_2 < \dots$ on letters.

Finally, the alternating normal form cuts braids into maximal blocks that belong to smaller sub-monoids, recursively cutting these blocks until there is a unique representative. This normal form is tightly connected to the rotating normal form [6], a similar normal form defined on the *dual* braid monoid $B_n^{**}$, which is the sub-monoid of $B_n$ positively generated by braids of the form $\sigma_u\sigma_{u-1} \cdots \sigma_{v+1}\sigma_v\sigma_{v+1}^{-1}\sigma_{v+2}^{-1} \cdots \sigma_u^{-1}$. The alternating, the rotating and the lexicographic normal forms are known to be regular, but the question of whether they are automatic is still open. Moreover, there is no description of the minimal automaton associated to the alternating normal form.

In this article, we study the alternating normal form, and prove two main results: a new characterization of the alternating normal form (Theorem 37) answering Question 6.1. of [3], and an explicit construction of the minimal automaton recognizing the language of words in alternating normal form (Theorems 54 and 55).
In Section 2, we define the standard braid monoid, we give some of its main known properties, and we define the alternating normal form. In Section 3, we prove a new characterization of the alternating normal form. In Section 4, we use this characterization to construct the minimal automaton recognizing the language of words in alternating normal form, computing explicitly its number of states and transitions.

Part of the results of this article were already presented in a shorter conference article [10], but without full proofs.

## 2. Context

### 2.1. The standard braid monoid

For all integer $n \ge 2$, we define the standard braid monoid $B_n^+$.

**Definition 1 (Standard braid monoid).** The standard braid monoid on $n \ge 2$ strands is defined as:

$$B_n^+ = \left\langle \sigma_1, \sigma_2, \dots, \sigma_{n-1} \left| \begin{array}{ll} \sigma_i \sigma_j \equiv \sigma_j \sigma_i & \text{if } |i-j| > 1 \\ \sigma_i \sigma_j \sigma_i \equiv \sigma_j \sigma_i \sigma_j & \text{if } |i-j| = 1 \end{array} \right. \right\rangle^+$$

The notation $\equiv$ expresses the equality of braids in the braid monoid, and will be denoted as such to distinguish it from equality between words. The monoid $B_n^+$ comes with a binary operation, the concatenation of braids, which associates the braid $\beta \gamma \in B_n^+$ to two braids $\beta, \gamma \in B_n^+$; as well as a neutral element associated to this operation, the trivial braid $\varepsilon$, such that $\beta \varepsilon \equiv \varepsilon \beta \equiv \beta$ for all braids $\beta \in B_n^+$.

To each braid $\beta \in B_n^+$ is associated a finite equivalence class of words over the alphabet $A_n = \{\sigma_1, \dots, \sigma_{n-1}\}$, the set of letters. The set $A_n^*$ is called the set of representatives of braids, as each word in this set is a representative of a single braid in $B_n^+$. For all integers $m \ge n \ge 2$, there exists a canonical injection from $A_n^*$ to $A_m^*$, from which we can deduce an injection from $B_n^+$ to $B_m^+$, so we can define $B^+ = \bigcup_{n=2}^{\infty} B_n^+$ the set of all positive braids.

We also define divisibility in the braid monoid: a braid $\beta \in B_n^+$ left-divides $\gamma \in B_n^+$ if there exists a braid $\zeta \in B_n^+$ such that $\gamma \equiv \beta \zeta$; we then write $\beta \le \gamma$. Symmetrically, we write $\gamma \ge \beta$ if $\beta$ right-divides $\gamma \in B_n^+$. Divisibility can be characterized using words, as a braid $\beta$ divides a braid $\gamma$ when any/all representative of $\beta$ is a prefix of a representative of $\gamma$, so divisibility can be seen as an extension of the prefix relation on words.

It is shown in [4] (chapter VII) that $B^+$ has a lattice structure: there exists a unique gcd (greatest common divisor) and lcm (least common multiple), to the left and the right, of any two braids. In this article, we only work with left-divisibility, so in particular gcd and lcm will always refer to left-gcd and left-lcm.

Furthermore, the set $D(\beta) = \{\gamma : \gamma \le \beta\}$ of left divisors of a braid $\beta$ also forms a lattice since the gcd and lcm of any two divisors of $\beta$ are also divisors of $\beta$. Since the set $D(\beta)$ is finite, it is bounded, so it contains a unique maximal element $(\beta)$ and a unique minimal element $(\varepsilon)$.

In order to study the set of representatives of a braid $\beta$, we often need information about the letters with which words that represent $\beta$ can begin. Since this corresponds to letters that left-divide the braid $\beta$, we introduce the following set:

**Definition 2 (Left set of a braid).** Let $\beta \in B^+$ be a braid. We define $L(\beta)$ the set of indices of letters left-dividing $\beta$; in other words, $i \in L(\beta)$ if and only if $\sigma_i \in D(\beta)$. The set $L(\beta)$ is called the left set of the braid $\beta$.
In general, any notion that is defined on braids can be extended to words by using the braid represented by the word. For example, if a word $w$ represents a braid $\beta$, we define $L(w)$ as the set $L(\beta)$.

**Remark 3.** For all braids $\beta, \gamma \in B^+$, we have $L(\gcd(\beta, \gamma)) = L(\beta) \cap L(\gamma)$.

*Proof.* Let $i \in \mathbb{N}$. Then:

$$ \begin{align*} i \in L(\gcd(\beta, \gamma)) &\Leftrightarrow \sigma_i \le \gcd(\beta, \gamma) \\ &\Leftrightarrow \sigma_i \le \beta \text{ and } \sigma_i \le \gamma \\ &\Leftrightarrow i \in L(\beta) \cap L(\gamma) \end{align*} $$

□

When studying the alternating normal form, we will often work with braids using a specific subset of generators, so we introduce the parabolic sub-monoids of the braid monoid.

**Definition 4 (Parabolic sub-monoid).** For any set of positive integers $I \subset \mathbb{N}$, we define $B_I^+$ the monoid generated by $A_I = \{\sigma_i : i \in I\}$. It is called a parabolic sub-monoid of $B^+$.

For all $I \subset \mathbb{N}$, there is a canonical injection $B_I^+$ to $B_n^+$, where $I \subseteq [1, n]$. In particular, $B_I^+$ is a sub-lattice of $B_n^+$. Furthermore, the monoid $B_I^+$ is isomorphic to an Abelian product of standard braid monoids, each of them corresponding to a maximal segment in $I$. For example, $B_{[1,n-1]}^+ = B_n^+$ and $B_{[1,4]}^+ \cup B_{[7,n+5]}^+ \cong B_{[1,4]}^+ \times B_{[7,n+5]}^+ \cong B_{[1,4]}^+ \times B_{[1,n-1]}^+ \cong B_5^+ \times B_n^+$.

## 2.2. Garside structure

In order to compute the left set of a braid, we will rely on the Garside structure of the monoid: the left-lcm of all the generators in $A_n$ is equal to the right-lcm of all the generators.

**Definition 5 (Garside element).** Let $n \ge 2$. We define $\Delta_n$ the lcm of all the generators in $A_n$, called the Garside element of the standard braid monoid. It is given by $\Delta_2 \equiv \sigma_1$ and $\Delta_{n+1} \equiv \sigma_1\sigma_2 \dots \sigma_n\Delta_n$, see Fig. 2.

<figure><img src="image_3.png" /><figcaption>Figure 2: Two representatives of $\Delta_4$</figcaption></figure>

Left-divisors of $\Delta_n$ are called *simple braids*. As mentioned above, they form a finite lattice $S_n = D(\Delta_n)$ for left-divisibility, whose maximum is $\Delta_n$. Simple braids are exactly braids in which each pair of strands crosses at most once. This leads to a canonical bijection with permutations, by looking at the permutation induced on strands by simple braids. In this context, $\Delta_n$ is sent to the reverse permutation of $[1, n-1]$, while left-divisibility in the braid lattice corresponds to the weak order on permutations [5]. Given a braid $\beta \in B^+$, knowing the largest simple braid that left-divides $\beta$ gives a lot of information about $\beta$, making the following notion very useful.
**Definition 6.** Let $n, m \ge 2$ be two integers and let $\beta \in B_m^+$ be a braid. We define $\alpha_n(\beta) = \text{gcd}(\beta, \Delta_n)$.

Since both $\beta$ and $\Delta_n$ belong to $B_{\max(n,m)}^+$, the braid $\alpha_n(\beta)$ can be computed in $B_{\max(n,m)}^+$ and is always in $S_{\min(n,m)}$.

**Remark 7.** Let $n \ge 2$ be an integer and $\beta \in B_n^+$ be a braid. By Remark 3, we have $L(\alpha_n(\beta)) = L(\beta)$, so $\alpha_n(\beta)$ characterizes $L(\beta)$.

We will also often use the following property, which is non-trivial [5]:

**Proposition 8.** For all $n \ge 2$ and $\beta, \gamma \in B_n^+$, $\alpha_n(\beta\gamma) = \alpha_n(\beta\alpha_n(\gamma))$.

In particular, this last property gives a simple algorithm to compute $\alpha_n$ of a braid from any of its representative. First pre-compute all $\alpha_n(\beta\gamma)$ for $\beta, \gamma \in S_n$. Then for any word $w \in A_n^*$ written as a sequence of letters (or a concatenation of simple words) $w = u_1u_2\dots u_k$, we have $\alpha_n(w) = \alpha_n(u_1\alpha_n(u_2\alpha_n(\dots\alpha_n(u_k))))$, so we can compute $\alpha_n(w)$ from right to left, letter by letter (or simple word by simple word). Thanks to Remark 7, this also gives an efficient algorithm to compute the left set of a braid.

It is easy to check that for all $i \in [1, n-1]$, $\Delta_n\sigma_i \equiv \sigma_{n-i}\Delta_n$. The function $\sigma_i \to \sigma_{n-i}$ on letters is compatible with the relations of $B_n^+$, letting us define the Garside automorphism of the braid monoid.

**Definition 9 (Garside automorphism).** Let $n \ge 2$. We define $\Phi_n$ the automorphism of $B_n^+$ associated with the conjugation by $\Delta_n$, called the Garside automorphism.

This automorphism is a canonical object present in any Garside monoid. In the case of the braid monoid, $\Phi_n$ can be seen as a vertical flip on braids: $\Phi_n$ replaces each letter $\sigma_i$ with $\sigma_{n-i}$, flipping braids vertically. The morphism $\Phi_n$ induces an automorphism on $A_n^*$ and $A_n$, sending $\sigma_i$ to $\sigma_{n-i}$, so we also define $\Phi_n$ directly on $A_n^*$, $A_n$ and $[1, n-1]$ (respectively words, letters and indices). Note that $\Phi_n$ is an involution: $\Phi_n^2$ is the identity automorphism. Since $\Phi_n = \Phi_n^{-1}$, so we will only use $\Phi_n$ from now on. This is not true for any Garside automorphism: for example, in the dual braid monoid, the Garside automorphism has order $n$, where $n$ is the number of strings.

For most functions involving braids and words, it will often be helpful to look at the same function conjugated by $\Phi_n$, so we introduce a specific notation for this conjugation.

**Definition 10.** Let $n \ge 2$, and $A_n, B_n$ two sets on which $\Phi_n$ is defined. Let $\rho$ be a function from $A_n$ to $B_n$. We define $\rho^{\Phi_n} = \Phi_n \circ \rho \circ \Phi_n$.

This conjugation can already be used to express more simply some relations between $\Phi_n$, $\alpha_n$ and the left set.

**Remark 11.** For all integers $n \ge 2$ and braids $\beta \in B_n^+$, $\alpha_n^{\Phi_n}(\beta) = \alpha_n(\beta)$ and $L^{\Phi_n}(\beta) = L(\beta)$. This can also be expressed as $\alpha_n(\Phi_n(\beta)) = \Phi_n(\alpha_n(\beta))$ and $L(\Phi_n(\beta)) = \Phi_n(L(\beta))$.

For any finite $I \subset \mathbb{N}$, we can also define $\Delta_I$ (the lcm of $\sigma_i$ for $i \in I$), $\Phi_I$ (the associated automorphism) and $\alpha_I$ (the gcd of a braid with $\Delta_I$). Since $B_I^+$ is isomorphic to an abelian product of standard braid monoids, these objects also possess mostly the same properties. In particular, Remark 7 generalizes to $\alpha_I$, and if $I = I_1 \cup I_2$ such that $I_1$ and $I_2$ are distant (i.e. there is no $i \in I_1$ and $j \in I_2$ such that $|i-j| \le 1$), then $\Delta_I = \Delta_{I_1}\Delta_{I_2}$. Moreover, if some set $J \subset \mathbb{N}$ (possibly infinite) is distant from $I$, then $\Delta_I$ and $\sigma_j$ commute for all $j \in B_J^+$, so $\Phi_I$ can be extended to braids in $B_{I \cup J}^+$ such that $\Phi_I$ coincides with the identity on $B_J^+$.
### 2.3. Definition of the alternating normal form

The main missing ingredient of the alternating normal form is the way to decompose a braid into braids with fewer strands in a canonical way. To that end, we will introduce the following concept, which is standard in the case where a monoid has submonoids closed under $\text{lcm}$ [4] (Chapter 7, Lemmas 1.1 and 1.4).

**Definition 12** ($B_k^+$-head and $B_k^+$-body). Let $k \ge 2$ be an integer and $\beta \in B^+$ be a braid. The $B_k^+$-head of $\beta$, denoted by $h_k(\beta)$, and the $B_k^+$-body of $\beta$, denoted by $b_k(\beta)$, are braids such that:

* $h_k(\beta) \in B_k^+$ is the maximal (for left-divisibility) braid of $B_k^+$ that left-divides $\beta$,

* $\beta \equiv h_k(\beta)b_k(\beta)$.

Note that the braid $h_k(\beta)$ is the top element of the lattice $D(\beta) \cap B_k^+$. We will also consider the $B_I^+$-head and $B_I^+$-body of a braid when $I \subset \mathbb{N}$, defined the same way.

**Remark 13.** Let $k, n$ be two integers such that $k, n \ge 2$ and $k \le n$. Let $\beta \in B_n^+$ be a braid. Then $h_n(\alpha_k(\beta)) = \alpha_k(h_n(\beta)) = \alpha_n(h_k(\beta)) = h_k(\alpha_n(\beta)) = \alpha_k(\beta)$, so by Remark 3 and Remark 7, $L(h_k(\beta)) = L(\beta) \cap [1, k-1]$. Moreover, by maximality of $h_k(\beta)$, $L(b_k(\beta)) \subseteq [k, n-1]$.

More generally, for any $I, J \subseteq \mathbb{N}$, with $J$ finite, we have $h_I(\alpha_J(\beta)) = \alpha_J(h_I(\beta)) = \alpha_{I \cap J}(\beta)$. Finally, $L(h_I(\beta)) = L(\beta) \cap I$ and $L(b_I(\beta)) \subseteq [1, n-1] \setminus I$.

It is possible to split braids into smaller and simpler braids in many different ways [3]. One such decomposition is the alternating splitting of a braid [3, 4].

**Definition 14** (The alternating splitting). Let $n \ge 3$. The $n$-splitting (or $n$-alternating splitting) of a braid $\beta \in B_n^+$ is the unique sequence $(\beta_0, \beta_1, \dots, \beta_\ell)$ of braids $\beta_i \in B_{n-1}^+$ such that:

* if $\beta$ is trivial, the sequence is empty,

* otherwise, $\beta_0 = h_{n-1}(\beta)$, and $(\beta_1, \dots, \beta_\ell)$ is the $n$-splitting of $\Phi_n(b_{n-1}(\beta))$.

We call blocks the braids forming the $n$-splitting. The integer $\ell$ is called the length of the $n$-splitting and is denoted $\ell_n(\beta)$, with $\ell_n(\varepsilon) = -1$.

This splitting is often defined from right to left instead of left to right because to its links to the Dehornoy ordering of braids [4]. Since these two conventions are equivalent by symmetry, we define it from left to right as it is more natural when studying languages.

If $(\beta_0, \beta_1, \dots, \beta_\ell)$ is the $n$-splitting of a braid $\beta \in B_n^+$, we can write $\beta = \beta_0\Phi_n(\beta_1)\dots\Phi_n^\ell(\beta_\ell)$ by expanding the decomposition. For all integers $i, j \in [0, \ell]$ such that $i \le j$, we define $\beta_{[i:j]} = \beta_i\Phi_n^1(\beta_{i+1})\dots\Phi_n^{j-i}(\beta_j)$. We also define $\beta_{[i:j]} = \beta_{[i:\ell]}$ and $\beta_{[:j]} = \beta_{[0:j]}$, so that $\beta = \beta_{[:i]}\Phi_n^{i+1}(\beta_{[i+1]:})$.

**Example 15.** Let $\beta = \sigma_2\sigma_1\sigma_2\sigma_3\sigma_2\sigma_1\sigma_3\sigma_2$ be a braid of $B_4^+$, for which we want to compute the $4$-splitting.

The first block of the $4$-splitting of $\beta$ is $\beta_0 = h_3(\beta) = \sigma_2\sigma_1\sigma_2\sigma_2$, so that the rest of the braid is $\beta' = b_3(\beta) = \sigma_3\sigma_2\sigma_2\sigma_3\sigma_1\sigma_2$. We then flip this part to continue the $4$-splitting: $\Phi_4(\beta') = \sigma_1\sigma_2\sigma_2\sigma_3\sigma_1\sigma_2$. The next block is $\beta_1 = h_3(\Phi_4(\beta')) = \sigma_1\sigma_2\sigma_2\sigma_1$, giving $\beta_2 = \sigma_1\sigma_2$ as the last block. This proves that the $4$-splitting of $\beta$ is $(\sigma_2\sigma_1\sigma_2\sigma_2, \sigma_1\sigma_2\sigma_2\sigma_1, \sigma_1\sigma_2)$ (see Fig. 3).
<figure><img src="image_4.png" /><figcaption>Figure 3: The 4-splitting ($\sigma_2\sigma_1\sigma_2\sigma_2, \sigma_1\sigma_2\sigma_2\sigma_1, \sigma_1\sigma_2$) of the braid $\beta = \sigma_2\sigma_1\sigma_2\sigma_3\sigma_2\sigma_3\sigma_2\sigma_1\sigma_3\sigma_2$.</figcaption></figure>

**Remark 16.** For all braids $\beta_0, \beta_1, \dots, \beta_\ell \in B_{n-1}^+$, the sequence $(\beta_0, \beta_1, \dots, \beta_\ell)$ is an n-splitting if and only if $(\varepsilon, \beta_1, \dots, \beta_\ell)$ is an n-splitting. Moreover, if $(\beta_0, \dots, \beta_\ell)$ is an n-splitting, then for all $i \in [1, \ell]$, the sequence $(\varepsilon, \beta_i, \dots, \beta_\ell)$ is an n-splitting.

In particular, the braid $\beta_0$ has no influence on whether $(\beta_0, \beta_1, \dots, \beta_\ell)$ is an n-splitting.

We can now define the alternating normal form of a braid, which consists in taking the alternating splitting recursively until it defines a single word [4].

**Definition 17** (The alternating normal form). We define the n-alternating normal form of a braid $\beta \in B_n^+$ the specific representative $\mathrm{Alt}_n(\beta) \in A_n^*$ of $\beta$ defined inductively as follows:

* if $n=2$, then $\mathrm{Alt}_n(\beta)$ is the only representative of $\beta$,

* if $n \ge 3$, then $\mathrm{Alt}_n(\beta) = \mathrm{Alt}_{n-1}(h_{n-1}(\beta)) \mathrm{Alt}_n^{\Phi_n}(b_{n-1}(\beta))$.

It follows from Definition 14 that for all $n \ge 2$, the n-alternating normal form of $\beta$ is given by $\mathrm{Alt}_n(\beta) = \mathrm{Alt}_{n-1}(\beta_0)\Phi_n(\mathrm{Alt}_{n-1}(\beta_1)) \dots \Phi_n^\ell(\mathrm{Alt}_{n-1}(\beta_\ell))$, where $(\beta_0, \beta_1, \dots, \beta_\ell)$ is the n-splitting of $\beta$.

We define $\mathrm{Alt}_n = \mathrm{Alt}_n(B_n^+)$ the set of words in $A_n^*$ in alternating normal form, and $\mathrm{Alt}$ the set of all words in alternating normal form. Note that for all integers $n < m$, a word in $A_n^*$ is in $\mathrm{Alt}_n$ if and only if it is in $\mathrm{Alt}_m$, so we can talk about the alternating normal form of a braid without ambiguity. By induction on $n$, we can see that the language $\mathrm{Alt}_n$ is stable by prefix.

**Definition 18** (The word n-splitting). Let $w \in \mathrm{Alt}_n$ be the alternating normal form of a braid $\beta \in B_n^+$ and let $\ell = \ell_n(\beta)$. The word $w$ can be written $w = w_0\Phi_n(w_1)\dots\Phi_n^\ell(w_\ell)$, such that for all $i \in [0, \ell]$, the word $w_i \in \mathrm{Alt}_{n-1}$ is the alternating normal form of $\beta_i$, the $i^{\mathrm{th}}$ block of the n-splitting of $\beta$. The sequence $(w_0, w_1, \dots, w_\ell)$ is unique, and is called the word n-splitting of $w$.

If $(w_0, w_1, \dots, w_\ell)$ is the word n-splitting of $w$, then for all $i, j \in [0, \ell]$ such that $i \le j$, we define $w_{[i:j]} = w_i \Phi_n^1(w_{i+1}) \dots \Phi_n^{j-i}(w_j)$.

**Example 19.** Let $\beta = \sigma_2\sigma_1\sigma_2\sigma_3\sigma_2\sigma_3\sigma_1\sigma_2$ be a braid of $B_4^+$. We know its 4-splitting is $(\sigma_2\sigma_1\sigma_2\sigma_2, \sigma_1\sigma_2\sigma_2\sigma_1, \sigma_1\sigma_2)$. To get the alternating normal form of $\beta$, we put each block in alternating normal form.
The 3-splitting of $\beta_0 \equiv \sigma_2\sigma_1\sigma_2\sigma_2 \equiv \sigma_1\sigma_1\sigma_2\sigma_1$ is $(\sigma_1\sigma_1, \sigma_1, \sigma_1)$, so its alternating normal form is $Alt_3(\beta_0) = \sigma_1\sigma_1\sigma_2\sigma_1$. The two following blocks only have a single representative each, which is necessarily their alternating normal forms. The alternating normal form of $\beta$ is $Alt_4(\beta) = \sigma_1\sigma_1\sigma_2\sigma_1\Phi_4(\sigma_1\sigma_2\sigma_2\sigma_1)\Phi_4^2(\sigma_1\sigma_2) = \sigma_1\sigma_1\sigma_2\sigma_1\sigma_3\sigma_2\sigma_2\sigma_3\sigma_1\sigma_2$ (see Fig. 4). Moreover, the word 4-splitting of $Alt_4(\beta)$ is $(\sigma_1\sigma_1\sigma_2\sigma_1, \sigma_1\sigma_2\sigma_2\sigma_1, \sigma_1\sigma_2)$.

<figure><img src="image_5.png" /><figcaption>Figure 4: The computation of the 4-alternating normal form $w = \sigma_1\sigma_1\sigma_2\sigma_1\sigma_3\sigma_2\sigma_2\sigma_3\sigma_1\sigma_2$ of the braid $\beta \equiv \sigma_2\sigma_1\sigma_2\sigma_3\sigma_2\sigma_3\sigma_2\sigma_1\sigma_3\sigma_2$ from its 4-splitting. We can see that the word 4-splitting of $w$ is $(w_0, w_1, w_2) = (\sigma_1\sigma_1\sigma_2\sigma_1, \sigma_1\sigma_2\sigma_2\sigma_1, \sigma_1\sigma_2)$.</figcaption></figure>

The $B_{n-2}^+$-head of each block of an $n$-splitting is trivial, except for the first block. This implies that the blocks in an alternating normal form have some constraints on their left-divisors in addition to being in normal form. This motivates the following definition.

**Definition 20.** For all $n \ge 2$ and $i \in [1, n-1]$, we define $Alt_n^i$ the set of words $w \in Alt_n$ such that $L(w) \subseteq \{i\}$, i.e., $w$ is empty or $L(w) = \{i\}$.

We will often use this notation when $i \in \{1, n-1\}$, as those braids appear naturally in the alternating decomposition. Note that in particular $Alt_n^i = Alt_{n+1}^i \cap A_n^*$, as was the case for $Alt_n$. Moreover, using Remark 16, we can see that $Alt_n = Alt_{n-1}\Phi_n(Alt_n^1)$, which means we can study $Alt_n^1$ to deduce properties on $Alt_n$ inductively.

## 2.4. Results

In this article, we prove a simple characterization of the alternating decomposition and the alternating normal form, construct an automaton recognizing this normal form using the characterization, and then prove its minimality.

**Theorem 37 (Characterization of the alternating normal form).** Let $w \in A_n^*$. The word $w$ is in $n$-alternating normal form ($Alt_n$) if and only if: $n = 2$, or $n \ge 3$ and it can be written:

$$w = w_0\Phi_n(w_1)w_2\dots\Phi_n^\ell(w_\ell)$$

such that:

(0) The word $w_0$ is in $Alt_{n-1}$.
(1) For all $i \in [1, \ell]$, $w_i \in A_{n-1}$ is non-empty, and the word $\Phi_{n-1}(w_i)$ is in $Alt_{n-1}$ and begins with the letter $\sigma_{n-2}$.

(2) For all $i \in [1, \ell - 1]$, consider the minimal $k_i < n$ such that $\sigma_{n-1} \dots \sigma_{k_i}$ is a prefix of $\Phi_n(w_{[i+1]})$; then $w_i$ contains the letters $\sigma_{n-2}$ and $\sigma_{k_i-1}$ in this order.

Moreover, in this case, $(w_0, w_1, \dots, w_\ell)$ is the word n-splitting of w.

The condition (2) implies in particular that $w_i \in Alt_{n-1}^1$ for all $i \ge 1$. This characterization helps construct the minimal automaton of the alternating normal form, for which we get multiple properties.

**Theorem 54-55.** For all $n \ge 2$, $Alt_n$ is regular, and the minimal automaton $A_n$ recognizing $Alt_n$ can be described explicitly. It has $s_n$ states and $t_n$ transitions, where

$$s_n = \frac{25 \times 2^{2n-3} - 9n^2 + 3n + 7}{27} \quad \text{and} \quad t_n = \frac{(225n - 290)2^{2n-5} - 9n^3 - 9n^2 + 93n - 77}{81}.$$

Analogous results were proven by Jean Fromentin in [6], which shows a similar characterization for the rotating normal form in the dual braid monoid and also constructs a finite automaton recognizing the language (which, while not proven in [6], is in fact also minimal).

### 3. Alternating normal form characterization

In this section, we prove a new characterization of the alternating normal form, similar to known results for the rotating normal form [6] and the Garside normal form [8].

In Section 3.1, we introduce and study two braid invariants, which are properties verified by all or none of a braid representatives. First, in Section 3.1.1, we define the notion of chains, which are sub-words of the form $\sigma_{i \to j}$ (defined as $\sigma_i \sigma_{i+1} \dots \sigma_{j-1} \sigma_j$ or $\sigma_i \sigma_{i-1} \dots \sigma_{j+1} \sigma_j$ depending on the sign of $i - j$). This leads to the introduction of the first braid invariant, $ch_n$: the longest $\sigma_{n-1 \to j}$ chain present in a braid (Definition 25). In Section 3.1.2, we prove some properties regarding the left set and $\alpha_n$. We use those results to define the second braid invariant, $st_n$: the longest factor of the form $\sigma_{n-1 \to j}$ at the start of a braid (Definition 31). Finally, in Section 3.2, we use those two invariants to characterize alternating splittings (Theorem 36) and alternating normal forms (Theorem 37).

#### 3.1. Braid invariants

In order for a sequence $(\beta_0, \beta_1, \dots, \beta_\ell)$ to be an alternating splitting, each block must be maximal. In practice, only two conditions need to be verified. The first condition is that that no letter can go from a block $\beta_i$ to $\beta_{i-1}$, which is easily checked by ensuring that the left set of each block is reduced to $\{1\}$. The second condition is that no letter can go from $\beta_{i+1}$ to $\beta_{i-1}$, which is not so simply characterized. It requires checking whether $\beta_i$ can prevent letters moving from $\beta_{i+1}$ to $\beta_{i-1}$, which is done by comparing $ch_{n-1}(\beta_i)$ with $st_{n-1}^{\Phi_{n-1}}(\beta_{i+1})$. Those two conditions will then lead a characterization of the alternating splitting, and from that we will deduce a characterization of the alternating normal form.
### 3.1.1. The first invariant: containing a chain

A sub-word of a word $w$ is a sequence of letters of $w$ that may or may not be contiguous. This is notably different from factors, which is a sequence of contiguous letters. For example, the word $\sigma_4\sigma_2\sigma_3$ is a factor and a sub-word of $w = \sigma_1\sigma_2\sigma_4\sigma_2\sigma_3$, the word $\sigma_2\sigma_2$ is a sub-word but not a factor of $w$, and $\sigma_2\sigma_3\sigma_2$ is neither a sub-word nor a factor of $w$.

**Definition 21 (Chains).** When $1 \le a \le b$, let $\sigma_{a \to b}$ and $\sigma_{b \to a}$ denote the words $\sigma_a\sigma_{a+1}\dots\sigma_{b-1}\sigma_b$ and $\sigma_b\sigma_{b-1}\dots\sigma_{a+1}\sigma_a$. Those are called respectively $\sigma_{a \to b}$-chain and $\sigma_{b \to a}$-chain, or simply chains.

Each chain is the only word representing its braid, so we can identify the word with the braid, and will use the same notation for both. When a word contains a $\sigma_{a \to b}$-chain as a sub-word, we will simply say that it contains a $\sigma_{a \to b}$-chain (see Fig. 5).

**Definition 22 (Isolated chains).** Let $a, b \in [1, n]$, with $a \le b$. We say that a word $w \in A_n^*$ contains an decreasing isolated $\sigma_{b \to a}$-chain if there exist words $u_{a-1}, \dots, u_b \in A_n^*$ such that $w = u_b\sigma_b u_{b-1}\sigma_{b-1} \dots u_a\sigma_a u_{a-1}$, and for all $i \in [a-1, b]$, $u_i$ does not contain any $\sigma_i$ nor $\sigma_{i+1}$.

In particular, if a word contains an isolated chain, it contains the associated chain. The definition can be adapted when $b < a$ to define an increasing isolated $\sigma_{b \to a}$-chain. When $a \ne b$, we know whether an isolated chain is increasing or decreasing, so we simply say isolated chain (see Fig. 5).

<figure><img src="image_6.png" /><figcaption>Figure 5: A green $\sigma_{3 \to 1}$-chain and a red isolated $\sigma_{4 \to 1}$-chain in the word $\sigma_3\sigma_1\sigma_2\sigma_4\sigma_2\sigma_3\sigma_1\sigma_4\sigma_2\sigma_1\sigma_2$.</figcaption></figure>

In practice, a word contains an isolated $\sigma_{b \to a}$-chain if the strand $b$ only crosses the strands in $[a, b-1]$, and each of them exactly once. This can give an intuition as to why containing an isolated chain is a braid invariant.

**Remark 23.** Let $a, c \in [1, n-1]$ be two integers with $a < c$ and let $u, v, w \in A_n^*$ be words such that $w = uv$. The word $w$ contains an increasing (isolated) $\sigma_{a \to c}$-chain if and only if there exists $b \in [a, c-1]$ such that $u$ contains an increasing (isolated) $\sigma_{a \to b}$-chain and $v$ contains an increasing (isolated) $\sigma_{b+1 \to c}$-chain.

The same is true for decreasing chains.

We will now prove that the existence of chains is a braid invariant, i.e. does not depend on the word representative of the braid.

**Lemma 24 (Containing an (isolated) chain is a braid property).** Let $\beta \in B_n^+$ and $a, b \in [1, n-1]$. Suppose a representative of $\beta$ contains an (isolated) $\sigma_{a \to b}$-chain. Then all representatives of $\beta$ also contain an (isolated) $\sigma_{a \to b}$-chain.
*Proof.* We can suppose by symmetry that $a \le b$ and only look at increasing (isolated) chains. It suffices to prove that the property "containing an increasing (isolated) chain" is preserved by commutation and braid relations.

Suppose $a = b$. Braid and commutation relations preserve the list of letters contained in a word, so all representative of $\beta$ contain the same list of letters. This implies that if a representative of $\beta$ contains an $\sigma_{a \to a}$-chain, then they all do. A representative that contains an increasing isolated $\sigma_{a \to a}$-chain contains only one $\sigma_a$, with no $\sigma_{a-1}$ to its left and no $\sigma_{a+1}$ to its left. This property is preserved by all relations, since commutation relations do, and no braid relations can involve the letter $\sigma_a$ under those conditions. This implies that if a representative of $\beta$ contains an increasing isolate $\sigma_{a \to a}$-chain, then they all do.

We can now suppose that $a < b$. Consider a representative $w \in A_n^*$ of $\beta$ that contains an (isolated) $\sigma_{a \to b}$-chain. Consider a relation on $w$ such that $w \equiv w'$ through this relation.

Suppose $b = a + 1$, so that there exist three words $u_a, u_{a+1}, u_{a+2} \in A_n^*$ such that $w = u_a\sigma_a u_{a+1}\sigma_{a+1}u_{a+2}$. Suppose the relation involves only letters of the prefix $u_a\sigma_a u_{a+1}$. We can observe that $u_a\sigma_a u_{a+1}$ contains an (isolated) $\sigma_{a \to a}$-chain and $\sigma_{a+1}u_{a+2}$ contains a (isolated) $\sigma_{a+1 \to a+1}$-chain. By the case $a=b$, $u_a\sigma_a u_{a+1}$ still contains an (isolated) $\sigma_{a \to a}$-chain after the operation. So by Remark 23, $w'$ contains an (isolated) $\sigma_{a \to a+1}$-chain. The same reasoning holds if the relation involves only letters of the suffix $u_{a+1}\sigma_{a+1}u_{a+2}$. Otherwise, the relation must involve both $\sigma_a$ and $\sigma_{a+1}$. The only possible relation is a braid relation, which implies that $u_{a+1}$ is empty, and the relation must exchange the words $u_a\sigma_a\sigma_{a+1}(\sigma_a u'_{a+2})$ and $(u'_a\sigma_{a+1})\sigma_a\sigma_{a+1}u_{a+2}$. Both words contain an $\sigma_{a \to a+1}$-chain, and if one contains an isolated $\sigma_{a \to a+1}$-chain, then the other does too, which ends this case.

Suppose $b \ge a+2$, so that there exist $u_a, u_{a+1}, \dots, u_{b+1} \in A_n^*$ such that $w = u_a\sigma_a u_{a+1} \dots u_b\sigma_b u_{b+1}$. We can suppose by induction on $b-a$ that the theorem is true for braids that contain shorter (isolated) $\sigma_{a \to b}$-chains. The relation concerns at most two letters from the chain, so it is either included in the prefix $u_a\sigma_a u_{a+1} \dots u_b$ or the suffix $u_{a+1} \dots u_b\sigma_b u_{b+1}$. In both cases, thanks to the induction hypothesis and Remark 23, we can conclude that $w'$ contains an (isolated) $\sigma_{a \to b}$-chain. $\square$

Since chains and isolated chains are preserved in all representatives of a braid, it makes sense to talk about a braid containing a $\sigma_{a \to b}$-chain or an isolated $\sigma_{a \to b}$-chain. This property leads to the definition of the first braid invariant.

**Definition 25** (The braid invariant ch). Let $k \ge 2$ and $\beta \in B^+$. Let $r$ be the least integer such that $\beta$ contains a decreasing $\sigma_{k-1 \to r}$-chain, with $r = k$ if $\beta$ does not contain any $\sigma_{k-1}$. We define $\text{ch}_k(\beta) = r$.

For all $n \ge 2$, $\text{ch}_n^{\Phi_n}$ is well-defined on $B_n^+$, and its value does not depend on $n$, so we can extend it to a morphism $\text{ch}^{\Phi}$ defined on $B^+$. For all $\beta \in B^+$, $\text{ch}^{\Phi}(\beta)$ is equal to the largest integer such that $\beta$ contains an increasing $\sigma_{1 \to \text{ch}(\beta)}$-chain, with $\text{ch}^{\Phi}(\beta) = 0$ if $\beta$ does not contain any $\sigma_1$.

Chains being one the main class of braids we will manipulate, it will be useful to have some properties on the conjugation by chains. Consider two integers $i \le j$. Since $\Delta_{[i,j]} \equiv \sigma_{i \to j} \Delta_{[i,j-1]}$, we can deduce that $\Phi_{[i,j]}\Phi_{[i,j-1]}^{-1} = \Phi_{[i,j]}\Phi_{[i,j-1]}$ is the morphism that corresponds to the left-conjugation by $\sigma_{i \to j}$. It is well defined on $B_I^+$, with $I = \mathbb{N}^* \setminus \{i-1, j, j+1\}$. This leads to the following definition.

**Definition 26** (Conjugation by chains). Let $i, j \in \mathbb{N}^*$ two integers such that $i \le j$. Let $I = \mathbb{N}^* \setminus \{i-1, j, j+1\}$ and $J = \mathbb{N}^* \setminus \{i-1, i, j+1\}$. We define $\phi_i^j$, the morphism associated to the
left-conjugation by $\sigma_{i \to j}$ (or equivalently the right-conjugation by $\sigma_{j \to i}$), defined on $B_I^+$ and with values in $B_J^+$, such that for all $\beta \in B_I^+$, $\beta\sigma_{i \to j} \equiv \sigma_{i \to j}\phi_i^j(\beta)$.

The morphism $\phi_i^j$ can be extended to $A_I^*$, $A_I$ and $I$, with values respectively in $A_J^*$, $A_J$ and $J$.

Note that $\phi_i^j(k) = \begin{cases} k+1 & \text{if } k \in [i, j-1]. \\ k & \text{if } k \in \mathbb{N}^* \setminus [i-1, j+1]. \end{cases}$

The morphism $(\phi_i^j)^{-1}$ is well defined and will be denoted by $\phi_j^i$. It is defined on $B_J^+$, has values in $B_I^+$, and corresponds to the left-conjugation by the decreasing chain $\sigma_{j \to i}$.

We can now use chains and isolated chains to limit the mobility of letters in a word.

**Lemma 27.** Let $n \ge 2$ and $a, b \in [1, n-1]$, with $a \le b$. Let $\beta \in B_n^+$ be a braid that contains a decreasing isolated $\sigma_{b \to a}$-chain and no $\sigma_{b+1}$.

There exists a braid $\beta' \in B_n^+$ such that $\beta \equiv \beta'\sigma_{b \to a}$, and $\beta'$ does not contain any $\sigma_b$. Moreover, if $\beta$ (or, equivalently, $\beta'$) contains a $\sigma_{(b-1) \to (a-1)}$-chain, then $L(\beta') = L(\beta)$.

*Proof.* Let $w \in A_n$ be a representative of $\beta$. Since $w$ contains a decreasing isolated $\sigma_{b \to a}$-chain there exists a sequence of words $u_b, u_{b-1}, \dots, u_a, u_{a-1} \in A_n$ such that $w = u_b\sigma_b u_{b-1}\sigma_{b-1} u_{b-2} \dots u_{a+1}\sigma_{a+1} u_a\sigma_a u_{a-1}$. For all $i \in [a-1, b]$, since the $\sigma_{b \to a}$-chain is isolated, there is no letter $\sigma_{i+1}$ or $\sigma_i$ in $u_i$.

We show the first part by decreasing induction on $a$. Suppose $a = b$, so that $w = u_b\sigma_b u_{b-1}$. The word $u_{b-1}$ does not contain the letters $\sigma_b$, $\sigma_{b-1}$ and $\sigma_{b+1}$, so $u_{b-1}$ and $\sigma_b$ commute. This implies that $\beta \equiv u_b\sigma_b u_{b-1} \equiv u_b u_{b-1}\sigma_b$, so that $\beta \equiv \beta'\sigma_{b \to b}$, with $\beta' \equiv u_b u_{b-1}$. The braid $\beta'$ does not contain the letter $\sigma_b$ since $u_b$ and $u_{b-1}$ do not contain the letter $\sigma_b$.

Suppose that $a < b$ and that the first part of the lemma is true for $a+1$. Let $\beta_a \in B_n^+$ the braid represented by $w_a = u_b\sigma_b u_{b-1}\sigma_{b-1} u_{b-2} \dots u_{a+1}\sigma_{a+1} u_a$, so that $w = w_a\sigma_a u_{a-1}$ and $\beta \equiv \beta_a\sigma_a u_{a-1}$. The braid $\beta_a$ contains a decreasing isolated $\sigma_{b \to (a-1)}$-chain and no $\sigma_{b+1}$. By induction hypothesis, there exists a braid $\beta'_a \in B_n^+$ that does not contain the letter $\sigma_b$ such that $\beta_a \equiv \beta'_a\sigma_{b \to a+1}$, so that $\beta \equiv \beta'_a\sigma_{b \to a+1}\sigma_a u_{a-1} \equiv \beta'_a\sigma_{b \to a}u_{a-1}$. The word $u_{a-1}$ does not contain the letters $\sigma_a$ and $\sigma_{a-1}$, and no $\sigma_{b+1}$ by hypothesis. By Definition 26, we have $\sigma_{b \to a}u_{a-1} \equiv \phi_b^a(u_{a-1})\sigma_{b \to a}$. So $\beta \equiv \beta'\sigma_{b \to a}$, with $\beta' \in B_n^+$ the braid $\beta' \equiv \beta'_a\phi_b^a(u_{a-1})$. The word $\phi_b^a(u_{a-1})$ does not contain the letter $\sigma_b$, so $\beta'$ does not contain $\sigma_b$ by concatenation, which ends the induction.

Since $\beta'$ does not contain the letter $\sigma_b$ and $L(\sigma_{b \to a}) = \{b\}$, we can deduce that $\beta' \equiv h_I(\beta)$, with $I = [1, n-1] \setminus \{b\}$. By Remark 13, we get $L(\beta') = L(\beta) \cap I = L(\beta) \setminus \{b\}$. Suppose that $\beta$ contains a $\sigma_{(b-1) \to (a-1)}$-chain. The word $u_{a-1}$ does not contain the letter $\sigma_{a-1}$, so the rightmost $\sigma_{a-1}$ in $w$ is included in $w_a \equiv u_b\sigma_b u_{b-1}\sigma_{b-1} \dots u_{a+1}\sigma_{a+1} u_a$, which must then contain a $\sigma_{b-1 \to a}$-chain. By induction, we deduce that $u_b$ contains a $\sigma_{b-1 \to b}$-chain, i.e., $u_b$ contains the letter $\sigma_{b-1}$. In particular, the word $u_b$ is not empty. Since $u_b$ does not contain the letter $\sigma_b$, the word $w$ does not begin with the letter $\sigma_b$. Since $w$ is an arbitrary representative of $\beta$, this implies that $b \notin L(\beta)$, so $L(\beta') = L(\beta) \setminus \{b\} = L(\beta)$. $\square$

We now want some criteria for the existence of chains. We first prove a weak sufficient condition for braids to contain chains.

**Lemma 28.** Let $\beta \in B^+$ be a braid that contains the letter $\sigma_j$. Then there exists $i \in L(\beta)$ such that $\beta$ contains a $\sigma_{i \to j}$-chain.

*Proof.* The result is immediate if $\beta$ is of length one, so that $\beta \equiv \sigma_j$. Suppose $\beta$ contains at least two letters. Let $w \in A^*$ be a word representing $\beta$. There exist two words $u, v \in A^*$ such that $w = u\sigma_j v$ with no $\sigma_j$ in $u$, by considering the left-most $\sigma_j$ in $w$. If $u$ contains no $\sigma_{j-1}$ and no
$\sigma_{j+1}$, then $u\sigma_j \equiv \sigma_j v$, so $j \in L(\beta)$, and $\beta$ contains a $\sigma_{j \to j}$-chain. Otherwise, $u$ contains $\sigma_{j-1}$ or $\sigma_{j+1}$. By induction on the length of $\beta$, there exists $i \in L(u)$ such that $u$ contains a $\sigma_{i \to k}$-chain with $k \in \{j-1, j+1\}$. If $j \in [i, k]$, then $u$ contains in particular a $\sigma_{i \to j}$-chain, so $\beta$ does too. Otherwise, $\sigma_{i \to k} \sigma_j \equiv \sigma_{i \to j}$, so $u\sigma_j$ contains a $\sigma_{i \to j}$-chain, so $\beta$ does too. $\square$

We can now deduce necessary and sufficient conditions for a braid to contain a chain, and some important consequences.

**Proposition 29.** Let $\beta \in B^+$ be a braid and $j \le k$ be two integers. The following statements are equivalent:

1. The braid $\beta$ contains a $\sigma_{k \to j}$-chain, i.e., $ch_{k+1}(\beta) \le j$.

2. The $B_k^+$-body of $\beta$ contains a letter $\sigma_j$.

3. The alternating normal form $w$ of $\beta$ contains $\sigma_k \sigma_j$ as a sub-word.

Moreover, if $\beta$ contains no letter $\sigma_{k+1}$ or $\sigma_{k+2}$, these statements are also equivalent to:

4. $L(\beta\sigma_{k+1 \to j+1}) = L(\beta)$.

5. $k+1 \notin L(\beta\sigma_{k+1 \to j+1})$.

*Proof.* If 1 is valid, then the alternating normal form $w$ of $\beta$ contains a $\sigma_{k \to j}$-chain, so $w$ contains the subword $\sigma_k \sigma_j$, and 3 is valid.

Suppose 3 is valid. The word $w$ is in alternating normal form, so it can be written $w_0 w'$, with $w_0$ a representative of $h_k(\beta)$ and $w'$ a representative of $b_k(\beta)$. Since $w_0 \in B_k^+$, the word $w_0$ does not contain the letter $\sigma_k$, so the sub-word $\sigma_k \sigma_j$ of $w$ is also a sub-word of $w'$. This implies that $b_k(\beta)$ contains the letter $\sigma_j$, so 2 is valid.

Suppose 2 is valid. By Remark 13, we have $L(b_k(\beta)) \subset [k, n-1]$. By Lemma 28, the braid $b_k(\beta)$ contains a decreasing $\sigma_{k' \to j}$-chain, with $k' \in [k, n-1]$, so it contains a $\sigma_{k \to j}$-chain, which implies that 1 is valid, so $1 \Leftrightarrow 2 \Leftrightarrow 3$.

Now, suppose in addition that $\beta$ contains no letter $\sigma_{k+1}$ or $\sigma_{k+2}$. If 1 is valid, the braid $\beta\sigma_{k+1 \to j+1}$ contains both a decreasing $\sigma_{k \to j}$-chain and a decreasing isolated $\sigma_{k+1 \to j+1}$-chain, hence Lemma 27 proves that $L(\beta\sigma_{k+1 \to j+1}) = L(\beta)$, so 4 is valid. The braid $\beta$ does not contain the letter $\sigma_{k+1}$, so $k+1 \notin L(\beta)$, thus $4 \Rightarrow 5$. If 2 is invalid, then $b_k(\beta)$ contains no letter $\sigma_j$, $\sigma_{k+1}$ or $\sigma_{k+2}$, so Definition 26 implies that $b_k(\beta)\sigma_{k+1 \to j+1} \equiv \sigma_{k+1 \to j+1}\phi_{j+1}^{k+1}(b_k(\beta))$. Since $h_k(\beta) \in B_k^+$, the braid $h_k(\beta)$ commutes with $\sigma_{k+1}$, so $h_k(\beta)\sigma_{k+1} \equiv \sigma_{k+1}h_k(\beta)$, which implies that $k+1 \in L(\beta\sigma_{k+1 \to j+1})$, so 5 is invalid, proving $5 \Rightarrow 2$. $\square$

Note that by applying $\Phi_n$, we can also treat the case where $j > k$. To prove the characterization, we actually only apply this lemma when $\beta \in B_n^+$ and $k = n-1$, but the more general result will be useful to prove further results on the alternating normal form, in particular its left-automaticity [11].

### 3.1.2. The second invariant: the start of a braid

Before introducing the next main braid invariant, we need some properties about braids with a constrained left set.
**Lemma 30.** A braid $\beta \in B_n^+$ satisfies $L(\beta) = \{n-1\}$ if and only if $\beta$ is non-trivial and $h_{n-1}(\beta)$ is trivial (i.e., the first block of the n-splitting of $\beta$ is trivial).

In this case, there exists an integer $r \in [1, n-1]$ such that $\alpha_n(\beta) = \sigma_{n-1 \to r}$, and either $\beta$ is simple (so $\beta = \sigma_{n-1 \to r}$), or $\sigma_{n-1 \to r} \sigma_r$ is a prefix of all words representing $\beta$ (so, in particular, $\sigma_{n-1 \to r} \sigma_r \le \beta$). Letting $\beta' \in B_n^+$ be the braid such that $\beta = \alpha_n(\beta)\beta'$, this also implies that $L(\beta') \subseteq \{r\}$.

*Proof.* First note that $L(\beta) = \{n-1\}$ if and only if $L(\beta) \ne \emptyset$ and $L(\beta) \cap [1, n-2] = \emptyset$. By Remark 13, we have $L(h_{n-1}(\beta)) = L(\beta) \cap [1, n-2]$, which implies that $L(\beta) = \{n-1\}$ if and only if $\beta$ is non-trivial and $h_{n-1}(\beta)$ is trivial.

We will now prove the additional properties. Let $r \in [1, n-1]$ be the least integer such that $\sigma_{n-1 \to r}$ left-divides $\beta$, which exists since $\sigma_{n-1} \le \beta$. Let $\beta' \in B_n^+$ be the braid such that $\beta = \sigma_{n-1 \to r} \beta'$. For all $k \in [1, r-2]$, we have $\sigma_{n-1 \to r} \sigma_k = \sigma_k \sigma_{n-1 \to r}$, but $k \notin L(\beta)$, so by contraposition, $k \notin L(\beta')$. For all $k \in [r+1, n-1]$, we have $\sigma_{n-1 \to r} \sigma_k = \sigma_{k-1} \sigma_{n-1 \to r}$, but $k-1 \notin L(\beta)$, so $k \notin L(\beta')$. Finally, for $k = r-1$, we have $\sigma_{n-1 \to r} \sigma_k = \sigma_{n-1 \to r-1}$, but $r$ is minimal, so $k \notin L(\beta')$. So $L(\beta') \subseteq \{r\}$.

Since the braid $\sigma_{n-1 \to r}$ is simple, $\sigma_{n-1 \to r} \le \alpha_n(\beta)$. Let $\gamma \in B_n^+$ be the braid such that $\alpha_n(\beta) = \sigma_{n-1 \to r} \gamma$. Since $\gamma \le \beta'$, we have $L(\gamma) \subseteq \{r\}$. The braid $\sigma_{n-1 \to r} \sigma_r$ is not simple, so $r \notin L(\gamma)$, so that $L(\gamma) = \emptyset$, which means that $\gamma$ is trivial and that $\alpha_n(\beta) = \sigma_{n-1 \to r}$. Finally, if $\beta$ is simple, then $\beta = \sigma_{n-1 \to r}$. Otherwise, $\beta'$ is non-trivial, so $L(\beta') = \{r\}$, which implies that $\sigma_{n-1 \to r} \sigma_r$ left-divides $\beta$. The word $\sigma_{n-1 \to r} \sigma_r$ is a prefix of all words representing $\beta$ since there exists no relation that can modify this prefix without contradicting $L(\beta') = \{r\}$. $\square$

Thanks to Lemma 30, we can now define the second braid invariant.

**Definition 31** (The braid invariant st). Let $n, k \ge 2$ and $\beta \in B_n^+$. If there exists an integer $r \in [1, k-1]$ such that $\alpha_n(\beta) = \sigma_{(k-1) \to r}$, we define $\text{st}_k(\beta) = r$; otherwise we set $\text{st}_k(\beta) = k$.

For all $n \ge 2$, $\text{st}_n^\Phi$ is well defined on $B_n^+$, and its value does not depend on $n$, so we can extend it to a morphism $\text{st}^\Phi$ defined on $B^+$. For all $\beta \in B_n^+$, $\text{st}^\Phi(\beta)$ is equal to the integer $r \in [1, \infty]$ such that $\alpha_n(\beta) = \sigma_{1 \to r}$, and $\text{st}^\Phi(\beta) = 0$ if no such integer exists.

We now give a case where we can easily compute $\alpha$ and, by extension, st.

**Lemma 32.** Let $n$ and $k$ be integers such that $n \ge 2$ and $k \in [2, n]$. Let $\beta \in B_n^+$ be a braid such that $L(\beta) = \{1\}$ and $h_k(\beta)$ is not simple. Then $\alpha_n(\beta) = \alpha_n(h_k(\beta)) = \alpha_k(\beta)$ and $\text{st}^\Phi(\beta) = \text{st}^\Phi(h_k(\beta))$.

*Proof.* By Remark 13, $L(h_k(\beta)) = L(\beta) \cap [1, k-1] = \{1\}$, and $\alpha_k(\beta) = \alpha_n(h_k(\beta))$. Let $r = \text{st}^\Phi(\beta)$ and $s = \text{st}^\Phi(h_k(\beta))$, so that $\alpha_n(\beta) = \sigma_{1 \to r}$ and $\alpha_k(\beta) = \sigma_{1 \to s}$.

The braid $h_k(\beta)$ is not simple, so by Lemma 30, $\sigma_{1 \to r} \sigma_r \le h_k(\beta)$. Since $h_k(\beta) \le \beta$, we have $\sigma_{1 \to r} \sigma_r \le \beta$, so there exists a representative of $\beta$ that starts with $\sigma_{1 \to r} \sigma_r$. On the other hand, $\beta$ is not simple, so by Lemma 30 all representatives of $\beta$ start with $\sigma_{1 \to s} \sigma_s$. This implies that $r = s$, so $\alpha_n(\beta) = \alpha_k(\beta)$ and $\text{st}^\Phi(\beta) = \text{st}^\Phi(h_k(\beta))$. $\square$

## 3.2. Characterization of the alternating splitting and the alternating normal form

We will now prove the last few lemmas needed to get the characterization.

**Lemma 33 (Flipping the normal form).** Let $\beta \in B_n^+$ and $\beta_0, \beta_1, \dots, \beta_\ell \in B_{n-1}^+$ be braids such that $\beta = \beta_0 \Phi_n(\beta_1) \dots \Phi_n^\ell(\beta_\ell)$. Then $L(\beta) = \{1\}$ and $(\beta_0, \beta_1, \dots, \beta_\ell)$ is the n-splitting of $\beta$ if and only if $(\varepsilon, \beta_0, \beta_1, \dots, \beta_\ell)$ is the n-splitting of $\Phi_n(\beta)$.
In particular, a word $w \in A_n^*$ such that $L(w) = \{1\}$ or $L(w) = \{n-1\}$ is in $Alt_n$ if and only if $\Phi_n(w)$ is in $Alt_n$. Said another way, for all $\beta \in B_n^+$ such that $L(\beta) = \{1\}$ or $L(\beta) = \{n-1\}$, $Alt_n^{\Phi_n}(\beta) = Alt_n(\beta)$.

**Proof.** Suppose $L(\beta) = \{1\}$ and $(\beta_0, \beta_1, \dots, \beta_\ell)$ is the $n$-splitting of $\beta$. Since $L(\Phi_n(\beta)) = \{n-1\}$, by Lemma 30, $h_{n-1}(\Phi_n(\beta))$ is trivial, so the $n$-splitting of $\Phi_n(\beta)$ is $\varepsilon$, followed by the $n$-splitting of $\Phi_n(\Phi_n(\beta)) = \beta$, i.e., $(\varepsilon, \beta_0, \beta_1, \dots, \beta_\ell)$.

Conversely, suppose $(\varepsilon, \beta_0, \beta_1, \dots, \beta_\ell)$ is the $n$-splitting of $\Phi_n(\beta)$. Then $h_{n-1}(\Phi_n(\beta))$ is trivial, so by Lemma 30, $L(\Phi_n(\beta)) = \{n-1\}$, which implies that $L(\beta) = \{1\}$. Moreover, since $(\varepsilon, \beta_0, \beta_1, \dots, \beta_\ell)$ is the $n$-splitting of $\Phi_n(\beta)$, we know that $h_{n-1}(\Phi_n(\beta)) = \varepsilon$ and $(\beta_1, \dots, \beta_\ell)$ is the $n$-splitting of $\Phi_n(b_{n-1}(\Phi_n(\beta))) = \Phi_n(\Phi_n(\beta)) = \beta$, so the $n$-splitting of $\beta$ is $(\beta_0, \beta_1, \dots, \beta_\ell)$.

The result on words in normal form is a direct consequence of the result on splittings. $\square$

We can deduce from Lemma 33 that for all $w \in A_n^*$, we have $w \in Alt_n^1$ if and only if $\Phi_n(w) \in Alt_n^{n-1}$, so in particular $Alt_n^{n-1} = \Phi_n(Alt_n^1)$. Note that by Lemma 30, the hypothesis $L(\beta) = \{n-1\}$ (resp. $L(\beta) = \{1\}$) can be replaced by $h_{n-1}(\beta)$ being trivial (resp. $h_{n-1}^{\Phi_n}(\beta)$ being trivial).

We are now able to concatenate braids and characterize the value of the new left set using $ch$ and $st$.

**Lemma 34.** Let $\gamma \in B_{n-1}^+$ and $\beta \in B_n^+$ be braids such that $L(\gamma) = \{1\}$ and $L(\beta) = \{n-1\}$. Then $L(\gamma\beta) = \{1\}$ if and only if $st_n(\beta) > ch_{n-1}(\gamma)$.

Moreover, in this case, either $\gamma = \sigma_{1 \to n-2}$, in which case $st^\Phi(\gamma\beta) = n-1$, or $\gamma$ is not simple and $st^\Phi(\gamma\beta) = st^\Phi(\gamma)$.

**Proof.** Suppose that $L(\gamma\beta) = \{1\}$. Since $\sigma_{(n-1) \to st_n(\beta)}$ left-divides $\beta$, we have $\{1\} = L(\gamma) \subseteq L(\gamma\sigma_{(n-1) \to st_n(\beta)}) \subseteq L(\gamma\beta) = \{1\}$, so $L(\gamma\sigma_{n-1 \to st_n(\beta)}) = \{1\}$. By 4 $\Rightarrow$ 1 of Proposition 29, we have $ch_{n-1}(\gamma) < st_n(\beta)$.

Conversely, suppose that $st_n(\beta) > ch_{n-1}(\gamma)$. By 1 $\Rightarrow$ 4 of Proposition 29, we have $L(\gamma\sigma_{n-1 \to st_{n-1}(\beta)}) = L(\gamma) = \{1\}$. On the other hand, $\alpha_n(\beta) = \sigma_{n-1 \to st_n(\beta)}$, so that $\alpha_n(\gamma\beta) = \alpha_n(\gamma\alpha_n(\beta)) = \alpha_n(\gamma\sigma_{n-1 \to st_n(\beta)})$. By Remark 7, this implies that $L(\gamma\beta) = L(\gamma\sigma_{n-1 \to st_n(\beta)}) = \{1\}$.

We now prove the second part. Assume $L(\gamma\beta) = \{1\}$. If $\gamma$ is simple, then by Lemma 30, there exists an integer $r \in [1, n-2]$ such that $\gamma = \sigma_{1 \to r}$. Since $L(\beta) = \{n-1\}$ and $L(\gamma\beta) = \{1\}$, we have $r = n-2$, so $\gamma = \sigma_{1 \to n-2}$. This implies that $st^\Phi(\gamma\beta) \ge n-1$, and since $\gamma\beta \in B_n^+$, we get $st^\Phi(\gamma\beta) = n-1$.

Otherwise, $\gamma$ is not simple, so Lemma 32 proves that $st^\Phi(\gamma\beta) = st^\Phi(\gamma)$. $\square$

We can reformulate this result using alternating splittings thanks to Lemma 33.

**Lemma 35.** Suppose $(\varepsilon, \beta_1, \beta_2, \dots, \beta_\ell)$ and $(\varepsilon, \gamma)$ are $n$-splittings of $\beta$ and $\Phi_n(\gamma)$. Then $(\varepsilon, \gamma, \beta_1, \beta_2, \dots, \beta_\ell)$ is an $n$-splitting (of $\Phi_n(\gamma\beta)$) if and only if $st_n(\beta) > ch_{n-1}(\gamma)$, i.e., $st^\Phi(\Phi_n(\beta)) \le ch^\Phi(\Phi_{n-1}(\gamma))$.

We can now obtain the first main result.

**Theorem 36** (Characterization of the alternating splitting). Let $n \ge 3$ and $\beta_0, \dots, \beta_\ell \in B_{n-1}^+$. The sequence $(\beta_0, \dots, \beta_\ell)$ is an $n$-splitting if and only if:

$$ (1') \text{ For all } i \in [1, \ell], L(\beta_i) = \{1\}. $$

$$ (2') \text{ For all } i \in [1, \ell-1], st_n(\Phi_n(\beta_{[i+1:]})) > ch_{n-1}(\beta_i), \text{ i.e., } st^\Phi(\beta_{[i+1:]}) \le ch^\Phi(\Phi_{n-1}(\beta_i)). $$
*Proof.* Suppose (1') and (2') are true. If $\ell \in \{-1, 0\}$, there is nothing to prove, so we now suppose that $\ell \ge 1$. We will show by induction on $i$ from $\ell$ to 0 that the $n$-splitting of $\beta_{[i:]}$ is $(\beta_i, \beta_{i+1}, \dots, \beta_\ell)$ and that $L(\beta_{[i:.]}) = \{1\}$ if $i \ge 1$.

First, $\beta_{[\ell:]} \equiv \beta_\ell \in B_{n-1}^+$, so its $n$-splitting is $(\beta_\ell)$, and by (1'), $L(\beta_\ell) = \{1\}$. Let $i \in [0, \ell - 1]$ be an integer, and suppose by induction that the $n$-splitting of $\beta_{[i+1:]}$ is $(\beta_{i+1}, \beta_{i+2}, \dots, \beta_\ell)$ and that $L(\beta_{[i+1:.]}) = \{1\}$. By (1'), $L(\Phi_n(\beta_{i+1})) = \{n-1\}$, so $h_{n-1}(\beta_{[i:]}) = \beta_i$. This implies that the $n$-splitting of $\beta_{[i:]}$ is $(\beta_i, \beta_{i+1}, \dots, \beta_\ell)$. On the other hand, if $i \ge 1$, by (2'), $\mathrm{st}_n(\Phi_n(\beta_{[i+1:]})) > \mathrm{ch}_{n-1}(\beta_i)$. By (1'), $L(\beta_i) = \{1\}$. Finally, by induction hypothesis, $L(\Phi_n(\beta_{[i+1:]})) = \{n-1\}$. So by Lemma 34, $L(\beta_{[i:]}) = L(\beta_i\Phi_n(\beta_{[i+1:]})) = \{1\}$. This ends the induction, proving that $(\beta_0, \dots, \beta_\ell)$ is an $n$-splitting.

Conversely, suppose $(\beta_0, \dots, \beta_\ell)$ is an $n$-splitting. Then for all $i \in [1, \ell]$, $b_{n-1}(\beta_{[i-1:]}) = \Phi_n(\beta_{[i:]})$, so $L(\beta_{[i:]}) = \{1\}$. Since $\beta_i$ is non-trivial, $\emptyset \subsetneq L(\beta_i) \subseteq L(\beta_{[i:]}) = \{1\}$, which implies that $L(\beta_i) = \{1\}$. Moreover, for all $i \in [1, \ell - 1]$, $L(\beta_i\Phi_n(\beta_{[i+1:]})) = \{1\}$, so by Lemma 34, $\mathrm{st}_n(\Phi_n(\beta_{[i+1:]}) > \mathrm{ch}_{n-1}(\beta_i)$. $\square$

Note that condition (2') implies in particular that for all $i \in [2, \ell - 1]$, the braid $\beta_i$ is not simple. Indeed, we would otherwise have $\beta_i \equiv \sigma_{1 \to n-2}$ and $n-1 \in L(\Phi_n(\beta_{[i+1:]}))$, so that $\sigma_{1 \to n-1} \le \beta_{[i:]}$, which implies $\mathrm{st}_n(\Phi_n(\beta_{[i:]})) = 1$, contradicting (2').

As a consequence, we get the following characterization of the alternating normal form.

**Theorem 37 (Characterization of the alternating normal form).** Let $w \in A_n^*$. The word $w$ is in $n$-alternating normal form ($\mathrm{Alt}_n$) if and only if: $n=2$, or $n \ge 3$ and it can be written

$$w = w_0 \Phi_n(w_1) w_2 \dots \Phi_n^\ell(w_\ell)$$

such that:

(0) The word $w_0$ is in $\mathrm{Alt}_{n-1}$.

(1) For all $i \in [1, \ell]$, the word $w_i \in A_{n-1}$ is non-empty, and the word $\Phi_{n-1}(w_i)$ is in $\mathrm{Alt}_{n-1}$ and begins with the letter $\sigma_{n-2}$.

(2) For all $i \in [1, \ell - 1]$, we have $\mathrm{st}_n(\Phi_n(w_{[i+1:]})) > \mathrm{ch}_{n-1}(w_i)$ or, equivalently, $\mathrm{st}^\Phi(w_{[i+1:]}) > \mathrm{ch}^\Phi(\Phi_{n-1}(w_i))$.

Moreover, in this case, $(w_0, w_1, \dots, w_\ell)$ is the word $n$-splitting of $w$.

*Proof.* If $n=2$, there is nothing to prove. Suppose $n \ge 3$, and that $w = w_0\Phi_n(w_1)w_2\dots\Phi_n^\ell(w_\ell)$ respects all the conditions of the theorem. For all $i \in [0, \ell]$, let $\beta_i$ be the braid represented by $w_i$. By (0), $w_0 \in \mathrm{Alt}_{n-1}$. By (1), for all $i \in [1, \ell]$, $\Phi_{n-1}(w_i) \in \mathrm{Alt}_{n-1}$ and starts with $\sigma_{n-2}$. This implies that the first block of the $n$-splitting of $\Phi_{n-1}(\beta_i)$ is empty, i.e. $h_{n-1}(\Phi_{n-1}(\beta_i)) \equiv \varepsilon$, which implies that $L(\Phi_{n-1}(\beta_i)) = \{n-2\}$ by Lemma 30. This proves that $L(\beta_i) = \{1\}$, so $\beta_i$ fulfills the conditions of (1'). Moreover, by Lemma 33, $w_i \in \mathrm{Alt}_{n-1}$. Finally, by (2), (2') is also verified. This implies by Theorem 36 that $(\beta_0, \dots, \beta_\ell)$ is the $n$-splitting of $\beta$. Moreover, we have shown that for all $i \in [0, \ell]$, $w_i$ is in $(n-1)$-alternating normal form, so $w$ is in $n$-alternating normal form.

Conversely, if a word is in alternating normal form, then by Theorem 36 and Lemma 33, the conditions are verified.

Finally, the equivalent (2) condition is a consequence of the result on words from Lemma 30 and Proposition 29. $\square$
Note that thanks to Proposition 29, the condition (2) is equivalent to: For all $i \in [1, \ell - 1]$, consider the minimal $k_i < n$ such that $\sigma_{n-1} \dots \sigma_{k_i}$ is a prefix of $\Phi_n(w_{[i+1:]})$; then $w_i$ contains $\sigma_{n-2}\sigma_{k_i-1}$ as a sub-word.

### 3.2.1. Consequences

Using the characterizations, we deduce a few powerful tools relative to alternating splittings and alternating normal forms. Those tools are more general and stronger than what we need to construct the minimal automaton in Section 4, but are very useful to tackle harder problems on the alternating normal form, in particular its automaticity [11].

**Lemma 38 (Joining two splittings).** Let $k$ and $\ell$ be two integers such that $0 \le k \le \ell$. Suppose that $(\beta_0, \dots, \beta_k)$ and $(\varepsilon, \beta_k, \dots, \beta_\ell)$ both are $n$-splittings, and that $\beta_k$ is not simple. Then $(\beta_0, \dots, \beta_\ell)$ is an $n$-splitting.

*Proof.* We will show by induction on $i$ from $k$ to $1$ that the $n$-splitting of $\beta_{[i:]}$ is $(\varepsilon, \beta_i, \beta_{i+1}, \dots, \beta_\ell)$. This is true for $i = k$ by hypothesis.

Let $i \in [2, k]$. Suppose the $n$-splitting of $\beta_{[i:]}$ is $(\varepsilon, \beta_i, \beta_{i+1}, \dots, \beta_\ell)$. Then $L(\beta_{[i:]}) = L(\beta_{[i:k]}) = \{1\}$ and $h_{n-1}(\beta_{[i:]}) = h_{n-1}(\beta_{[i:k]}) = \beta_i$. If $i \in [2, k-1]$, then $\beta_i$ is not simple by Theorem 36, and if $i = k$, then $\beta_i$ is not simple by hypothesis. By Lemma 32 on both $\beta_{[i:k]}$ and $\beta_{[i:]}$, we have $\mathrm{st}^\Phi(\beta_{[i:k]}) = \mathrm{st}^\Phi(\beta_i) = \mathrm{st}^\Phi(\beta_{[i:]})$. By Theorem 36 on $(\beta_0, \dots, \beta_k)$, we have $L(\beta_{i-1}) = \{1\}$, and $\mathrm{st}^\Phi(\beta_{[i:k]}) \le \mathrm{ch}^\Phi(\Phi_{n-1}(\beta_{i-1}))$. This implies that $(\varepsilon, \beta_{i-1})$ is an $n$-splitting, and that $\mathrm{st}^\Phi(\beta_{[i:]}) \le \mathrm{ch}^\Phi(\Phi_{n-1}(\beta_{i-1}))$.

By Lemma 35, $(\varepsilon, \beta_{i-1}, \beta_i, \beta_{i+1}, \dots, \beta_\ell)$ is an $n$-splitting, which ends the induction. Finally, since $(\varepsilon, \beta_1, \beta_2, \dots, \beta_\ell)$ is an $n$-splitting, then by Remark 16, $(\beta_0, \beta_1, \beta_2, \dots, \beta_\ell)$ is too. $\square$

**Lemma 39 (Substitution of braids).** Let $\beta, \gamma, \zeta \in B_n^+$ be braids such that $\alpha_n(\gamma) = \alpha_n(\zeta)$. Let $(\beta_0, \dots, \beta_\ell)$, $(\gamma'_0, \dots, \gamma'_k)$ and $(\zeta'_0, \dots, \zeta'_m)$ the $n$-splittings of $\beta, \gamma' = \Phi_n^\ell(\gamma)$ and $\zeta' = \Phi_n^\ell(\zeta)$, where $\ell = \ell_n(\beta)$.

If the $n$-splitting of $\beta\gamma$ is $(\beta_0, \dots, \beta_\ell\gamma'_0, \gamma'_1, \dots, \gamma'_k)$, then the $n$-splitting of $\beta\zeta$ is $(\beta_0, \dots, \beta_\ell\zeta'_0, \zeta'_1, \dots, \zeta'_m)$, and $\alpha_{n-1}(\gamma'_0) = \alpha_{n-1}(\zeta'_0)$.

*Proof.* First, by Remark 13, $\alpha_{n-1}(\gamma'_0) = \alpha_{n-1}(h_{n-1}(\gamma')) = h_{n-1}(\alpha_n(\gamma'))$. The same reasoning leads to $\alpha_{n-1}(\zeta'_0) = h_{n-1}(\alpha_n(\zeta'))$. Since $\alpha_n(\gamma) = \alpha_n(\zeta)$, by Remark 11, we get $\alpha_n(\gamma') = \alpha_n(\zeta')$, so that $\alpha_{n-1}(\gamma'_0) = \alpha_{n-1}(\zeta'_0)$.

If $\ell \in \{-1, 0\}$, there is nothing else to prove, so we now suppose that $\ell \ge 1$. By Proposition 8, we have $\alpha_{n-1}(\beta_\ell\gamma'_0) = \alpha_{n-1}(\beta_\ell\zeta'_0)$, so that $\mathrm{st}^\Phi(\beta_\ell\gamma'_0) = \mathrm{st}^\Phi(\beta_\ell\zeta'_0)$. By Theorem 36, since $(\beta_0, \dots, \beta_\ell\gamma'_0)$ is an $n$-splitting, $(\beta_0, \dots, \beta_\ell\zeta'_0)$ is also an $n$-splitting. By Remark 16, $(\beta_\ell\zeta'_0, \zeta'_1, \dots, \zeta'_m)$ is an $n$-splitting, and since $L(\beta_\ell\zeta'_0) = L(\beta_\ell\gamma'_0) = \{1\}$, this implies that $(\varepsilon, \beta_\ell\zeta'_0, \zeta'_1, \dots, \zeta'_m)$ is also an $n$-splitting. Finally, by Lemma 38, $(\beta_0, \dots, \beta_\ell\zeta'_0, \zeta'_1, \dots, \zeta'_m)$ is an $n$-splitting. $\square$

**Lemma 40 (Substitution of words).** Let $\beta, \gamma, \zeta \in B_n^+$, with $\alpha_n(\gamma) = \alpha_n(\zeta)$. If $\mathrm{Alt}_n(\beta)$ is a prefix of $\mathrm{Alt}_n(\beta\gamma)$ then $\mathrm{Alt}_n(\beta)$ is a prefix of $\mathrm{Alt}_n(\beta\zeta)$.

Moreover, if $L(\Phi_n^{\ell_n(\beta)}(\zeta)) = \{n-1\}$ or if $\zeta$ only has only one representative, then $\mathrm{Alt}_n(\beta\zeta) = \mathrm{Alt}_n(\beta)\mathrm{Alt}_n(\zeta)$.

*Proof.* If $\beta$ is trivial, the result is immediate, so we now suppose that $\beta$ is not trivial. If $n=2$, there is also nothing to prove. We now suppose that $n \ge 3$, and we suppose by induction that the result is true for $n-1$. Let $(\beta_0, \dots, \beta_\ell)$ the $n$-splitting of $\beta$ and $(\gamma'_0, \dots, \gamma'_k)$ the $n$-splitting of $\gamma' = \Phi_n^\ell(\gamma)$.
Since $Alt_n(\beta)$ is a prefix of $Alt_n(\beta\gamma)$ and $h_{n-1}(\Phi_n^\ell(\beta\ell\gamma)) = \Phi_n^\ell(\beta\ell)h_{n-1}(\Phi_n^\ell(\gamma)) = \Phi_n^\ell(\beta\ell\gamma'_0)$, the $n$-splitting of $\beta\gamma$ is $(\beta_0, \dots, \beta_\ell\gamma'_0, \gamma'_1, \dots, \gamma'_k)$.

By Lemma 39, the $n$-splitting of $\beta\zeta$ is $(\beta_0, \dots, \beta_\ell\zeta'_0, \zeta'_1, \dots, \zeta'_m)$, with $(\zeta'_0, \dots, \zeta'_m)$ the $n$-splitting of $\zeta' = \Phi_n^\ell(\zeta)$, and $\alpha_{n-1}(\gamma'_0) \equiv \alpha_{n-1}(\zeta'_0)$. Since $Alt_n(\beta)$ is a prefix of $Alt_n(\beta\gamma)$, $Alt_n(\beta\ell)$ is also a prefix of $Alt_n(\beta\ell\gamma'_0)$ by looking at the block $\beta_\ell\gamma'_0$ in the $n$-splitting of $\beta\zeta$. By induction hypothesis, $Alt_n(\beta\ell)$ is a prefix of $Alt_n(\beta\ell\zeta'_0)$. So $Alt_n(\beta)$ is a prefix of $Alt_n(\beta\zeta)$ by concatenation, since the $n$-splitting of $\beta\zeta$ is $(\beta_0, \dots, \beta_\ell\zeta'_0, \zeta'_1, \dots, \zeta'_m)$.

If $L(\Phi_n^\ell(\zeta)) = \{n-1\}$, then Lemma 30 proves that the braid $\zeta'_0$ is trivial. From the $n$-splitting $(\beta_0, \dots, \beta_\ell\zeta'_0, \zeta'_1, \dots, \zeta'_m)$ of $\beta\zeta$, we get $Alt_n(\beta\zeta) = Alt_n(\beta)Alt_n^{\Phi_n^\ell}(\zeta)$. Moreover, since $\zeta'_0$ is empty, by Lemma 33, $Alt_n^{\Phi_n^\ell}(\zeta) = Alt_n(\zeta)$, which proves that $Alt_n(\beta\zeta) = Alt_n(\beta)Alt_n(\zeta)$.

Finally, since $Alt_n(\beta)$ is a prefix of $Alt_n(\beta\zeta)$, there exists $w$ a representative of $\zeta$ such that $Alt_n(\beta\zeta) = Alt_n(\beta)w$. If $\zeta$ has only one representative, then $w = Alt_n(\zeta)$, so $Alt_n(\beta\zeta) = Alt_n(\beta)Alt_n(\zeta)$.

☐

# 4. Minimal automaton

We now construct the minimal automaton $\mathcal{A}_n$ recognizing the language $Alt_n$ for all $n \ge 2$. In order to do so, we first construct the minimal automaton $\mathcal{A}_n^1$ recognizing the language $Alt_n^1$, and construct $\mathcal{A}_n$ inductively thanks to the relations $Alt_n = Alt_{n-1}\Phi_n(Alt_n^1)$.

Since all the languages we study are closed by prefix, all the states of our automata will be accepting. In this paper, $\mathcal{A}_n$ is defined by the tuple $(V_n, \mathbb{A}_n, \mu_n, \iota_n)$, where $V_n$ denotes the set of states, all of which are accepting; $\mathbb{A}_n$ is the alphabet; $\mu_n: V_n \times \mathbb{A}_n \to V_n$ denotes the transition function; and $\iota_n \in V_n$ denotes the unique initial state of the automaton. Similarly, $\mathcal{A}_n^1$ is defined by the tuple $(V_n^1, \mathbb{A}_n, \mu_n^1, \iota_n^1)$. In order to construct $\mathcal{A}_n^1$, we will first construct an automaton $\tilde{\mathcal{A}}_n^1 = (\tilde{V}_n^1, \mathbb{A}_n, \tilde{\mu}_n^1, \tilde{\iota}_n^1)$ that also recognizes $Alt_n^1$, but is not minimal.

The language $Alt_2 = Alt_2^1$ consists of all words on the alphabet $\mathbb{A}_2 = \{\sigma_1\}$. When $n \ge 3$, we inductively build the automata $\mathcal{A}_n$ and $\mathcal{A}_n^1$ from the automata $\mathcal{A}_{n-1}$ and $\mathcal{A}_{n-1}^1$. Of course, we may use Theorem 37 directly to compute $\mathcal{A}_3^1$: the language $Alt_3^1$ consists of words of the form $(\sigma_1\sigma_1^*\sigma_2^*\sigma_2\sigma_1)^*$ and their prefixes, from which we deduce the minimal automaton $\mathcal{A}_3^1$ given in Fig. 6.

<figure><img src="image_7.png" /><figcaption>Figure 6: Automaton $\mathcal{A}_3^1$</figcaption></figure>

## 4.1. Some properties of $Alt_n$ and $Alt_n^1$

In order to prove the correctness of the automata, we first need some specific results on $Alt_n$ and $Alt_n^1$.
**Lemma 41.** Let $n \ge 2$. Let $w$ be a word belonging to $\text{Alt}_n$, and let $\sigma_k$ be its rightmost letter, or $\sigma_k = \sigma_1$ if $w$ is empty. Then for all $j \in [1, n-1]$, the word $w\sigma_{k \to j}$ also belongs to $\text{Alt}_n$. Furthermore, if $w$ belongs to $\text{Alt}_n^1$, so does $w\sigma_{k \to j}$.

*Proof.* If $w$ is empty, the first part is obvious. Suppose $w$ is non-empty, and let $w' \in A_n^*$ be the word such that $w = w'\sigma_k$. The language $\text{Alt}_n$ is stable by prefix, so $w'$ is in $\text{Alt}_n$. Let $v = \sigma_k\sigma_{k \to j}$, so that $w'v = w\sigma_{k \to j}$. Since $\alpha_n(v) = \sigma_k = \alpha_n(\sigma_k)$, we can apply Lemma 40, and since $v$ has only one representative, this implies that $w'v \in \text{Alt}_n$. Moreover, by Proposition 8, we have $\alpha_n(w'v) = \alpha_n(w)$, which proves that $L(w'v) = L(w)$. In particular, if $w$ belongs to $\text{Alt}_n^1$, then $L(w'v) = L(w) = \{1\}$, so $w\sigma_{k \to j}$ is also in $\text{Alt}_n^1$. $\square$

**Lemma 42.** Let $n \ge 3$ be an integer and $w$ be a non-empty word in $\text{Alt}_n^1$. Let $(w_0, w_1, \dots, w_\ell)$ be the word n-splitting of $w$, so that $w = w_0\Phi_n(w_1)\dots\Phi_n(w_\ell)$, and suppose that $w_\ell$ is not simple.

Let $\sigma_x$ be the rightmost letter of $w_\ell$, and $\sigma_y$ be the letter of maximal index in $w_\ell$. Then the words $w\Phi_n^\ell(\sigma_x)$ and $w\Phi_n^\ell(\sigma_{y+1})$ belong to $\text{Alt}_n^1$.

*Proof.* The letter $\Phi_n^\ell(\sigma_x)$ is the rightmost letter of $w$, so by Lemma 41, the word $w\Phi_n^\ell(\sigma_x)$ belongs to $\text{Alt}_n^1$.

By hypothesis, $w_\ell \in A_{y+1}^*$, so the $(y+2)$-splitting of $w_\ell\sigma_{y+1}$ is $(w_\ell, \sigma_1)$. This prove that the word $w_\ell\sigma_{y+1}$ is in $(y+2)$-alternating normal form. By hypothesis, the word $w_\ell$ is not simple, and $L(w_\ell) = \{1\}$, so by Lemma 32, $\alpha_n(w_\ell\sigma_{y+1}) = \alpha_n(h_{y+1}(w_\ell\sigma_{y+1})) = \alpha_n(w_\ell)$. This implies that $L(w_\ell\sigma_{y+1}) = L(w_\ell) = \{1\}$. In particular $L(\Phi_n^{\ell-1}(w_\ell\sigma_{y+1})) = \{n-1\}$, so we can apply Lemma 40 with to the braid $\beta = w_0\Phi_n(w_1)\dots\Phi_n^{\ell-1}(w_{\ell-1})$, the braid $\gamma = \Phi_n^\ell(w_\ell)$ and the braid $\zeta = \Phi_n^\ell(w_\ell\sigma_{y+1})$, which proves that $w\Phi_n^\ell(\sigma_{y+1}) \in \text{Alt}_n$.

Moreover, by Proposition 8 and Remark 11, we get:

$$ 
\begin{align*}
\alpha_n(w\Phi_n^\ell(\sigma_{y+1})) &\equiv \alpha_n(w_0\Phi_n(w_1)\dots\Phi_n^{\ell-1}(w_{\ell-1})\alpha_n(\Phi_n^\ell(w_\ell\sigma_{y+1}))) \\
&\equiv \alpha_n(w_0\Phi_n(w_1)\dots\Phi_n^{\ell-1}(w_{\ell-1})\alpha_n(\Phi_n^\ell(w_\ell))) \\
&\equiv \alpha_n(w)
\end{align*}
$$

This proves that $L(w\Phi_n^\ell(\sigma_{y+1})) = L(w) = \{1\}$, so that $w\Phi_n^\ell(\sigma_{y+1}) \in \text{Alt}_n^1$. $\square$

**Lemma 43.** Let $w$ be a word belonging to $\text{Alt}_n^1$ and let $(w_0, w_1, \dots, w_\ell)$ be its word n-splitting, so that $w = w_0\Phi_n(w_1)\dots\Phi_n^\ell(w_\ell)$, with $w_0, \dots, w_\ell \in \text{Alt}_{n-1}^1$. Then:

* If $\ell \le 0$, then $\text{ch}_n(w) = n$.

* If $\ell = 1$ and $w_1$ is simple, then there exists an integer $j \in [2, n-1]$ such that $\Phi_n(w_1) = \sigma_{n-1 \to j}$ and $\text{ch}_n(w) = j$.

* If $\ell = 1$ and $w_1$ is not simple, then $\text{ch}_n(w) = a+1$, where $a \in [1, n-2]$ is the least integer such that $w\sigma_a \in \text{Alt}_n^1$.

* If $\ell \ge 2$, then $\text{ch}_n(w) = 1$.

*Proof.* If $\ell \le 0$, then $w \in A_{n-1}^*$, so the word $w$ contains no $\sigma_{n-1}$, which proves that $\text{ch}_n(w) = n$.

If $\ell \ge 2$, then $w_2$ is non-empty, and its leftmost letter is $\sigma_1$. Since $L(\Phi_n(w_1)w_2) = \{n-1\}$, Lemma 28 implies that $\Phi_n(w_1)w_2$ contains a $\sigma_{n-1 \to 1}$-chain, so $\text{ch}_n(w) = 1$.

If $\ell = 1$ and $w_1$ is simple, then by Lemma 30, there exists an integer $j \in [2, n-1]$ such that $\Phi_n(w_1) = \sigma_{n-1 \to j}$, which proves that $\text{ch}_n(w) = j$.
Suppose that $\ell = 1$ and that $w_1$ is not simple. Let $y \in [1, n-2]$ be the index of the maximal letter in $w_1$. Let $b \in [1, n-2]$ be an integer such that $w\sigma_b \in \text{Alt}_n^1$. Since $L(\Phi_n(w_1)\sigma_b) = \{n-1\}$, Lemma 28 implies that $\Phi_n(w_1)\sigma_b$ contains a $\sigma_{n-1 \to b}$-chain, so $\Phi_n(w_1)$ contains a letter $\sigma_{b+1}$. In particular, $\Phi_n(b+1) \le y$, i.e., $b \ge \Phi_n(y+1)$. On the other hand, by Lemma 42, we have $w\Phi_n(\sigma_{y+1}) \in \text{Alt}_n^1$. This proves that the least integer $a$ such that $w\sigma_a \in \text{Alt}_n^1$ is $a = \Phi_n(y+1)$.

Since $w_1$ contains the letter $y$, Lemma 28 implies that the word $w_1$ contains a $\sigma_{1 \to y}$-chain. Since $y$ is maximal, the word $\Phi_n(w_1)$ contains no $\sigma_{y+1}$, so $w_1$ contains no $\sigma_{1 \to y+1}$-chain. This implies that $w$ contains a $\sigma_{1 \to a+1}$-chain but no $\sigma_{1 \to a}$-chain, so that $\text{ch}_n(w) = a+1$. $\square$

One important consequence of Lemma 43 is that for all $w \in \text{Alt}_n^1$ with at most two block (i.e., contains no $\sigma_{n-1 \to 1}$-chain), $\text{ch}_n(w)$ only depends on whether $w_1$ is of the form $\sigma_{n-1 \to j}$ and on the least letter $\sigma$ that can be added to $w$ so that $w\sigma$ is still in $\text{Alt}_n^1$.

We will use this property to define $\text{ch}_n$ on the states of the automaton $\mathcal{A}_{n-1}^1$ in the next section.

## 4.2. Construction of a first automaton recognizing $\text{Alt}_n^1$

Given an integer $n \ge 4$, let $\mathcal{A}_{n-1}^1 = (V_{n-1}^1, A_{n-1}^1, \mu_{n-1}^1, i_{n-1}^1)$ be the minimal automaton recognizing $\text{Alt}_{n-1}^1$. The automata $\tilde{\mathcal{A}}_n^1$ will be defined inductively using $\mathcal{A}_{n-1}^1$. It will need to be able to compute of the value of $\text{ch}_{n-1}$ when reading a block. Most of this information is actually already contained in the states of $\mathcal{A}_{n-1}^1$.

**Definition 44.** Given a state $s \in V_{n-1}^1$, we define $\text{ch}_{n-1}(s)$ as follows.

* If there exists a word $w \in \text{Alt}_{n-1}^1$ with $\ell_{n-1}(w) \le 1$ such that $\mu_{n-1}^1(i_{n-1}^1, w) = s$, then we define $\text{ch}_{n-1}(s) = \text{ch}_{n-1}(w)$.

* Otherwise, we define $\text{ch}_{n-1}(s) = 1$.

Note that this definition a priori depends on the choice of $w$. We can see that it does not depend on $w$ for states in $\mathcal{A}_2^1$ and $\mathcal{A}_3^1$, and we suppose by induction that this is also true for states belonging to $\mathcal{A}_{n-1}^1$. We will prove inductively that this definition is valid after constructing $\mathcal{A}_{n-1}^1$ at the end of Section 4.3. For now, we can suppose by induction that $\text{ch}_{n-1}(s)$ is the common value $\text{ch}_{n-1}(w)$ of all words $w$ in $\text{Alt}_{n-1}^1$ that arrive in $s$, and such that $\ell_{n-1}(w) \le 1$, i.e., such that $w$ does not contain the sub-word $\sigma_{(n-2) \to 1}$.

In order to check that a word is in alternating normal form, there are two bits of information $\tilde{\mathcal{A}}_n^1$ will have to keep track of when reading a block: its parity (is it a normal or a flipped block?), and whether we have seen the longest possible decreasing chain $\sigma_{(n-2) \to 1}$. The automaton $\tilde{\mathcal{A}}_n^1$ will also need to look the start of blocks in order to compute $\text{st}_n$ and compare it to $\text{ch}_{n-1}$.

We now define $\tilde{\mathcal{A}}_n^1$, and show that it recognizes the language $\text{Alt}_n^1$.

**Definition 45.** Let $n \ge 4$. We define the automaton $\tilde{\mathcal{A}}_n = (\tilde{V}_n^1, A_n, \tilde{\mu}_n^1, \tilde{i}_n^1)$ as follows.

* The state set of $\tilde{\mathcal{A}}_n^1$ is given by $\tilde{V}_n^1 = ((V_{n-1}^1 \times \{\top, \bot\}) \cup \tilde{P}_n^1) \times \{\text{Id}_n, \Phi_n\}$, where $\tilde{P}_n^1 = \{p_i^j: 2 \le j \le i \le n-1\}$, such that:

- The first boolean in $\{\top, \bot\}$ will indicate whether we have found the sub-word $\sigma_{(n-2) \to 1}$ in the current block of the n-splitting.
- The value in {$\mathsf{Id}_n, \Phi_n$} is another boolean, which keeps track of the parity of the block. States with the boolean $\mathsf{Id}_n$ are called $\mathsf{Id}_n$-states, and the others are called $\Phi_n$-states.

- States in the set $\tilde{P}_n^1$ keep track of the value of $\mathsf{st}_n$ when at the start of a block, and restrict letters using the value $\mathsf{ch}_{n-1}$ from the previous block. More precisely, being in the state $p_i^j$ means that the start of the current block $\Phi_n(v)$ is currently $\sigma_{(n-1)\to i}$, and that $\mathsf{st}_n(\Phi_n(v))$ must stay greater or equal to $j$ (because the value of $\mathsf{ch}_{n-1}$ of the previous block was $j-1$).

* The initial state of $\tilde{\mathcal{A}}_n^1$ is given by $\tilde{\mathcal{I}}_n^1 = (\mathcal{I}_{n-1}^1, \perp, \mathsf{Id}_n)$.

* The transition function $\tilde{\mu}_n^1$ is given by:

a. $\tilde{\mu}_n^1((s, \mathsf{f}, \mathsf{Id}_n), \sigma_i) = (\mu_{n-1}^1(s, \sigma_i), \mathsf{f}, \mathsf{Id}_n)$ when $i \neq n-1$ and $(\mathsf{ch}_{n-1}(s), i) \neq (2, 1)$;

b. $\tilde{\mu}_n^1((s, \mathsf{f}, \mathsf{Id}_n), \sigma_1) = (\mu_{n-1}^1(s, \sigma_1), \top, \mathsf{Id}_n)$ when $\mathsf{ch}_{n-1}(s) = 2$;

c. $\tilde{\mu}_n^1((p_i^j, \mathsf{Id}_n), \sigma_{n+1-i}) = (p_{i-1}^j, \mathsf{Id}_n)$ when $p_{i-1}^j \in \tilde{P}_n^1$;

d. $\tilde{\mu}_n^1((p_i^j, \mathsf{Id}_n), \sigma_{n-i}) = (\mu_{n-1}^1(\mathcal{I}_{n-1}^1, \sigma_{1\to(n-i)}\sigma_{n-i}), \perp, \mathsf{Id}_n)$;

e. $\tilde{\mu}_n^1((s, \perp, \mathsf{Id}_n), \sigma_{n-1}) = (p_{n-1}^j, \Phi_n)$ when $3 \le j \le n-1$ and $\mathsf{ch}_{n-1}(s) = j-1$;

f. $\tilde{\mu}_n^1((s, \top, \mathsf{Id}_n), \sigma_{n-1}) = (p_{n-1}^2, \Phi_n)$;

g. $\tilde{\mu}_n^1((s, \mathsf{f}, \Phi_n), \sigma_i) = (s', \mathsf{f}', \Phi_n^{k+1})$ when $\tilde{\mu}_n^1((s, \mathsf{f}, \mathsf{Id}_n), \sigma_{n-i}) = (s', \mathsf{f}', \Phi_n^k)$;

h. $\tilde{\mu}_n^1((s, \mathsf{f}, \Phi_n^k), \sigma_i)$ is not defined in every other case.

**Lemma 46.** The states and the transitions of the automaton $\tilde{\mathcal{A}}_n^1$ have the intended semantic and $\mathcal{A}_n^1$ recognizes $\mathsf{Alt}_n^1$.

*Proof.* We prove that in every case, the information contained in the current state is enough to check all the conditions of the alternating normal form characterization.

- In case a, we only need to check that the current block of the splitting is in alternating normal form: no boolean needs to change, and we use the previous automaton to check the normality of the current block.

- In case b, we now know that we have seen $\sigma_{(n-2)\to 1}$, so we store this information by changing the corresponding boolean, and we use the previous automaton to check the normality of the current block.

- In case c, we are extending the chain at the start of the block in a case where are allowed to.

- In case d, we stop extending the chain at the start of the block, so we leave $\tilde{P}_n^1$ and are back into "normal" territory. Thanks to Theorem 37, we can forget mostly how we got here, and just remember the start of the block we are in as well as fix the new value for the two booleans. The cases c and d cover the only two possible letters that can be read from $p_i^j$ by Lemma 30.

- In cases e and f, we go out of a block by reading $\sigma_{n-1}$, and just need to know $\mathsf{ch}_{n-1}$ of the previous block to restrict the value of $\mathsf{st}_n$ of the new block. In case f, we know we have seen $\sigma_{(n-2)\to 1}$ thanks to the boolean, and in case e we use $\mathsf{ch}_{n-1}(s)$ to know the value of $\mathsf{ch}_{n-1}$ of the previous block.
- In case g, we treat all cases where the block is flipped by referring to the other cases, by symmetry.

- In case h, we observe that we treated every case where reading a letter constructs a valid normal form. □

### 4.3. Construction of the minimal automaton recognizing $Alt_n^1$

When $n \ge 4$, the automaton $\tilde{\mathcal{A}}_n^1$ is not minimal. A first reason is that some states have the same residuals, and should thus be merged; we recall that the residual of a state $s \in \tilde{V}_n^1$ is the language $Alt_n^1(s)$ of words $w \in A_n^*$ for which $\tilde{\mu}_n^1(s, w)$ exists and is accepting. A second reason is that, when $n \ge 5$, some states of $\tilde{\mathcal{A}}_n^1$ are not even accessible. Thus, we shall transform $\tilde{\mathcal{A}}_n^1$ into the minimal automaton $\mathcal{A}_n^1$ of $Alt_n^1$, see Fig. 7.

**Definition 47.** Given an integer $n \ge 4$, let $\tilde{\mathcal{A}}_n^1 = (\tilde{V}_n^1, A_n, \tilde{\mu}_n^1, \tilde{\iota}_n^1)$ be the automaton built in Section 4.2. The automaton $\mathcal{A}_n^1 = (V_n^1, A_n, \mu_n^1, \iota_n^1)$ is defined from $\tilde{\mathcal{A}}_n^1$ by:

* Merging the states $(\iota_{n-1}^1, \perp, \Phi_n^k)$ and $(p_{n-1}^{n-1}, \Phi_n^k)$ for each $\Phi_n^k \in \{\mathrm{Id}_n, \Phi_n\}$. This amounts to deleting the state $(p_{n-1}^{n-1}, \Phi_n^k)$ and redirecting toward $(\iota_{n-1}^1, \perp, \Phi_n^k)$ the transitions of $\tilde{\mathcal{A}}_n^1$ that were targeted toward $(p_{n-1}^{n-1}, \Phi_n^k)$. We define $P_n^1 = \tilde{P}_n^1 \setminus \{p_{n-1}^{n-1}\}$.

* Deleting states of the form $((p_i^j, \mathrm{Id}_{n-1}), \perp, \Phi_n^k)$, where $p_i^j \in P_{n-1}^1$ and $\Phi_n^k \in \{\mathrm{Id}_n, \Phi_n\}$.

Hence the state set of $\mathcal{A}_n^1$ is $V_n^1 = ((\overline{V_{n-1}^1} \times \{\perp\}) \cup (V_{n-1}^1 \times \{\top\}) \cup P_n^1) \times \{\mathrm{Id}_n, \Phi_n\}$, where $\overline{V_{n-1}^1} = V_{n-1}^1 \setminus (P_{n-1}^1 \times \{\mathrm{Id}_{n-1}\})$.

We now consider $(p_{n-1}^{n-1}, \Phi_n^k)$ as an alias for $(\iota_{n-1}^1, \perp, \Phi_n^k)$.

**Lemma 48.** The automaton $\mathcal{A}_n^1$ recognizes $Alt_n^1$.

*Proof.* The reason why we merge the states $\tilde{\iota}_n^1 = (\iota_{n-1}^1, \perp, \mathrm{Id}_n)$ and $(p_{n-1}^{n-1}, \mathrm{Id}_n)$ is that both states have only one outgoing transition, labeled by $\sigma_1$, and whose target state is $\tilde{\mu}_n^1(\tilde{\iota}_n^1, \sigma_1)$, proving that those states have the same residual. Similarly, we merge the states $(\iota_{n-1}^1, \perp, \Phi_n)$ and $(p_{n-1}^{n-1}, \Phi_n)$.

We also delete states of the form $((p_i^j, \mathrm{Id}_{n-1}), \perp, \Phi_n^k)$ because they are not accessible. Indeed, by construction of $\tilde{\mu}_{n-1}^1$, every path in $\tilde{\mathcal{A}}_{n-1}^1$ (or in $\mathcal{A}_{n-1}^1$) ending in a state $(p_i^j, \mathrm{Id}_{n-1})$ must have previously visited a state of the form $(t, \Phi_{n-1})$. Thus, every word $w$ for which $\mu_{n-1}^1(\iota_{n-1}^1, w) = (p_i^j, \mathrm{Id}_{n-1})$ already contains an $(n-2, 1)$-chain, thereby proving that $\tilde{\mu}_n^1(\iota_n^1, w) = ((p_i^j, \mathrm{Id}_{n-1}), \top, \mathrm{Id}_n)$. It follows that $((p_i^j, \mathrm{Id}_{n-1}), \perp, \mathrm{Id}_n)$ is inaccessible, and we prove similarly that $((p_i^j, \mathrm{Id}_{n-1}), \perp, \Phi_n)$ is also inaccessible.

We conclude that $\mathcal{A}_n^1$ and $\tilde{\mathcal{A}}_n^1$ recognize the same language, which is $Alt_n^1$. □

To prove that $\mathcal{A}_n^1$ is minimal, it remains to show that all its states are accessible and have distinct residuals. We will proceed by induction. The automata $\mathcal{A}_2^1$ and $\mathcal{A}_3^1$ are minimal. We suppose that $\mathcal{A}_{n-1}^1$ is minimal, with $n \ge 4$.

**Lemma 49.** All the state of the automaton $\mathcal{A}_n^1$ are accessible. Let $s$ be a state in $\overline{V}_n^1$, so that $s \in V_n^1$ and $s$ is distinct from the states $(p_i^j, \mathrm{Id}_n)$ with $p_i^j \in P_n^1$. Then there exists a word $w \in Alt_n^1$ with $\mu_n^1(\iota_n^1, w) = s$ such that $\ell_n(w) \le 1$ (i.e., $w$ does not contain any $(n-1, 1)$-chain). Moreover, if $s$ is of the form $(s, f, \mathrm{Id}_n)$, there exists a word $w \in Alt_{n-1}^1$ such that $\mu_n^1(\iota_n^1, w) = s$.
<figure><img src="image_8.png" /><figcaption>Figure 7: Automaton $\mathcal{A}_4^1$, which contains four copies of $\mathcal{A}_3^1$ (circled in gray, two of which miss an edge) and a few dangling states $p_i^j$. Overlined states are $\Phi_n$-states, and the other states are $\mathrm{Id}_n$-states. Erasing dashed edges gives us an automaton that recognizes the language $\mathrm{Alt}_4^1 \cap (\mathrm{Alt}_3^1\Phi_4(\mathrm{Alt}_3^1))$, in which $p_2^2$ and $p_3^2$ are no longer accessible, and whose states have been split into four classes, colored in brown, blue, green and red: a state $s$ lies in the blue (resp., green, red) class when $\mathrm{ch}_4(w) = 2$ (resp., 3, 4) for all the words $w \in \mathrm{Alt}_3^1\Phi_4(\mathrm{Alt}_3^1)$ such that $\mu_4^1(i_4^1, w) = s$. Once a dashed edge has been taken, we just have $\mathrm{ch}_4(w) = 1$. Similarly, we have $\mathrm{ch}_3(w) = 1$ (resp., 2, 3) for all the words $w \in \mathrm{Alt}_3^1$ such that $\mu_4^1(i_4^1, w) = s$ when $s \in \{s_1^\top, s_2^\top, s_3^\top, s_4^\top\}$ (resp., $\{s_3^\perp, s_4^\perp\}$, $\{s_1^\perp, s_2^\perp\}$). The arrows labeled $\sigma_1$ going to $s_1^\top$ are actually arrows that were directed toward $p_3^2$ before merging the two states, and the same is true for $\bar{s}_1^\top$.</figcaption></figure>

**Proof.** For $n \le 3$, the result holds. Let $n \ge 4$, and suppose that the lemma is true for $n-1$. Let $s \in V_{n-1}^1$ be a state. By induction, there exists a word $w \in \mathrm{Alt}_{n-1}^1$ that does not contain a $(n-2, 1)$-chain such that $\mu_{n-1}^1(i_{n-1}^1, w) = s$. We can observe that $\mu_{n-1}^1(i_{n-1}^1, v) = i_{n-1}^1$, where $v = \sigma_{1 \to (n-2)}\sigma_{(n-2) \to 1}$. It follows that $\mu_n^1(i_n^1, v) = (i_{n-1}^1, \top, \mathrm{Id}_n)$. Moreover, for each state $p_i^j \in P_n^1$, the word $w_i^j = \sigma_{1 \to (n-2)}\sigma_{(n-2) \to (j-1)}\sigma_{(n-1) \to i}$ obeys the relation $\mu_n^1(i_n^1, w_i^j) = (p_i^j, \Phi_n)$. The identification of the states $(i_n^1, \bot, \Phi_n)$ and $p_{n-1}^{n-1}$ also makes this construction valid when $p_i^j = p_{n-1}^{n-1}$, so that $\mu_n^1(i_n^1, w_{n-1}^{n-1}) = \mu_n^1(i_n^1, \sigma_{1 \to n-2}\sigma_{n-2} \sigma_{n-1}) = (p_{n-1}^{n-1}, \Phi_n) = (i_{n-1}^1, \bot, \Phi_n)$.

We complete the proof by observing that:

* $(s, \bot, \mathrm{Id}_n) = \mu_n^1(i_n^1, w)$, with $\ell_n(w) = 0$;

* $(s, \top, \mathrm{Id}_n) = \mu_n^1(i_n^1, vw)$, with $\ell_n(vw) = 0$;
• $(p_i^j, \Phi_n) = \mu_n^1(i_n^1, w_i^j)$, with $\ell_n(w_i^j) = 1$;

• $(s, \perp, \Phi_n) = \mu_n^1((i_{n-1}^1, \perp, \Phi_n), \Phi_n(w)) = \mu_n^1(i_n^1, w_{n-1}^{n-1}\Phi_n(w))$, with $\ell_n(w_{n-1}^{n-1}\Phi_n(w)) = 1$;

• $(s, \top, \Phi_n) = \mu_n^1((i_{n-1}^1, \top, \Phi_n), \Phi_n(vw)) = \mu_n^1(i_n^1, w_{n-1}^{n-1}\Phi_n(vw))$, with $\ell_n(w_{n-1}^{n-1}\Phi_n(vw)) = 1$;

• $(p_i^j, \mathrm{Id}_n) = \mu_n^1((i_{n-1}^1, \perp, \Phi_n), \Phi_n(w_i^j)) = \mu_n^1(i_n^1, w_{n-1}^{n-1}\Phi_n(w_i^j))$.

□

Note that the automaton $\mathcal{A}_n^1$ is actually strongly connected, but this is not necessary to prove its minimality.

**Lemma 50.** The states of $\mathcal{A}_n^1$ have pairwise distinct residuals.

*Proof.* Let $s$ and $s'$ be distinct states of $\mathcal{A}_n^1$, and let $w$ and $w'$ be non-empty words in $\mathrm{Alt}_n^1$ such that $\mu_n^1(i_n^1, w) = s$ and $\mu_n^1(i_n^1, w') = s'$. Let $w^{(0)}\Phi_n(w^{(1)})\cdots\Phi_n^k(w^{(k)})$ and $w'^{(0)}\Phi_n(w'^{(1)})\cdots\Phi_n^l(w'^{(\ell)})$ be their factorizations given by Theorem 37; we assume that $w$ and $w'$ are chosen so that $k$ and $\ell$ are minimal.

We first prove that the states of the form $(t, f, \mathrm{Id}_n)$ or $(p_i^j, \mathrm{Id}_n)$ have pairwise distinct residuals. We call such states "$\mathrm{Id}_n$-states", as opposed to "$\Phi_n$-states":

• Suppose $s$ is of the form $(p_i^j, \mathrm{Id}_n)$, with $i \in [2, n-1]$. Then the only letter in $\mathrm{Alt}_n^1(s)$ is $\sigma_{n-i}$. If $s'$ is of the form $(p_j^s, \mathrm{Id}_n)$ with $j \neq i$, then the unique letter it can read is different. If $s'$ is of the form $(p_j^{j'}, \mathrm{Id}_n)$ with $j \neq j'$, then $\mathrm{Alt}_n^1(s')$ contains two letters, which are $\sigma_{n-i}$ and $\sigma_{n+1-i}$. Finally, if $s'$ is of the form $(t', f', \mathrm{Id}_n)$, then $\ell = 0$ by Lemma 49, so we can apply Lemma 42 to prove that $\mathrm{Alt}_n^1(s')$ contains at least two letters. Thus, each state $(p_i^i, \mathrm{Id}_n)$ has a residual distinct from all other $\mathrm{Id}_n$-states.

• Suppose $s$ is of the form $(p_j^i, \mathrm{Id}_n)$ with $j \neq i$. The state $s$ is the only state such that $\mu_n^1(s, \sigma_{(n+1-j)\to(n-i)}) = (p_i^i, \mathrm{Id}_n)$. Thus, the state $\mu_n^1(s', \sigma_{(n+1-j)\to(n-i)})$ either fails to exist or does not coincide with $(p_i^i, \mathrm{Id}_n)$: in both cases, $s$ and $s'$ have distinct residuals.

• Suppose both $s$ and $s'$ are of the form $(t, f, \mathrm{Id}_n)$ and $(t', f', \mathrm{Id}_n)$. If $f \neq f'$, the chain $\sigma_{(n-1)\to 2}$ belongs to exactly one of the residuals $\mathrm{Alt}_n^1(s)$ and $\mathrm{Alt}_n^1(s')$: the residual whose boolean is $\top$. Otherwise, $t \neq t'$, and the induction hypothesis proves that $\mathrm{Alt}_n^1(s) \cap \mathrm{Alt}_{n-1}^1 = \mathrm{Alt}_{n-1}^1(t) \neq \mathrm{Alt}_{n-1}^1(t') = \mathrm{Alt}_n^1(s') \cap \mathrm{Alt}_{n-1}^1$.

Similarly, all $\Phi_n$-states have distinct residuals.

Finally, assume that $s$ is an $\mathrm{Id}_n$-state and that $s'$ is a $\Phi_n$-state. Let $\sigma_u$ be the last letter of $w$, with $u \in [1, n-2]$, and let $z = \mathrm{ch}_{n-1}(s)$. We have $\mu_n^1(s, \sigma_{u \to n-1}) = (p_{n-1}^{z+1}, \Phi_n)$. Suppose $u = 1$. Then $\mu_n^1(s', \sigma_u)$ either does not exist, or is a state of the form $(p_{n-1}^j, \mathrm{Id}_n)$, so that $\mu_n^1(s', \sigma_{u \to n-1})$ does not exist. Suppose $u \ge 2$. Then $s'' = \mu_n^1(s', \sigma_{u \to n-2})$ is a $\Phi_n$-state, so that $\mu_n^1(s', \sigma_{u \to n-1}) = \mu_n^1(s'', \sigma_{n-1})$ differs from $(p_{n-1}^{z+1}, \Phi_n)$, since the transitions going to that state all come from $\mathrm{Id}_n$-states. $\square$

As a consequence of Lemmas 49 and 50, we obtain the following result.

**Proposition 51.** The automaton $\mathcal{A}_n^1$ is the minimal automaton of the language $\mathrm{Alt}_n^1$.

Finally, we need to prove that $\mathrm{ch}_n$ is well defined on $\mathcal{A}_n^1$ to properly end the induction.
**Proposition 52.** The function $ch_n$ is well defined on the states of $\mathcal{A}_n^1$.

*Proof.* Let $t \in V_n^1$. Suppose $t = (p_i^j, \mathbf{1}_d)$. Let $w \in \mathrm{Alt}_n^1$ such that $\mu_n^1(\iota_{n-1}^1, w) = t$. Then by construction, $\ell_n(w) \ge 2$, as all paths to $t$ contain a decreasing $\sigma_{(n-1)\to 1}$-chain, so Lemma 43 proves that $ch_n(t) = 1$.

Otherwise, by Lemma 49, there exists $w \in \mathrm{Alt}_n^1$ with $\mu_n^1(\iota_{n-1}^1, w) = t$ such that $\ell_n(w) \le 1$. Then:

* If $t = (s, f, \mathbf{1}_d)$, then $\ell_n(w)$ is even by construction of $\mathcal{A}_n^1$, so $\ell_n(w) = 0$, so Lemma 43 proves that $ch_n(w) = n$.

* If $t = (p_i^j, \Phi_n)$, then the second block of the word $n$-splitting of $w$ is $w_1 = \sigma_{n-1\to i}$, so Lemma 43 proves that $ch_n(w) = i$.

* If $t = (s, f, \Phi_n)$, then $\ell_n(w)$ is odd, so $\ell_n(w) = 1$. Moreover, the second block of $w$ is not simple, since reading $w$ would end in a state of the form $(p_i^j, \Phi_n)$ in that case. By Lemma 43, we have $ch_n(w) = a+1$, with $a$ the least integer such that $w\sigma_a \in \mathrm{Alt}_n^1$. The integer $a$ is also the least integer such that $\tilde{\mu}_n^1(t, \sigma_a)$ is defined, which only depends on $t$.

In every case, the value of $ch_n(t)$ does not depend on the choice of $w$, so $ch_n$ is well defined on the states of $\mathcal{A}_n^1$. $\square$

### 4.4. Construction of the minimal automaton recognizing $\mathrm{Alt}_n$

We construct the automata $\mathcal{A}_n$ as follows (see Fig. 8).

**Definition 53.** First, $\mathcal{A}_2 = \mathcal{A}_2^1$ is the automaton with one unique state and one loop labeled by $\sigma_1$. Then, when $n \ge 3$, the state set and initial state of $\mathcal{A}_n$ are defined by $V_n = V_{n-1} \cup V_n^1$, $\iota_n = \iota_{n-1}$ and the transition function $\mu_n$ is defined as follows:

* $\mu_n(s, \sigma_u) = \mu_{n-1}(s, \sigma_u)$ when $s \in V_{n-1}$ and $u \le n-2$;

* $\mu_n(s, \sigma_{n-1}) = \mu_n^1(\iota_n^1, \sigma_1)$ when $s \in V_{n-1}$;

* $\mu_n(s, \sigma_u) = \mu_n^1(s, \Phi_n(\sigma_u))$ when $s \in V_n^1$.

**Theorem 54.** The automaton $\mathcal{A}_n$ is the minimal automaton recognizing the language $\mathrm{Alt}_n$.

*Proof.* The relation $\mathrm{Alt}_n = \mathrm{Alt}_{n-1} \Phi_n (\mathrm{Alt}_n^1)$ proves that this automaton recognizes $\mathrm{Alt}_n$.

We prove by induction on $n \ge 2$ that every state of $\mathcal{A}_n$ is accessible. This is true for $n=2$. Let $n \ge 3$, and suppose every state of $\mathcal{A}_{n-1}$ is accessible. Let $s \in V_n$. If $s \in V_{n-1}$, the state $s$ is accessible by induction. Suppose $s \in V_n^1$. The state $t = \mu_n^1(\iota_n^1, \sigma_1) = \mu_n(\iota_n^1, \sigma_{n-1})$ is accessible in $\mathcal{A}_n$ from $\iota_n$ via the one-letter word $\sigma_{n-1}$, so that $t = \mu_n(\iota_n, \sigma_{n-1})$. Moreover, $\mu_n^1(t, w) = \iota_n^1$, with $w = \sigma_{2\to n-1} \sigma_{n-1\to 1}$, so that $\mu_n(t, \Phi_n(w)) = \iota_n^1$. By Lemma 49, $s$ is accessible from $\iota_n^1$, so $s$ is accessible from $\iota_n$, which ends the induction.

Our last task consists in proving that any two states $s$ and $s'$ of $\mathcal{A}_n$ have pairwise distinct residuals, which we also prove by induction on $n$. When $s$ and $s'$ belong to $V_{n-1}$, this is the induction hypothesis, and when $s$ and $s'$ belong to $V_n^1$, this is the irreducibility of $\mathcal{A}_n^1$. Finally, when $s \in V_{n-1}$ and $s' \in V_n^1$, let $w$ be a word such that $\mu_n(\iota_n, w) = s$, and let $\sigma_u$ be its last letter, or $\sigma_u = \sigma_1$ in case $w$ is empty. Let $v = \sigma_{u\to 1}$. Lemma 41 proves that $wv$ belongs to $\mathrm{Alt}_{n-1}$,
<figure><img src="image_9.png" /><figcaption>Figure 8: The automaton $\mathcal{A}_4$. The state $s_0$ is the unique state of $\mathcal{A}_2$, and $s_0, s_1, s_2, s_3, s_4$ are the states of $\mathcal{A}_3$.</figcaption></figure>

so that $\mu_n(s, v\sigma_{n-1}) = \mu_n^1(\iota_n^1, \sigma_1)$; this is a state of $\mathcal{A}_n^1$ that differs from all states $(p_i^j, \mathbf{1}_d)$ by contrast, if it ever exists, the state $\mu_n(s', v) = \mu_n^1(s', \Phi_n(v))$ is a $\Phi_n$-state (since $\Phi_n(v)$ ends with the letter $\sigma_{n-1}$), so that $\mu_n(s', v\sigma_{n-1}) = \mu_n^1(\mu_n^1(s', \Phi_n(v)), \sigma_1)$ is a state $(p_{n-1}^i, \mathbf{1}_d)$ — which may be the state $(p_{n-1}^{n-1}, \mathbf{1}_d) = \iota_n^1$. This implies that $\mu_n(s, v\sigma_{n-1})$ and $\mu_n(s', v\sigma_{n-1})$ are distinct states of $V_n^1$, so their residual are different. $\square$

**Theorem 55.** For all $n \ge 2$, the automaton $\mathcal{A}_n$ has $s_n$ states and $t_n$ transitions, where

$$s_n = \frac{25 \times 2^{2n-3} - 9n^2 + 3n + 7}{27} \quad \text{and} \quad t_n = \frac{(225n - 290)2^{2n-5} - 9n^3 - 9n^2 + 93n - 77}{81}.$$

*Proof.* Let $s'_n$ and $t'_n$ denote the numbers of states and transitions of the automaton $\mathcal{A}_n^1$. First, we have $s'_2 = 1$, $s'_3 = 4$ and $t'_2 = 1$, $t'_3 = 6$. Then, when $n \ge 4$, we have $|P_n^1| = |P_{n-1}^1| + (n-2)$. It
follows that

$$s'_{n} = |V_{n}^{1}| = 2((|V_{n-1}^{1}| - |P_{n-1}^{1}|) + |V_{n-1}^{1}| + |P_{n}^{1}|) = 4s'_{n-1} + 2(n-2),$$

and an immediate induction proves that $s'_{n} = (25 \times 2^{2n-5} - 6n + 4)/9$ for all $n \ge 3$.

Furthermore, each state $(p_i^j, \Phi_n^k)$ has out-degree 2 when $i > j$, and out-degree 1 when $i = j$; the latter case occurs $n-3$ times, so in total, $2|P_n^1| - (n-3)$ transitions leave states of the form $(p_i^j, \mathrm{Id}_n)$. In addition, the $\mathrm{Id}_n$-states of $\mathcal{A}_n^1$ from which one can read a letter $\sigma_{n-1}$ are the states $(s, f, \mathrm{Id}_n)$ for which $f = \top$ or $s$ is a $\Phi_{n-1}$-state of $\mathcal{A}_{n-1}^1$; there are $s'_{n-1}$ states in the first family, and $s'_{n-1}/2$ states in the second family that are not in the first one. Consequently, in total, there are

$$(t'_{n-1} - (2|P_{n-1}^1| - (n-4))) + t'_{n-1} + (2|P_n^1| - (n-3)) + 3s'_{n-1}/2$$

transitions leaving $\mathrm{Id}_n$-states, so that $t'_n = 4t'_{n-1} + 3s'_{n-1} + 2(2n-5)$. Hence, another induction proves that $t'_n = ((25n-35)2^{2n-7} - 2n + 4)/3$ for all $n \ge 3$.

Finally, $s_2 = 1$ and $t_2 = 1$, whereas $s_n = s_{n-1} + s'_n$ and $t_n = t_{n-1} + s_{n-1} + t'_n$ for all $n \ge 3$. Thus, an easy induction proves once again that $s_n = (25 \times 2^{2n-3} - 9n^2 + 3n + 7)/27$ and $t_n = ((225n - 290)2^{2n-5} - 9n^3 - 9n^2 + 93n - 77)/81$ whenever $n \ge 2$. $\square$

### 4.5. Linear-timed algorithm recognizing alternating normal forms

Using the automaton $\mathcal{A}_n$ gives an algorithm checking whether a word $w \in \mathcal{A}_n$ is in alternating normal form in $O(|w|)$, but pre-computing $\mathcal{A}_n$ in time $\Omega(s_n + t_n) = \Omega(n2^n)$. On the other hand, directly using the characterization of Theorem 37 gives a faster algorithm to check a normal form. We can check whether a word $w \in \mathcal{A}_n^*$ is in $\mathrm{Alt}_n^1$ in time $O(n * |w|)$ by:

* Stopping if $n = 2$: $O(|w|)$

* Reading $w$ once to find the word $n$-splitting $(w_1, \dots, w_\ell)$: $O(|w|)$

* Computing $\mathrm{ch}_{n-1}$ and $\mathrm{st}^\Phi$ for each block, and comparing them to check the condition (2) of the characterization: $O(|w|)$

* Checking that each block $w_i$ is in $\mathrm{Alt}_{n-1}^1$ by induction: $O((n-1) * |w|)$

We can then check whether a word $w \in \mathcal{A}_n^*$ is in alternating normal form by:

* Reading $w$ once to compute the minimal $n$ such that $w \in \mathcal{A}_n^*$, and stopping if $n = 2$: $O(|w|)$

* Finding the end of the first block $w_0$ of the word $n$-splitting, so that $w = w_0w'$: $O(|w_0|)$

* Checking that $w'$ is in $\mathrm{Alt}_n^1$: $O(n * |w'|)$

* Checking that $w_0$ is in $\mathrm{Alt}$ by induction: $O((n-1) * |w_0|)$

This leads to an algorithm running in $O(n * |w|)$, where $n$ is the minimal integer such that $w \in \mathcal{A}_n^*$. In practice, it is possible to rewrite the order of operation to read each letter only once, checking everything recursively at each step. This actually amounts to simulating a path in $\mathcal{A}_n$ without constructing it explicitly, only remembering the current state in the form of a tuple $(p_u^v, \phi_i^\gamma, f_{i+1}, \phi_{i+1}^\gamma, \dots, f_k, \phi_k^\gamma)$ encompassing the value of all the useful booleans and the start of the current block. This also gives an algorithm in $O(n * |w|)$ recognizing words $w$ in $\mathrm{Alt}_n$.
# 5. Perspectives

**Generating random braid.** In [9], the authors used the minimal automaton recognizing the lexicographic normal form to construct an algorithm generating random braids in $B_n^+$ of a given length $k$ uniformly at random in time $O(n^4 \ln(n)k^{\alpha+2})$, where $\alpha = \log_2(3)$. We think it is possible to use the same strategy with $\mathcal{A}_n$ to find a new algorithm generating random braids.

**Automaticity.** The automaticity of a normal form is a much stronger property compared to regularity, and ensures in particular that the normal form is easy to compute. It was proven in [3] that, while the alternating normal form is regular, it is not automatic on the left side, and the author suggested that the normal form is not automatic on the right side. However, in future work [11], we will use our new characterization to prove the right-automaticity of the alternating normal form.

**Rotating normal form.** The dual braid monoid is another classic braid monoid with a larger set of generators, in which there is a generator for each strand transposition. In this monoid, we can define the rotating normal form, which is derived from the Garside automorphism associated to the dual braid monoid. This normal form has very similar properties to the alternating normal form, and has been studied by Jean Fromentin in [6], in which he found a similar characterization, and also constructed the automaton associated to the language. We think we can prove the minimality of the constructed automaton, but also the right-automaticity of this normal form.

**Other block decompositions.** The decomposition of a braid into blocks using fewer strands is natural, but the strands that are allowed in each block is arbitrary. The alternating normal form splits a braid using strands numbered 1 to $n$ into blocks using the intervals $[[1, n-1]]$ and $[[2, n]]$ alternatively, but we could study other decompositions. For example we could use the intervals $[[1, k + \ell]]$ and $[[k, n]]$ alternatively for any $k \in [[2, n-1]]$ and $\ell \in [[0, n-k-1]]$. These kinds of decompositions have been introduced in [3], and we think the same tools can be used to find similar properties for the splittings associated to these decompositions.

**Other Coxeter braid monoids.** The braid monoid can be seen as a finite Coxeter group of type $A$ (i.e. permutations) without the involution properties of generators. The same process can be used to deduce exotic braid monoids associated to other type of finite Coxeter groups, which all have similar properties to the braid monoid. We think it is possible to construct normal forms similar to the alternating normal form in those exotic braid monoids, and maybe prove similar characterizations.

# References

[1] Emil Artin. Theorie der Zöpfe. In *Abhandlungen aus dem mathematischen Seminar der Universität Hamburg*, volume 4, pages 47–72. Springer, 1925.

[2] Serge Burckel. The wellordering on positive braids. *Journal of Pure and Applied Algebra*, 120(1):1–17, 1997.

[3] Patrick Dehornoy. Alternating normal forms for braids and locally garside monoids. *Journal of pure and applied algebra*, 212(11):2413–2439, 2008.

[4] Patrick Dehornoy, Ivan Dynnikov, Dale Rolfsen, and Bert Wiest. *Ordering Braids*. Société Mathématique de France, 2007.
[5] David Epstein. *Word processing in groups*. CRC Press, 1992.

[6] Jean Fromentin. The rotating normal form of braids is regular. *Journal of Algebra*, 501:545-570, 2018.

[7] F.A. Garside. The theory of knots and associated problems. *PhD. Thesis*, Oxford University, 1965.

[8] F.A. Garside. The braid group and other groups. *The Quarterly Journal of Mathematics*, 20(1):235-254, 1969.

[9] Volker Gebhardt and Juan González-Meneses. Generating random braids. *Journal of Combinatorial Theory, Series A*, 120(1):111-128, 2013.

[10] Vincent Jugé and June Roupin. The alternating normal form of braids and its minimal automaton. *Leibniz International Proceedings in Informatics (LIPIcs)*, 302:23:1-23:15, 2024.

[11] June Roupin. Right-automaticity of the alternating normal form in the standard braid monoid. In preparation.