A Tropical Approach to the Compositional Piecewise Complexity of Words and Compressed Words

We follow [26]. For a word $u=a_1{a}_2\mathrm{\cdots }{a}_n$ of length $|u|=n$ and two positions $i,j$ such that $0\le i\le j\le n$, we write $u(i,j)$ for the factor $a_{i+1}{a}_{i+2}\mathrm{\cdots }{a}_j$. Note that $u(0,|u|)=u$, that $u(i_1,i_2)\cdot u(i_2,i_3)=u(i_1,i_3)$, and that $|u(i,j)|=j-i$. We write $u(i)$ as shorthand for $u(i-1,i)$, i.e., $a_i$, the $i$th letter of $u$. Finally, we use $u(i,)$ and $u(,j)$ as convenient notations for $u(i,n)$ and, respectively, $u(0,j)$: they are the $i$th prefix and the $j$th suffix of $u$, with the understanding that this numbering starts with a “$0$th” prefix, always equal to the empty word $ϵ$, and that suffixes get shorter and shorter when their index grow while the length of prefixes increases.

Fix a $m$-letter alphabet $\mathrm{\Sigma }=\{a_1,a_2,\mathrm{\dots },a_m\}$. A word $u\in {\mathrm{\Sigma }}^{\ast }$ is a subword of $v\in {\mathrm{\Sigma }}^{\ast }$, written $u\preccurlyeq v$, if there is a factorization $v=v_0{u}_1{v}_1{u}_2{v}_2\mathrm{\cdots }{u}_{\mathrm{\ell }}{v}_{\mathrm{\ell }}$ with factors $v_0,\mathrm{\dots },v_{\mathrm{\ell }},u_1,\mathrm{\dots },u_{\mathrm{\ell }}\in {\mathrm{\Sigma }}^{\ast }$ and such that $u=u_1\mathrm{\cdots }{u}_{\mathrm{\ell }}$ [24]. When furthermore $\mathrm{\ell }=1$ then $u$ is also a factor of $v$. For example, both $u_1=\mathrm{𝙰𝙰}$ and $u_2=\mathrm{𝙱𝙱}$ are subwords of $v=\mathrm{𝙰𝙱𝙱𝙰}$ but only $u_2$ is a factor of $v$. The longest subword of $u$ is $u$ itself, its shortest subword is the empty word, denoted $ϵ$. Subwords are the usual concept of subsequences in the special case of words, i.e., finite sequences of letters.

For given $m\in \mathbb{N}$, we write $v{\sim }_m{v}^{\prime }$ when $v$ and $v^{\prime }$ have the same subwords of length at most $m$ [27]. For example $\mathrm{𝙰𝙱𝙱𝙰}{\sim }_2\mathrm{𝙱𝙰𝙱𝙰}$ while $\mathrm{𝙰𝙱𝙱𝙰}{\sim ̸}_3\mathrm{𝙱𝙰𝙱𝙰}$ since, e.g., $\mathrm{𝙰𝙱𝙱}\preccurlyeq \mathrm{𝙰𝙱𝙱𝙰}$ and $\mathrm{𝙰𝙱𝙱}\preccurlyeq ̸\mathrm{𝙱𝙰𝙱𝙰}$. In situations where $u$ is subword of only one among two words $v$ and $v^{\prime }$, we say that $u$ is a (piecewise) distinguisher (also a separator) between $v$ and $v^{\prime }$.

Then $v{\sim }_k{v}^{\prime }$ means that $v$ and $v^{\prime }$ have no distinguisher of length $k$ or less, or that their shortest distinguisher (guaranteed to exist when $v\ne v^{\prime }$) has length at least $k+1$. Each ${\sim }_k$ is an equivalence relation over ${\mathrm{\Sigma }}^{\ast }$, with ${\sim }_0={\mathrm{\Sigma }}^{\ast }\times {\mathrm{\Sigma }}^{\ast }$ being the trivial “always true” relation, and $u{\sim }_{1}v$ holding if, and only if, $u$ and $v$ use the same subset of letters. Every ${\sim }_k$ has finite index [28, 14] and is a refinement of the previous ${\sim }_{k-1}$, i.e., $u{\sim }_{k}v⟹u{\sim }_{k-1}v$, with ${\bigcap }_{k\in \mathbb{N}}{\sim }_k=\text{Id}$. One speaks of “Simon’s congruence” in view of $u{\sim }_k{u}^{\prime }\wedge v{\sim }_k{v}^{\prime }⟹uv{\sim }_k{u}^{\prime }{v}^{\prime }$.

The piecewise complexity of a word $u$, denoted $h(u)$, is the smallest $k$ such that $u{\sim }_{k}v⟹u=v$ [15, 26]. In terms of distinguishers, $h(u)=k$ means that any $v\ne u$ can be separated from $u$ by a piecewise distinguisher of length $\le k$. We refer to [15, 26] and the references therein for more motivations and applications of piecewise complexity.

An $O(|u|\cdot |\mathrm{\Sigma }|)$ time algorithm computing $h(u)$ is given in [26]. It is based on a characterisation of $h(u)$ in terms of piecewise-distances. For a word $u\in {\mathrm{\Sigma }}^{\ast }$ and a letter $a\in \mathrm{\Sigma }$, we follow [27, 28] and define the right and left “side distances”:

The two notions are mirror of one another: $\mathrm{\ell }(a,u)=r(u^{𝖱},a)$, where $u^{𝖱}$ denotes the reverse, or the mirror image, of $u$.

One can reduce the computation of $h$ to the computation of $r$ and $\mathrm{\ell }$ in view of the following characterisation (see [26, Prop. 3.1]):

In order to compute $r(u,a)$, Schnoebelen and Vialard introduce the following characterisation:

Following [26], the $r$-table of $u$, denoted $R_u$, is the $m$-by-$(n+1)$ matrix with entry $r(u(,j),a_i)$ in column $0\le j\le n$ and row $1\le i\le m$, where we assume some fixed ordering $\{a_1,\mathrm{\dots },a_m\}$ of the letters in $\mathrm{\Sigma }$. There is a similar $\mathrm{\ell }$-table, denoted $L_u$, with entries $\mathrm{\ell }(a_i,u(j,))$. The key point is that, by Eq. (1), computing $h(u)$ amounts to finding the maximum value in the array $R_u+L_u$ obtained by summing the two matrices.

By tropical algebra we mean the semiring $⟨\mathbb{N}\cup \{+\mathrm{\infty }\};\min ,+⟩$, with $+\mathrm{\infty }$ as zero and $0$ as unit, also called the $(\min ,+)$-semiring. It is a semiring rather than a ring because there is no additive inverse and no subtraction. In the following we use $\ast$ as a less cumbersome notation for $+\mathrm{\infty }$,²²2It is common to use $ϵ$ as a light notation for the zero in tropical rings but we reserve $ϵ$ to denote the empty word. and ${\mathbb{N}}_{\ast }$ as shorthand for $\mathbb{N}\cup \{\ast \}$ (and also for the whole structure). We refer to [9, 22, 18] for more in-depth introductions and simply observe that, modulo a sign change, $(\min ,+)$-semirings are isomorphic to the more familiar $(\max ,+)$-semirings one typically encounters in operations research [13], combinatorics [3], economics, etc.

We use the standard linear ordering on ${\mathbb{N}}_{\ast }$, given by . Both semiring operations are monotonic w.r.t. $\le$: for any $x,x^{\prime },y,y^{\prime }\in {\mathbb{N}}_{\ast }$, $x\le x^{\prime }$ and $y\le y^{\prime }$ together imply $\min (x,y)\le \min (x^{\prime },y^{\prime })$ and $x+y\le x^{\prime }+y^{\prime }$. Finally, note that $\ast$, the zero of ${\mathbb{N}}_{\ast }$, is also its maximal element.

Tropical semirings lead to their own flavour of linear algebra. In ${\mathbb{N}}_{\ast }$, a linear combination of variables $𝒙=(x_1,\mathrm{\dots },x_k)$ has the form

where the ${\alpha }_j$’s are scalars from ${\mathbb{N}}_{\ast }$. Such an $f$ can be represented by a line vector $\left({\alpha }_1{\alpha }_2\mathrm{\cdots }{\alpha }_k\right)$, simply written $𝜶$, so that $f(𝒙)$ is the (tropical) dot product $𝜶\cdot 𝒙$.

Since ${\mathbb{N}}_{\ast }$ is only a commutative semiring and not a field, these linear combinations do not form a proper vector space, not even a module, but only a semimodule over ${\mathbb{N}}_{\ast }$. However, and for our limited purposes, the usual notions of vector and matrix sums and products work as expected so the reader should be on familiar ground. The next paragraphs introduce the notations we need and collect the main properties we shall rely on.

We will often use the vector $𝒆\stackrel{\text{def}}{=}\left(\mathrm{0\hspace{0.33em}0}\mathrm{\cdots }\mathrm{\hspace{0.33em}0}\right)$, made up of units only (not zeroes) and with dimension $m$ to be inferred from context. We write ${𝒆}_i$ for the vector $(\ast \mathrm{\cdots }\ast \mathrm{\hspace{0.33em}0}\ast \mathrm{\cdots }\ast )$ that has a single unit in position $i$, surrounded by zeroes. Thus ${𝒆}_i$ is the $i$th column of the tropical identity matrix $I_m$ and $𝒆$ is its diagonal. As expected, ${({𝒆}_i)}_{i=1,\mathrm{\dots },m}$ is a base for ${\mathbb{N}}_{\ast }^m$, the free $m$-dimensional ${\mathbb{N}}_{\ast }$-semimodule.

In ${\mathbb{N}}_{\ast }^m$, a linear application is a mapping $F:{\mathbb{N}}_{\ast }^m\to {\mathbb{N}}_{\ast }^n$ of the form $F(x_1,\mathrm{\dots },x_m)=(f_1(x_1,\mathrm{\dots },x_m),\mathrm{\dots },f_n(x_1,\mathrm{\dots },x_m))$ where each $f_i$ is a (tropical) linear combination. As in classical linear algebra, $F$ can be represented by a $n$-by-$m$ matrix $M_F$, where row $i$ contains the scalars defining $f_i$, so that $F(𝒙)=M_F\cdot 𝒙$.

The ordering on ${\mathbb{N}}_{\ast }$ leads to a partial ordering on tropical vectors and matrices. For two vectors $𝜶,𝜷\in {\mathbb{N}}_{\ast }^m$, we write $𝜶\le 𝜷$ when ${\alpha }_i\le {\beta }_i$ for all $i=1,\mathrm{\dots },m$. Similarly, given two tropical matrices $A$ and $B$ of same heights and widths, we write $A\le B$ when each value $A_{i,j}$ in $A$ is dominated by the corresponding $B_{i,j}$ in $B$. Then $A\le B$ and $𝜶\le 𝜷$ together imply $A\cdot 𝜶\le B\cdot 𝜷$, i.e., “linear applications are monotonic”. Note that the tropical sums of vectors $𝜶,𝜷$ or matrices $M,M^{\prime }$, are computed by applying $\min$ component-wise and coincide with infimums, or meets, in the lattices $({\mathbb{N}}_{\ast }^m,\le )$ and $({\mathbb{N}}_{\ast }^{m\times n},\le )$: for this reason we denote them with $𝜶\sqcap 𝜷$ and $M\sqcap M^{\prime }$ instead of “$\min (𝜶,𝜷)$” or “$\min (M,M^{\prime })$” which suggests picking the smaller vector or matrix. We still use $\min$ for scalars since, in that case, the two interpretations coincide.

The starting point of this paper is the realisation that Lemma 2.1 actually describes the $j+1$th column of $R_u$ as a tropically linear image of its $j$th column. For this we associate a tropical matrix with each word over $\mathrm{\Sigma }$.

We may now return to the table $R_u$. Let us write $C_{u,j}$ for its column number $j$, recalling that the first column has index 0, and use $C_u$ as shorthand for $C_{u,|u|}$, i.e., the last column. When $u$ is understood, we usually just write $C_j$ for $C_{u,j}$. Finally, we shall mostly display and use the $C_j$’s as line vectors without bothering to write $C_j^{⊺}$ everywhere.

By definition, $C_j$ is $\left(r(u(,j),a_1)r(u(,j),a_2)\mathrm{\cdots }r(u(,j),a_m)\right)$. In particular $C_0=𝒆$.

The key to computing $r$- and $\mathrm{\ell }$-tables compositionally is to consider $R_{vu}$ and $L_{uv}$ as functions of $R_v$ and $L_v$.

In other words, ${𝜹}_{i,j}$ is the $i$th column of the extension matrix for the $j$th prefix of $u$. Note that $F_u$ is a table of vectors where $R_u$ was a table of values.

Now $F_u$ can be used to compute $R_u$ via $r(u(,j),a_i)=𝒆\cdot {𝜹}_{i,j}$ (Lemma 3.3), but more generally it provides the $r(w,a_i)$’s for any word $w$ that has some $u(,j)$ as a suffix. Indeed, assume $w=vu(,j)$:

In order to compute the $r(u(,i),a)+\mathrm{\ell }(a,u(i,))$ required by Equation 1, we now want to combine the two tables, as done in Example 2.2. Recall, however, that these $+$ are actually products in ${\mathbb{N}}_{\ast }$, and that the vectors ${𝜹}_{i,j}$ and ${𝜸}_{i,j}$ actually encode the linear maps given by $C\mapsto {𝜹}_{i,j}\cdot C$ and $D\mapsto {𝜸}_{i,j}\cdot D$ in Eqs. (6) and (8).

Given two tropically linear functions $f(𝒙)=𝜶\cdot 𝒙$ and $g(𝒚)=𝜷\cdot 𝒚$ from ${\mathbb{N}}_{\ast }^m$ to ${\mathbb{N}}_{\ast }$, the tropical product $f\odot g$, defined via $(f\odot g)(𝒙,𝒚)\stackrel{\text{def}}{=}f(𝒙)+g(𝒚)$, satisfies

It is (tropically) bilinear since $(f\odot g)(𝒙\sqcap {𝒙}^{\mathbf{\prime }},𝒚)=(f\odot g)(𝒙,𝒚)\sqcap (f\odot g)({𝒙}^{\mathbf{\prime }},𝒚)$ and, for a scalar $\alpha \in {\mathbb{N}}_{\ast }$, $(f\odot g)(𝒙,\alpha \cdot 𝒚)=\alpha +(f\odot g)(𝒙,𝒚)$.³³3Here $\alpha \cdot 𝒚$ is a tropical scaling of a vector, which amounts to increase every value in $𝒚$ by $\alpha$. Such mappings are the natural objects of multilinear algebra, see e.g. [19]. Moving to the tensor space ${\mathbb{N}}_{\ast }^m\otimes {\mathbb{N}}_{\ast }^m$, we can see $f\odot g$, a mapping from ${\mathbb{N}}_{\ast }^{2m}$ to ${\mathbb{N}}_{\ast }$, as a tropically linear mapping from ${\mathbb{N}}_{\ast }^{m^2}$ to ${\mathbb{N}}_{\ast }$, denoted $f\otimes g$, and that associates $\left(𝜶\otimes 𝜷\right)\cdot \left(𝒙\otimes 𝒚\right)$ with the tensor $𝒙\otimes 𝒚$.

Adapted to tropical algebra, the elementary tensor $𝜿=𝜶\otimes 𝜷$ obtained as outer product of two vectors of size $m$ and $n$, respectively, is the $m$-by-$n$ matrix given by ${\kappa }_{i,j}={\alpha }_i+{\beta }_j$. It is natural to see $𝜿$ as a matrix but sometimes, as in the expression $\left(𝜶\otimes 𝜷\right)\cdot \left(𝒙\otimes 𝒚\right)$, it is more natural to see the tensors as vectors of size $nm$.⁴⁴4The size-$nm$ vector is obtained by reading the matrix column by colum, see Example 3.9 below.

In the above definition, ${𝜹}_{i,j}$ and ${𝜸}_{i,j}$ are as in the definition of $F_u$ and $G_u$. Finally, every ${𝜼}_{i,j}$ entry in $H_u$ is a $m$-by-$m$ tropical tensor, or, equivalently, a tropical vector of size $m^2$.

Let us now consider a word $w$ that contains $u$ as a factor, i.e., assume that $w$ is some $v_{1}u{v}_2$. For a position $j$ in $u$ and a letter $a_i$ in $\mathrm{\Sigma }$, one obtains

by combining Eqs. (6) and (8) with the definition of ${𝜼}_{i,j}$.

If now one wants to find the maximum value among all $r(v_{1}u(,j),a_i)+\mathrm{\ell }(a_i,u(j,)v_2)$, it is not necessary to consider all possibilities for $j=0,\mathrm{\dots },|u|$ and $i=1,\mathrm{\dots },m$. Since $C_{v_1}\otimes D_{v_2}$ does not change with $i$ and $j$, and since the dot-product in Eq. (9) is monotonic with respect to the component-wise order, we do not need the full $H_u$ table to compute $h(u)$ but only a set of its maximal elements. This leads to:

Note that $E_u$ is never empty and usually contains several elements since the ordering on ${\mathbb{N}}_{\ast }^{m^2}$ is only a partial ordering when $m>1$.

The following lemma, needed in Section 4, can be seen as another example.

Since the objects in signatures can accommodate concatenation, it is possible to compute them compositionally. The main result of this section is stated as

The proof is developed in several steps.

The above statement uses tensor products of linear maps. Recall that when $f,g:{\mathbb{N}}_{\ast }^n\to {\mathbb{N}}_{\ast }^m$ are two linear maps, their tensor product $f\otimes g:{\mathbb{N}}_{\ast }^{n^2}\to {\mathbb{N}}_{\ast }^{m^2}$ can be defined via $(f\otimes g)({⨆}_{𝒊}{𝜶}_{𝒊}\otimes {𝜷}_{𝒊})={⨆}_{𝒊}f({𝜶}_{𝒊})\otimes g({𝜷}_{𝒊})$. When $f$ and $g$ are given by two $n$-by-$m$ matrices $A$ and $B$, one can obtain a $n^2$-by-$m^2$ matrix, denoted $A\otimes B$, for $f\otimes g$ by taking the products of the rows of $A$ and the rows of $B$ (as expected since ${({𝒆}_i\otimes {𝒆}_j)}_{1\le i,j\le n}$ is a base of ${\mathbb{N}}_{\ast }^n\otimes {\mathbb{N}}_{\ast }^n$).