One of the fundamental objects of study in combinatorics on words is the pattern. A pattern is a word over an alphabet of variables and is meant to describe some kind of repetitive structure. For instance the pattern XX over the single variable X is meant to describe the repetition of the same word twice in succession. A word x over an alphabet \(\varSigma \) encounters a pattern p over an alphabet \(\varDelta \) if there is a non-erasing morphism \(h : \varDelta ^* \rightarrow \varSigma ^*\) such that h(p) is a factor of x. For example, the word waverers encounters the pattern XX via the map \(X \rightarrow \mathtt {er}\). If the word x does not encounter p then it avoids p.

The first systematic analysis of the avoidability of patterns was done by Bean, Ehrenfeucht, and McNulty [2], and, independently, by Zimin [14]. One of their major results was a characterization of which patterns are avoidable on a finite alphabet. The least k such that a pattern p is avoidable on a k-letter alphabet is called the index of p. Baker, McNulty, and Taylor [1] produced an example of a pattern with index 4 and left it as an open question whether or not there are patterns of higher index. Clark [4] produced an example of a pattern of index 5 and at present no pattern is known to have index higher than 5.

Cassaigne [3] introduced the related concept of a formula. A formula is a set of patterns \(\{p_1, \ldots , p_s\}\), usually written with “dots” as \(p_1\cdot p_2 \cdot \cdots \cdot p_s\). The \(p_i\) are referred to as fragments of the formula. The formula is avoided by a word x if there is no non-erasing morphism \(h : \varDelta ^* \rightarrow \varSigma *\) such that \(h(p_i)\) is a factor of x for every \(i = 1, \ldots , s\). Clark used this notion of formula to produce his example of a pattern of index 5.

Recently, there has been some interest in studying patterns with reversal, such as \(XXX^R\). A word x encounters \(XXX^R\) if there is a morphism \(h : \{X\}^* \rightarrow \varSigma ^*\) such that \(h(X)h(X)(h(X))^R\) is a factor of x, where \((h(x))^R\) denotes the reversal of the word h(x). Du, Mousavi, Rowland, Schaeffer, and Shallit [10] and Currie and Rampersad [8, 9] examined the patterns \(XXX^R\) and \(XX^RX\). Currie and Lafrance [5] determined the index of every binary pattern with reversal. For some recent algorithmic results, see [11,12,13].

Of course, one can generalize patterns with reversal to formulas with reversal in the same way one generalizes patterns to formulas. The work we will present in this talk is that of Currie, Mol, and Rampersad [6, 7] on formulas with reversal. The first results [6] are a construction of some simple formulas with reversal that have index 5. Clark’s example of a formula of index 5, which does not use reversal, is quite complicated; with reversals, our examples are quite simple. For each \(k\ge 1\), we define the formula

$$ \psi _i = XY_1Y_2 \cdots Y_kX \cdot Y_1^R \cdot Y_2^R \cdot \cdots \cdot Y_k^R. $$
FormalPara Theorem 1

The formula \(\psi _1\) has index 4.

FormalPara Theorem 2

The formula \(\psi _2\) has index 5.

FormalPara Theorem 3

For \(k \ge 1\), the formula \(\psi _k\) has index \({\ge }4\).

Our next result is an attempt to generalize the so-called Zimin characterization of unavoidable formulas. Let \(X_1, X_2, \ldots \) be variables. Define the Zimin words recursively by \(Z_0 = \epsilon \) and for \(n \ge 1\) we have \(Z_n = Z_{n-1}X_nZ_{n-1}\). Zimin showed that a formula (without reversal) on n variables is unavoidable if and only if it is encountered by \(Z_n\).

We generalize this to formulas with reversal as follows. Let \(X_1, X_2, \ldots \) and \(Y_1,Y_2,\ldots \) be variables. For any variable X define \(X^\sharp = \{X, X^R\}\). For \(m\ge 0\) and \(n \ge 0\) we define the Zimin formula with reversal \(Z_{m,n}\) by

$$ Z_{m,0} = X_1^\sharp \cdots X_m^\sharp $$

and

$$ Z_{m,n} = Z_{m,n-1}Y_nZ_{m,n-1}. $$

Given a formula with reversals \(\phi \), we say that a variable X is two-way in \(\phi \) if both X and \(X^R\) occur in \(\phi \). Otherwise, we say that X is one-way. Note that in \(Z_{m,n}\) the \(X_i\) are two-way and the \(Y_i\) are one-way. We have the following partial result [7].

FormalPara Theorem 4

Let \(\phi \) be a formula with reversals with \(m \ge 0\) two-way variables and \(n \le 2\) one-way variables. Then \(\phi \) is unavoidable if and only if it is encountered by \(Z_{m,n}\).

In this abstract we have been somewhat informal with our definitions. For full details and proofs, please see the papers [6, 7].