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

Philippe Schnoebelen, J. Veron, Isa Vialard

► To cite this version:

Philippe Schnoebelen, J. Veron, Isa Vialard. A Tropical Approach to the Compositional Piecewise Complexity of Words and Compressed Words. 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2025), Jul 2025, Aarhus, Denmark. 10.4230/LIPIcs.ICALP.2025.171 . hal-05402775

HAL Id: hal-05402775

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

Submitted on 7 Dec 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.

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

Distributed under a Creative Commons Attribution 4.0 International License
# A Tropical Approach to the Compositional Piecewise Complexity of Words and Compressed Words

Philippe Schnoebelen

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

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

Université Paris-Saclay, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, Gif-sur-Yvette, France

J. Veron

Université Paris-Saclay, CNRS, ENS Paris-Saclay, Laboratoire Méthodes Formelles, Gif-sur-Yvette, France

Isa Vialard

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

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

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

Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany

## Abstract

We express the piecewise complexity of words using tools and concepts from tropical algebra. This allows us to define a notion of piecewise signature of a word that has size $log(n)m^{O(1)}$ where $m$ is the alphabet size and $n$ is the length of the word. The piecewise signature of a concatenation can be computed from the signatures of its components, allowing a polynomial-time algorithm for computing the piecewise complexity of SLP-compressed words.

**2012 ACM Subject Classification** Theory of computation → Formal languages and automata theory

**Keywords and phrases** Tropical semiring, Subwords and subsequences, piecewise complexity, SLP-compressed words

**Digital Object Identifier** 10.4230/LIPIcs.ICALP.2025.171

**Category** Track B: Automata, Logic, Semantics, and Theory of Programming

**Acknowledgements** Work started while the third author was at Univ. Paris-Saclay.

# 1 Introduction

## Subwords and piecewise complexity

For two words $u, v$, we say that $u$ is a *subword* of $v$, written $u \preceq v$, if $u$ can be obtained by removing some letters (possibly all, possibly none) from $v$ at arbitrary positions. For example, **ABBA** $\preceq$ **ABRACADABRA**. This notion corresponds to *subsequences* in other areas, and is more general than the usual concept of *factors* of a word.<fnref n="1" />

Compared to factors, subwords are not so easy to reason about, and correspondingly they have been much less studied. However, they certainly are a fundamental notion, appearing naturally in many areas of formal languages, algorithmics, data sciences, logic, computational linguistics, genomics, etc.

In language theory, semigroup theory, and logic, an important concept is *piecewise-testability*, introduced in 1972 by Imre Simon [27]. This corresponds exactly to the first level in Straubing-Thérien hierarchy of first-order definable languages [6] and has been extended in many directions (infinite words [4], trees [2], any well quasi-ordered set [11]).

In this paper, we are interested in subword-based descriptive complexity of words. In particular, the *piecewise-complexity* of words and languages has been used in [15] for bounding the complexity of decidable fragments of the logic of subwords (see also [12]). In essence,

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

© Philippe Schnoebelen, J. Veron, and Isa Vialard;
licensed under Creative Commons License CC-BY 4.0

52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025).

Editors: Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis
Article No. 171; pp. 171:1–171:19

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

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

LIPICS

Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<footnote n="1">¹ Some authors use the terminology “subword” for factors, and then use “scattered subword” for subwords.</footnote>
171:2 A Tropical Approach to the Piecewise Complexity of Words

the piecewise-complexity of a word (or any piecewise-testable object) is the minimum size of
the pieces required to specify it. Regarding this measure, a recent algorithmic contribution
is [26], providing efficient algorithms for computing the piecewise-complexity of individual
words. The algorithms and the reasoning behind them are quite involved and it is not trivial
to extend them for, e.g., periodic words [23].

It turns out that many of the computations performed in [26] have a simple description
in the framework of tropical algebra, i.e., the (min, +)-semiring. Indeed, some fundamental
operations of [26] are just linear transformations in a tropical sense. This realisation is the
starting point for this paper.

Our contribution

In a first part, we rephrase the results of [26] in the language and notation of tropical algebra.
This setting makes it easier to develop a compositional way of computing piecewise-complexity:
we associate with any word $u$ a (piecewise) signature $\sigma(u)$ that has size logarithmic in $|u|$
(and polynomial in the size of the alphabet), and that contains enough information to allow
extracting, among other things, the piecewise complexity of $u$. Furthermore, signatures can
be computed compositionally, i.e., $\sigma(uv)$ is obtained in polynomial-time from $\sigma(u)$ and $\sigma(v)$.

In a second part we use this apparatus to compute the piecewise complexity of compressed
words in time polynomial in the size of their compressed description, solving a problem raised
in [25]. Reasoning on (e.g., searching) and handling (e.g., editing) compressed data structures
is an important field of algorithmics and compressed words are one of the most fundamental
and most fruitful instantiations of the paradigm, see [17]. While our algorithm is a simple
derivation of the results from the first part, its complexity analysis is quite involved and is
the main technical difficulty in this paper. We expect that the techniques behind piecewise
signatures can be useful for other subword-related problems on compressed words.

We hope to convince our readers that our contribution is made more elegant and technically
simpler through the use of tropical linear and multilinear algebra. This allows one to recruit
familiar notions of vectors, matrices, their products, their monotonicity, thus lightening the
brain load required for following through our reasoning. Tropical algebra was introduced in
the area of formal languages and automata by Imre Simon himself (in [29], see also [21]) in
connection with the star-height problem, opening the way to the algebraic and algorithmic
theory of weighted automata, now a very active area [7, 18]. In this respect it is surprising
that Simon did not use tropical algebra in his fundamental work on piecewise-testable
languages [27, 28] on which we heavily rely and whose bases we rephrase tropically.

Related work

Related to piecewise-complexity of words is the piecewise-distance $\delta(u, v)$ of two words, which has been more studied and is the topic of several recent papers [1, 3, 8, 10]. Indeed the piecewise-complexity of $u$ can be defined as $1 + \max_{v \neq u} \delta(u, v)$ [26] but this characterisation does not provide useful algorithms. The range of related questions include reconstructing words from their subwords [16], solving word equations [20], or computing edit-distance [20, 5], etc., modulo Simon's congruence.

Outline of the paper

Section 2 recalls the basic concepts, notations, and results used in the paper. Section 3, the main conceptual contribution, shows how to use tropical algebra for computing piecewise complexity compositionally, introduces piecewise signatures with their associated algorithms.
Section 4 applies this to SLP-compressed words. Finally, Section 5 handles the complexity analysis and contains the main technical difficulties. For readability concerns, some proofs are omitted from the main text and can be found in the Appendix.

## 2 Basic notions

### 2.1 Subwords and the piecewise complexity of words

We follow [26]. For a word $u = a_1a_2\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}\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 “0th” prefix, always equal to the empty word $\epsilon$, and that suffixes get shorter and shorter when their index grow while the length of prefixes increases.

Fix a $m$-letter alphabet $\Sigma = \{a_1, a_2, \dots, a_m\}$. A word $u \in \Sigma^*$ is a subword of $v \in \Sigma^*$, written $u \prec v$, if there is a factorization $v = v_0u_1v_1u_2v_2\cdots u_\ell v_\ell$ with factors $v_0, \dots, v_\ell, u_1, \dots, u_\ell \in \Sigma^*$ and such that $u = u_1\cdots u_\ell$ [24]. When furthermore $\ell = 1$ then $u$ is also a factor of $v$. For example, both $u_1 = \text{AA}$ and $u_2 = \text{BB}$ are subwords of $v = \text{ABBA}$ 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 $\epsilon$. 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'$ when $v$ and $v'$ have the same subwords of length at most $m$ [27]. For example $\text{ABBA} \sim_2 \text{BABA}$ while $\text{ABBA} \prec_3 \text{BABA}$ since, e.g., $\text{ABB} \prec \text{ABBA}$ and $\text{ABB} \not\prec \text{BABA}$. In situations where $u$ is subword of only one among two words $v$ and $v'$, we say that $u$ is a (piecewise) distinguisher (also a separator) between $v$ and $v'$.

Then $v \sim_k v'$ means that $v$ and $v'$ have no distinguisher of length $k$ or less, or that their shortest distinguisher (guaranteed to exist when $v \ne v'$) has length at least $k + 1$. Each $\sim_k$ is an equivalence relation over $\Sigma^*$, with $\sim_0 = \Sigma^* \times \Sigma^*$ 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 \implies 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' \wedge v \sim_k v' \implies uv \sim_k u'v'$.

The piecewise complexity of a word $u$, denoted $h(u)$, is the smallest $k$ such that $u \sim_k v \implies 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.

### 2.2 Computing $h(u)$

An $O(|u| \cdot |\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 \Sigma^*$ and a letter $a \in \Sigma$, we follow [27, 28] and define the right and left “side distances”:

$$r(u, a) \stackrel{\text{def}}{=} \max\{k \mid u \sim_k u a\},$$

$$\ell(a, u) \stackrel{\text{def}}{=} \max\{k \mid a u \sim_k u\}.$$

The two notions are mirror of one another: $\ell(a, u) = r(u^R, a)$, where $u^R$ denotes the reverse, or the mirror image, of $u$.
171:4 A Tropical Approach to the Piecewise Complexity of Words

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

$$
h(u) = \max_{\substack{0 \le i \le |u| \\ a \in \Sigma}} r(u(i), a) + \ell(a, u(i)) + 1. \qquad (1)
$$

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

► **Lemma 2.1** ([26, Lem. 3.8]). For any word $u \in \Sigma^*$ and any letters $a, b \in \Sigma$, the following hold:

$$
r(\epsilon, a) = 0, \tag{2}
$$

$$
r(ub, a) = \begin{cases} r(u, a) + 1 & \text{if } a = b, \\ \min(r(u, b) + 1, r(u, a)) & \text{if } a \neq b. \end{cases} \tag{3}
$$

Following [26], the *-table of* $u$, denoted $R_u$, is the *-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, \dots, a_m\}$ of the letters in $\Sigma$. There is a similar *-table, denoted $L_u$, with entries $\ell(a_i, u(j, \cdot))$. 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.

**Example 2.2.** Here are $R_u$ and $L_u$ for $u = \text{CBBCAC}$, assuming $\Sigma = \{\text{A}, \text{B}, \text{C}\}$:

$$
\left( \begin{array}{ccccccc} 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 2 & 2 & 1 & 1 \\ 0 & 1 & 1 & 1 & 2 & 1 & 2 \end{array} \right) \xrightarrow{r(u, [4], \mathcal{C}) = 2} \left( \begin{array}{ccccccc} 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 2 & 2 & 1 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 2 & 1 & 1 & 0 \end{array} \right) \xrightarrow{\ell(\mathcal{C}, u[4, \cdot]) = 1} \left( \begin{array}{ccccccc} 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 2 & 2 & 1 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 2 & 1 & 1 & 0 \end{array} \right)
$$

With Eq. (1), one sees that $h(u) = 4$, obtained as $r(u, [4], \mathcal{C}) + \ell(\mathcal{C}, u[4, \cdot]) + 1 = 2 + 1 + 1 = 4$.
This maximum is not uniquely attained: $r(u, [3], \mathcal{C}) + \ell(\mathcal{C}, u[3, \cdot]) + 1 = 1 + 2 + 1 = 4$. Note
that $\text{CBBCAC} \sim_3 \text{CBBCAC} = u$, so that indeed $h(u)$ is necessarily larger than 3.

3 Tropical algebra and piecewise complexity

**3.1 The tropical semiring**

By tropical algebra we mean the semiring $\mathbb{N} \cup \{+\infty\}; \min, +\rangle$, with $+\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 $*$ as a less cumbersome notation for $+\infty,^2$ and $\mathbb{N}_*$ as shorthand for $\mathbb{N} \cup \{*\}$ (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}_*$, given by $0 < 1 < 2 < \dots < i < i+1 < \dots < *$.
Both semiring operations are monotonic w.r.t. $\le$: for any $x, x', y, y' \in \mathbb{N}_*$, $x \le x'$ and $y \le y'$
together imply $\min(x, y) \le \min(x', y')$ and $x + y \le x' + y'$. Finally, note that $*$, the zero of
$\mathbb{N}_*$, is also its maximal element.

<footnote n="2">² It is common to use $\epsilon$ as a light notation for the zero in tropical rings but we reserve $\epsilon$ to denote the empty word.</footnote>
171:6 A Tropical Approach to the Piecewise Complexity of Words

► **Example 3.2.** Assuming $\Sigma = \{A, B, C\}$, the above definition leads to

$$ M_A = \begin{pmatrix} 1 & 1 & 1 \\ * & 0 & * \\ * & * & 0 \end{pmatrix}, \quad M_B = \begin{pmatrix} 0 & * & * \\ 1 & 1 & 1 \\ * & * & 0 \end{pmatrix}, \quad M_C = \begin{pmatrix} 0 & * & * \\ * & 0 & * \\ 1 & 1 & 1 \end{pmatrix}, $$

for letters, and

$$ M_{CBBCAC} = \begin{pmatrix} 1 & 1 & 2 \\ 2 & 2 & 3 \\ 2 & 2 & 3 \end{pmatrix}, \quad N_{CBBCAC} = \begin{pmatrix} 1 & 3 & 3 \\ 1 & 2 & 2 \\ 2 & 3 & 3 \end{pmatrix}, $$

for a word $u = CBBCAC$. Note that $M_u$ and $N_u$ have no clear relation ($M_u = M_v$ does not entail $N_u = N_v$).

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^T$ everywhere.

By definition, $C_j$ is $(r(u(j), a_1) r(u(j), a_2) \cdots r(u(j), a_m))$. In particular $C_0 = e$.

► **Lemma 3.3.** For any word $u$ and any factor $u(j, j')$ of $u$,

$$ C_{j'} = C_j \cdot M_{u(j, j')}. $$

In particular, $C_u = e \cdot M_u$.

**Proof.** By induction on $j' - j$, the length of the factor of $u$. The base case $j' = j$ is clear since $M_{u(j,j)}$, i.e., $M_e$, is the identity matrix. If $j' = j + 1$ then $u(j, j')$ is the letter $u(j') = a_i$ for some $1 \le i \le m$. By definition we have that for all $1 \le k \le m$, the $k$th entry of column $j$ is $(C_j)_k = r(u(j), a_k)$ and likewise, the $k$th entry of column $j+1$ is $(C_{j+1})_k = r(u(j+1), a_k)$. Therefore

$$ \begin{align*} (C_{j+1})_k &\stackrel{(3)}{=} \begin{cases} r(u(j), a_i) + 1 = (C_j)_i + 1 & \text{if } i = k, \\ \min(r(u(j), a_i) + 1, r(u(j), a_k)) = \min((C_j)_i + 1, (C_j)_k) & \text{if } i \neq k. \end{cases} \\ &= C_j \cdot M_{a_i}. \end{align*} $$

Finally, if $j' > j + 1$, then for any $j''$ strictly between $j$ and $j'$ we can derive

$$ C_j \cdot M_{u(j,j')} = C_j \cdot M_{u(j,j'') \cdot u(j'',j')} \stackrel{\text{Df. 3.1}}{=} C_j \cdot M_{u(j,j'')} \cdot M_{u(j'',j')} \stackrel{\text{i.h.}}{=} C_{j''} \cdot M_{u(j'',j')} \stackrel{\text{i.h.}}{=} C_{j'}. $$

using the induction hypothesis.

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

Mirror results hold for $L_u$ once we introduce the required notations. So let us write $D_{u,j}$ for the $j$th column of $L_u$ (counting from left and starting with $j = 0$) with standard abbreviations $D_j$ for $D_{u,j}$ when $u$ is understood, and $D_u$ for $D_{u,0}$. Then for any factor $u(j, j')$ of $u$ we have $D_j = D_{j'} \cdot N_{u(j,j')}$, and in particular $D_u = e \cdot N_u$.

3.3 Compositional computation of $R_u$

The key to computing $r$- and $\ell$-tables compositionally is to consider $R_{vu}$ and $L_{uv}$ as functions of $R_v$ and $L_v$.
171:8 A Tropical Approach to the Piecewise Complexity of Words

It is (tropically) bilinear since $(f \odot g)(\mathbf{x} \sqcap \mathbf{x}', \mathbf{y}) = (f \odot g)(\mathbf{x}, \mathbf{y}) \sqcap (f \odot g)(\mathbf{x}', \mathbf{y})$ and, for a scalar $\alpha \in \mathbb{N}_*$, $(f \odot g)(\mathbf{x}, \alpha \cdot \mathbf{y}) = \alpha + (f \odot g)(\mathbf{x}, \mathbf{y})$.<fnref n="3" /> Such mappings are the natural objects of multilinear algebra, see e.g. [19]. Moving to the tensor space $\mathbb{N}_*^m \otimes \mathbb{N}_*^m$, we can see $f \odot g$, a mapping from $\mathbb{N}_*^{2m}$ to $\mathbb{N}_*$, as a tropically linear mapping from $\mathbb{N}_*^{m^2}$ to $\mathbb{N}_*$, denoted $f \otimes g$, and that associates $(\alpha \otimes \beta) \cdot (\mathbf{x} \otimes \mathbf{y})$ with the tensor $\mathbf{x} \otimes \mathbf{y}$.

Adapted to tropical algebra, the elementary tensor $\kappa = \alpha \otimes \beta$ 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 $\kappa$ as a matrix but sometimes, as in the expression $(\alpha \otimes \beta) \cdot (\mathbf{x} \otimes \mathbf{y})$, it is more natural to see the tensors as vectors of size $nm$.<fnref n="4" />

**► Definition 3.7 (Summing $F_u$ and $G_u$).** The functional $r + \ell$-table associated with a word $u \in \Sigma^*$ is the $m$-by-$(n+1)$ matrix, denoted $H_u$, having $\eta_{i,j} \stackrel{\text{def}}{=} \delta_{i,j} \otimes \gamma_{i,j}$ in position $(i,j)$.

In the above definition, $\delta_{i,j}$ and $\gamma_{i,j}$ are as in the definition of $F_u$ and $G_u$. Finally, every $\eta_{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 $\Sigma$, one obtains

$$r(v_1 u(j), a_i) + \ell(a_i, u(j), v_2) = \eta_{i,j} \cdot (C_{v_1} \otimes D_{v_2}), \quad (9)$$

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

If now one wants to find the maximum value among all $r(v_1 u(j), a_i) + \ell(a_i, u(j), v_2)$, it is not necessary to consider all possibilities for $j = 0, \dots, |u|$ and $i = 1, \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:

**► Definition 3.8 (Piecewise signatures).** Assume a fixed alphabet $\Sigma = \{a_1, \dots, a_m\}$.

- The residual tensors associated with a word $u \in \Sigma^*$ is the set $E_u = \{\eta, \eta', \dots\}$ of all maximal elements in $H_u$.

- The (piecewise) signature of $u$ is the triple $\sigma(u) \stackrel{\text{def}}{=} (E_u, M_u, N_u)$ collecting $E_u$ and the two extension matrices.

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

**► Example 3.9.** We continue with $u = \text{CBBCAC}$. Here $H_u$ contains $3 \times 7 = 21$ tensors obtained as the pairwise products $\delta_{i,j} \otimes \gamma_{i,j}$ of the vectors from $F_u$ and $G_u$ listed earlier, see Example 3.6. It has seven (pairwise incomparable) maximal elements. They are

$$\begin{align*}
\eta_{A,0} &= (0 \ \ast \ \ast) \otimes (1 \ 1 \ 2) = (1 \ 1 \ 2 \ \ast \ \ast \ \ast \ \ast \ \ast \ \ast) , \\
\eta_{B,0} &= (\ast \ 0 \ \ast) \otimes (3 \ 2 \ 3) = (\ast \ \ast \ \ast \ 3 \ 2 \ 3 \ \ast \ \ast \ \ast) , \\
\eta_{C,0} &= (\ast \ \ast \ 0) \otimes (3 \ 2 \ 3) = (\ast \ \ast \ \ast \ \ast \ \ast \ 3 \ 2 \ 3) , \\
\eta_{C,3} &= (\ast \ 1 \ 1) \otimes (2 \ \ast \ 2) = (\ast \ \ast \ \ast \ 3 \ \ast \ 3 \ 3 \ \ast \ 3) , \\
\eta_{C,5} &= (1 \ 2 \ 2) \otimes (\ast \ \ast \ 1) = (\ast \ \ast \ 2 \ \ast \ \ast \ 3 \ \ast \ \ast \ 3) , \\
\eta_{A,6} &= (1 \ 2 \ 2) \otimes (0 \ \ast \ \ast) = (1 \ \ast \ \ast \ 2 \ \ast \ \ast \ 2 \ \ast \ \ast) , \\
\eta_{B,6} &= (1 \ 2 \ 2) \otimes (\ast \ 0 \ \ast) = (\ast \ 1 \ \ast \ \ast \ 2 \ \ast \ \ast \ 2 \ \ast) .
\end{align*}$$

<footnote n="3">³ Here $\alpha \cdot \mathbf{y}$ is a tropical scaling of a vector, which amounts to increase every value in $\mathbf{y}$ by $\alpha$.</footnote>

<footnote n="4">⁴ The size-$nm$ vector is obtained by reading the matrix column by column, see Example 3.9 below.</footnote>
Note that $\eta_{c,5}$ coincides with $\eta_{c,6}$, obtained as $(2 \ 3 \ 3) \otimes (* \ * \ 0)$: however $E_u$ only contains one copy of each maximal tensor. Similarly one has $\eta_{c,0} = \eta_{c,1}$ and $\eta_{c,4} = \eta_{c,5}$.

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

**Lemma 3.10.** For a letter $a \in \Sigma$ where $|\Sigma| = m$, $E_a$ contains $2m - 1$ maximal tensors.

**Proof.** Assume $a = a_s$. There are $2m$ vectors $\delta_{i,j}$ in $F_a$, with $1 \le i \le m$ and $0 \le j \le 1$. The table $G_a$ is the mirror image, i.e., $\gamma_{i,j} = \delta_{i,1-j}$. The $2m$ tensors in $H_a$ are all incomparable except for $\delta_{s,0} \otimes \gamma_{s,0} = \delta_{s,1} \otimes \gamma_{s,1}$, hence the claim. $\quad$

The signature of a word $u$, and more precisely the tensors in $E_u$, provides enough information to compute $h(u)$:

**Theorem 3.11 (Piecewise complexity from signatures).** For any word $u \in \Sigma^*$

$$h(u) = 1 + \max_{\eta \in E_u} \eta \cdot e. \qquad (10)$$

Proof. The proof is simple. Starting with Eq. (1), one has

$$\begin{aligned} h(u) &= \max_{u=u_1 u_2} 1 + r(u_1, a_i) + \ell(a_i, u_2) = 1 + \max_{\substack{0 \le j \le |u| \\ a_i \in A}} r(u, j, a_i) + \ell(a_i, u(j, )) + 1 \\ &= 1 + \max_{\substack{0 \le j \le |u| \\ a_i \in \Sigma}} \eta_{i,j} \cdot (C_{\epsilon} \otimes D_{\epsilon}) = 1 + \max_{\substack{0 \le j \le |u| \\ a_i \in \Sigma}} \eta_{i,j} \cdot (e \otimes e), \end{aligned}$$

using Eq. (9) with $v_1, v_2 = \epsilon$,

$$= 1 + \max_{\substack{0 \le j \le |u| \\ a_i \in \Sigma}} \eta_{i,j} \cdot e,$$

where it is understood that now $e$ denotes a size-$m^2$ tensor,

$$= 1 + \max_{\eta \in E_u} \eta \cdot e,$$

since dot-product is monotonic w.r.t. $\le$.

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

Note that, for $\eta$ an $m^2$-sized vector, the product $\eta \cdot e$ in Eq. (10) is just the minimal entry in $\eta$. However the notation $\eta \cdot e$ is quite convenient, and we shall extend the above reasoning with tensors different from $e$.

**Example 3.12.** Continuing with $u = CBBCAC$, the tensor in $E_u$ that has the largest minimal component is $\eta_{c,3}$ (see Example 3.9), yielding $\eta_{c,3} \cdot e = 3$ and $h(u) = 4$, in agreement with Example 2.2.

For complexity analysis we shall assume that signatures are simply represented as two $m$-by-$m$ matrices together with a collection of $m^2$-sized residual tensors. The values contained in these matrices and tensors are usually encoded using a logarithmic number of bits (e.g., they are written in binary).

**Theorem 3.13 (Space complexity of piecewise signatures).** The size $|\sigma(u)|$ of the signature of a word $u \in \Sigma^*$ is in $\log(n) \cdot m^{O(1)}$ where $n = |u|$ and $m = |\Sigma|$.

**Proof.** Let us write $\#E_u$ for the cardinal of $E_u$. Now $\sigma(u)$ contains two matrices and $\#E_u$ tensors, each made up of $m^2$ scalars. These scalars are bounded by $|u|$ (or are $*$) so only use $O(\log(n))$ space. It is therefore enough to show that $\#E_u$ is bounded by a polynomial of $m$. This is done in Section 5 where we prove $\#E_u \le 2m(2m + 1)$ (see Theorem 5.1). $\quad$

<figure><img src="image_12.png" /></figure>
## 3.5 Combining piecewise signatures

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

**Theorem 3.14 (Compositionality).** The signature $\sigma(uv)$ of the concatenation of two words $u, v \in \Sigma^*$ can be computed from $\sigma(u)$ and $\sigma(v)$.

Furthermore the computation of $\sigma(uv)$ can be done in time polynomial in $|\sigma(u)| + |\sigma(v)| + |\Sigma|$.

The proof is developed in several steps.

**Lemma 3.15.** Let $w = uv$. For $0 \le j \le |u|$, the tensor $(H_w)_{i,j}$ at position $(i,j)$ in $H_w$ is $(I_m \otimes N_v) \cdot (H_u)_{i,j}$. Similarly, for $0 \le j \le |v|$, the tensor $(H_w)_{i,|u|+j}$ in $H_w$ is $(M_u \otimes I_m) \cdot (H_v)_{i,j}$.

The above statement uses tensor products of linear maps. Recall that when $f, g : \mathbb{N}_*^n \to \mathbb{N}_*^m$ are two linear maps, their tensor product $f \otimes g : \mathbb{N}_*^{n^2} \to \mathbb{N}_*^{m^2}$ can be defined via $(f \otimes g)(\prod_i \alpha_i \otimes \beta_i) = \prod_i f(\alpha_i) \otimes g(\beta_i)$. 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 $(e_i \otimes e_j)_{1\le i,j \le n}$ is a base of $\mathbb{N}_*^n \otimes \mathbb{N}_*^n$).

**Proof (of Lemma 3.15).** We only prove the first claim since the second can be obtained directly by mirroring. Assume $0 \le j \le |u|$. By definition, $(H_w)_{i,j}$ is $(F_w)_{i,j} \otimes (G_w)_{i,j}$. Now, by Eq. (5),

$$(F_w)_{i,j} = M_{w,(j)} \cdot e_i = M_{u,(j)} \cdot e_i = (F_u)_{i,j},$$

while, by Eq. (7),

$$(G_w)_{i,j} = N_{w,(j)} \cdot e_i = N_{u,(j)v} \cdot e_i = N_v \cdot N_{u,(j)} \cdot e_i = N_v \cdot (G_u)_{i,j}.$$

Thus

$$(H_w)_{i,j} = (F_u)_{i,j} \otimes (N_v \cdot (G_u)_{i,j}) = (I_m \otimes N_v) \cdot ((F_u)_{i,j} \otimes (G_u)_{i,j}) = (I_m \otimes N_v) \cdot (H_u)_{i,j}$$

as claimed.

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

**Lemma 3.16.** Let $w = uv$. The tensors in $E_w$ are exactly the maximal tensors in $E' \stackrel{\text{def}}{=} \{(I_m \otimes N_v) \cdot \eta \mid \eta \in E_u\} \cup \{(M_u \otimes I_m) \cdot \eta' \mid \eta' \in E_v\}$.

**Proof.** First we claim that $E_w \subseteq E'$. Indeed, consider $(H_w)_{i,j} \in E_w$. We shall assume $0 \le j \le |u|$ since the other case is symmetric. By Lemma 3.15, $(H_w)_{i,j}$ is $(I_m \otimes N_v) \cdot (H_u)_{i,j}$. If $(H_u)_{i,j} \in E_u$ we have proved $(H_w)_{i,j} \in E'$. If, on the other hand, $(H_u)_{i,j} \notin E_u$, then there is some maximal $(H_u)_{i',j'} \in E_u$ that strictly dominates $(H_u)_{i,j}$. Since linear applications are monotonic we deduce

$$(H_w)_{i',j'} = (I_m \otimes N_v) \cdot (H_u)_{i',j'} \ge (I_m \otimes N_v) \cdot (H_u)_{i,j} = (H_w)_{i,j}.$$

Thus, and since $(H_w)_{i,j}$ is a maximal element of $H_w$, necessarily $(H_w)_{i,j}$ and $(H_w)_{i',j'}$ coincide, so $(H_w)_{i,j}$ is indeed the image by $I_m \otimes N_v$ of a tensor from $E_u$, hence is in $E'$.

Now, Lemma 3.15 entails that $E'$ is included in $H_w$. So $E_w = \max H_w \subseteq E' \subseteq H_w$. We conclude that $E_w$ and $\max E'$ coincide.

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

**Proof of Theorem 3.14.** With $\sigma(u) = (E_u, M_u, N_u)$ and $\sigma(v) = (E_v, M_v, N_v)$ one obtains $\sigma(w)$ as follows:

- $M_w$ and $N_w$ are matrix products $M_u \cdot M_v$ and $N_v \cdot N_u$;

- $E_w$ is obtained by computing $E'$ (from Lemma 3.16) and removing the non maximal elements.

All these operations are clearly polynomial-time.

<figure><img src="image_15.png" /></figure>
## 4 Piecewise complexity of SLP-compressed words

An SLP is an acyclic context-free grammar where each non-terminal has only one production rule, i.e., the grammar is deterministic and generates a single word. When a long word has many repetitions it can often be described by an SLP of smaller size and thus SLPs can be used as a compressed data structure for words. Importantly, most compression schemes used for texts and files are equivalent, via polynomial-time encodings, to the mathematically more elegant SLPs. We refer to [17] for more background and details.

Formally, an SLP $X$ with $k$ rules is an alphabet $\Sigma$ together with a list $\langle N_1 \to \rho_1; \dots; N_k \to \rho_k \rangle$ of production rules where each right-hand side $\rho_i$ is either a letter $a$ from $\Sigma$ or a concatenation $N_j N_{j'}$ of two nonterminals with $j, j' < i$. The size of an SLP, denoted $|X|$, is in $O(m + k \log k)$, where $m = |\Sigma|$.

In the context of $X$, the expansion of a nonterminal $N_i$ is a word $\exp(N_i) \in \Sigma^*$ defined inductively via:

$$ \exp(N_i) \stackrel{\text{def}}{=} \begin{cases} a & \text{if } \rho_i = a, \\ \exp(N_j) \exp(N_{j'}) & \text{if } \rho_i = N_j N_{j'}. \end{cases} $$

Finally, the expansion of the SLP itself, written $\exp(X)$, is the expansion $\exp(N_k)$ of its last nonterminal. Note that the length of $\exp(X)$ can reach $2^k - 1$, hence in $2^O(|X|)$.

**Theorem 4.1 (Piecewise signatures of compressed words).** Given an SLP $X$, one can compute $\sigma(\exp(X))$ in time $k^2 \cdot m^{O(1)}$ where $k$ is the number of rules of $X$ and $m$ is the size of its alphabet.

*Proof.* The algorithm computes piecewise signatures $\sigma_1, \dots, \sigma_k$ for each non-terminal of $X$, i.e., with $\sigma_i = \sigma(\exp(N_i))$. There are two cases to handle:

1. when $N_i$ is given by a rule $N_i \to a$, the signature of $a$ has extension matrices given by Eq. (4) and $E_a$ given by Lemma 3.10;

2. when $N_i$ is given by a rule $N_i \to N_j N_{j'}$, the signature $\sigma_i$ is obtained by combining $\sigma_j$ and $\sigma_{j'}$ as shown in Theorem 3.14.

These $k$ steps can each be performed in time $k \cdot m^{O(1)}$ since, by Theorem 3.13, each $\sigma_i$ has size bounded by $\log(|\exp(N_i)|)m^{O(1)}$, hence in $k \cdot m^{O(1)}$.

Combining with Theorem 3.11 we obtain:

**Corollary 4.2.** The piecewise complexity $h(X)$ of (the word represented by) an SLP $X$ can be computed in time $k^2 \cdot m^{O(1)}$.

## 5 The size of piecewise signatures

Fix some alphabet $\Sigma = \{a_1, \dots, a_m\}$. The goal of this section is to bound the number of tensors, written $\#E_u$, in any $E_u$ set. Such bounds are crucial for the complexity results in Theorems 3.13, 3.14, and 4.1. We first show that $\#E_u$ is bounded in $O(m^2)$. This is later complemented with Theorem 5.5 where we exhibit a family of witnesses proving an $\Omega(m^2)$ lower bound.

**Theorem 5.1.** For any $u \in \Sigma^*$, $\#E_u \le 2m(2m + 1)$ where $m = |\Sigma|$.

The proof of Theorem 5.1 is organized in three main lemmas.

For any $1 \le j \le m$, for any $u \in \Sigma^*$, let $M_u[\cdot, j] \stackrel{\text{def}}{=} M_u \cdot e_j$ denote the $j$th column of $M_u$. The columns of $M_u$ respect some patterns that are easier to analyze if we assume that the letters of $\Sigma$ are listed in the order they appear in $u$ (with letters not in $u$ listed at the end).
171:12 A Tropical Approach to the Piecewise Complexity of Words

This is no loss of generality since a permutation of Σ just amounts to a permutation of the indices in our matrices. Wherever we make that assumption, we say that $u$ and $\Sigma$ are *aligned*, or sometimes more succinctly that “$u$ is aligned”.

**Lemma 5.2.** Assume that $u$ is aligned and only uses letters $a_1, \dots, a_p$ with $p \le m$. Then every column $M_u[\cdot, j]$ agrees with one of the following two patterns:

1. If $1 \le j \le p$, then

$$ M_u[\cdot, j] = \begin{pmatrix} 1 & i & i+1 & p & p+1 & m \\ n+1 & \cdots & n+1 & n & \cdots & * \end{pmatrix} = T(n, i, p) $$

for some $1 \le n$ and some $0 \le i < p$. We write $T(n, i, p)$ for this vector.

2. If $p < j \le m$ then

$$ M_u[\cdot, j] = \begin{pmatrix} 1 & p & p+1 & j-1 & j & j+1 & m \\ 1 & \cdots & 1 & \ast & \cdots & \ast & 0 \end{pmatrix} = U(j, p) $$

and we write $U(j, p)$ for this vector.

**Proof.** By induction on the length of $u$. For $|u| = 0$ we have $u = \epsilon$, $p = 0$, $M_u = I_m$, so $p < j$ and indeed $M_u[\cdot, j] = e_j = U(j, 0) = U(j, p)$ for all $j = 1, \dots, k$.

Now assume that $u = va_q$ is aligned and that the claim holds for $v$. First let us see how the columns of $M_u$ are obtained from the columns of $M_v$: for any $j$ we have $M_u[\cdot, j] = (M_v \cdot M_{a_q})[\cdot, j] = M_v \cdot (M_{a_q}[\cdot, j])$. With Eq. (4) we see

$$ M_{a_q}[\cdot, j] = \begin{cases} 1 \cdot e_q = 1 \cdot e_j & \text{if } j = q, \text{ and} \\ (1 \cdot e_q) \sqcap e_j & \text{otherwise.} \end{cases} \qquad (\dagger) $$

Note that the terms in $(\dagger)$ involve a tropical scaling $1 \cdot e_q$ which means “increase every value in $e_q$ by 1”, while the second term contains a tropical sum “$_{\sqcap}$” which means “collect mins componentwise”. Finally $M_u[\cdot, q] = 1 \cdot M_v \cdot e_q = 1 \cdot M_v[\cdot, q]$ if $j = q$, and is $(1 \cdot M_v[\cdot, q]) \sqcap M_v[\cdot, j]$, simply written $\sqcap j$, otherwise.

We consider whether $a_q$ occurs in $v$:

If $a_q$ occurs in $v$ then $M_v[\cdot, q] = T(n, i, p)$ for some $1 \le n, 0 \le i < p$, hence $M_u[\cdot, q] = 1 \cdot T(n, i, p) = T(n+1, i, p)$. Now for $j \ne q$, $M_v[\cdot, j]$ is of the form $T(n', i', p)$ for some $1 \le n', 0 \le i' < p$ if $j \le p$, or $U(j, p)$ if $j > p$. If $M_v[\cdot, j] = T(n', i', p)$ then $M_u[\cdot, j] = \sqcap j = T(\min(n+1, n'), i'', p)$ with $i''$ being $i$ or $i'$. If $M_v[\cdot, j] = U(j, p)$ then observe that $T(n+1, i, p) \sqcap U(j, p) = U(j, p)$.

Similarly, if $a_q$ does not occur in $v$, (in which case $q = p$ by alignment assumption) then $M_v[\cdot, q] = U(p, p-1)$, hence $M_u[\cdot, q] = 1 \cdot M_v[\cdot, q] = T(1, p-1, p)$. For $j \ne q$, $M_v[\cdot, j]$ is of the form $T(n', i', p-1)$ for some $1 \le n', 0 \le i' < p-1$ if $j \le p-1$, or $U(j, p-1)$ if $j > p-1$. If $M_v[\cdot, j] = T(n', i', p-1)$ then $\sqcap j = T(1, i'', p)$ with $i''$ being $i'$ or $p-1$; if $M_v[\cdot, j] = U(j, p-1)$ then $\sqcap j = U(j, p)$.

Finally, all cases yield results that agree with the claim and the proof is completed. ◀

When $u$ is not aligned, the patterns above still apply but modulo a permutation of the lines and columns of $M_u$. Finally, the patterns also apply to $N_u$, i.e., to $M_{uR}$, but now alignment considers the letters of $u$ in their order of last appearance.

**Lemma 5.3.** If all the letters of $\Sigma$ occur in $u$, then $\#E_u \le 2m(2m+1)$.
171:14 A Tropical Approach to the Piecewise Complexity of Words

otherwise $T(n_1, i, p) \otimes T(n'_1, i'_1, p') \le T(n_2, i, p) \otimes T(n'_2, i'_2, p')$ iff $i'_1 \le i'_2$.

Since $0 \le i < p$ can have at most $p$ distinct values, the longest antichain of $S_{p,p'}$ is of size at most $p$. But we can reason symmetrically on $i'$, so in fine the longest antichain of $S_{p,p'}$ is of size at most $\min(p, p')$.

Let us now bound the size of the antichains of

$$R_{p,p'} \stackrel{\text{def}}{=} \{ U(j,p) \otimes T(n',i',p') \mid p < j \le m, n' \in \mathbb{N}, 0 \le i' < p' \}$$

with $0 \le p < m$ and $0 < p' \le m$. Any two elements of $R_{p,p'}$ are comparable if they have identical $U(j,p)$. Since $p < j \le m$ there are $(m-p)$ distinct $U(j,p)$, hence any antichain of $R_{p,p'}$ is of size at most $m-p$.

Symmetrically,

$$L_{p,p'} \stackrel{\text{def}}{=} \{ T(n, i, p) \otimes U(j', p') \mid n \in \mathbb{N}, 0 \le i < p, p' < j' \le m \}$$

with $0 < p \le m$ and $0 \le p' < m$, has antichains of size at most $m-p'$.

Now observe that

$$H_u \subseteq \bigcup_{(p,p') \in P} S(p,p') \cup R(p,p') \cup L(p,p'),$$

where $P$ is the set of all $(p,p')$ such that there exists a factorization $u = vw$ with $v$ and $w$ having respectively $p$ and $p'$ distinct letters. The pairs $(p,p')$ in $P$ depends on the order of appearances and disappearances of letters in $u$, hence they can be ordered such that $p$ is increasing and $p'$ is decreasing. Thus $P$ is of size at most $2m+1$. Moreover, $\min(p,p') + m - p + m - p' \le 2m$. Summing all three bounds, we end up seeing that, as claimed, any antichain in $H_u$ has size bounded by

$$\sum_{(p,p') \in P} \min(p,p') + m - p + m - p' \le 2m(2m+1).$$

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

When $u$ does not use all letters of $\Sigma$ we write $\Gamma$ for the subset of $\Sigma$ that collect the letters occurring in $u$. Now we have two $E_u$ sets depending on whether we consider the underlying alphabet to be $\Gamma$ or $\Sigma$. Accordingly we write $E_u^\Gamma$ and $E_u^\Sigma$ (and also $M_u^\Gamma$, etc.)

**Lemma 5.4.** Assume $|\Gamma| = m-1$. Then $\#E_u^\Sigma \le \#E_u^\Gamma + 2m-1$.

(See Section A.1 for the proof). We can now wrap up this subsection.

**Proof of Theorem 5.1.** Write $m'$ for $|\Gamma|$. By Lemma 5.3, $\#E_u^\Gamma \le 2m'(2m' + 1)$. Invoking Lemma 5.4 $m - m'$ times we obtain the required

$$\begin{aligned} \#E_u^\Sigma &\le \#E_u^\Gamma + (2m' + 1) + \dots + 2m - 1 \\ &\le 2m'(2m' + 1) + \sum_{m' < i \le m} (2i - 1) \\ &\le 2m(2m + 1). \end{aligned}$$

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

We conclude this section with a matching lower bound:

**Theorem 5.5** ($\#E_u$ is in $\Omega(m^2)$). For each $k = 1, 2, \dots$, there exists a word $u_k$ over a $k$-letter alphabet such that $\#E_{u_k} \ge k(k+1)$.

Describing and analyzing $u_k$ is quite involved so the proof has been relegated to Section A.2.
# 6 Concluding remarks

We developed a tropical algebraic approach to the computation of the $r$ and $\ell$ side distances that are the basis for the piecewise complexity of words. This allowed us to construct compact piecewise signatures and combine them elegantly and efficiently. An outcome of this approach is a polynomial-time algorithm for the piecewise complexity of compressed words. The proof that piecewise signatures have at most $O(m^2)$ elements, where $m$ is the size of the alphabet, is technically more involved but is made clearer in the tropical framework.

One can certainly derive more results from our tropical approach to piecewise complexity. For example, recall that the subword universality index $\iota(u)$ of a word $u$ is the largest $L \in \mathbb{N}$ such that $u$ contains all the length-$L$ words of $\Sigma^*$ as subwords $[1, 5]$.

**Theorem 6.1.** $\iota(u) = 0$ iff $\*$ occurs in $M_u$. When $\*$ does not occur in $M_u$ then $\iota(u)$ is the value of the minimal entry in $M_u$.

(See appendix for a proof.) This provides a simpler way (compared to [25]) of computing the universality index of SLP-compressed words in polynomial-time.

We hope that a tropical viewpoint can similarly profit related investigations on piecewise distance, canonical representatives modulo Simon's congruence, piecewise separability, or piecewise-testable languages and associated automata.

The tropical setting also leads to clearer code. We implemented all the algorithms presented in this paper, in order to analyze examples and derive the results in Section 5, or to test huge SLPs. Once a software library for tropical vectors and matrices is set up, the implementation is just a direct transcription of the algebraic formulae given in the paper.

# References

1. L. Barker, P. Fleischmann, K. Harwardt, F. Manea, and D. Nowotka. Scattered factor-universality of words. In Proc. DLT 2020, volume 12086 of Lecture Notes in Computer Science, pages 14-28. Springer, 2020. doi:10.1007/978-3-030-48516-0_2.

2. M. Bojańczyk, L. Segoufin, and H. Straubing. Piecewise testable tree languages. Logical Methods in Comp. Science, 8(3), 2012. doi:10.2168/LMCS-8(3:26)2012.

3. P. Butkovič. Max-algebra: the linear algebra of combinatorics? Linear Algebra and its Applications, 367:313-335, 2003. doi:10.1016/S0024-3795(02)00655-9.

4. O. Carton and M. Pouzet. Simon's theorem for scattered words. In Proc. DLT 2018, volume 11088 of Lecture Notes in Computer Science, pages 182-193. Springer, 2018. doi:10.1007/978-3-319-98654-8_15.

5. J. D. Day, P. Fleischmann, M. Kosche, T. Koß, F. Manea, and S. Siemer. The edit distance to k-subsequence universality. In Proc. STACS 2021, volume 187 of Leibniz International Proceedings in Informatics, pages 25:1-25:19. Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.STACS.2021.25.

6. V. Diekert, P. Gastin, and M. Kufleitner. A survey on small fragments of first-order logic over finite words. Int. J. Foundations of Computer Science, 19(3):513-548, 2008. doi:10.1142/S0129054108005802.

7. M. Droste, W. Kuich, and H. Vogler, editors. Handbook of Weighted Automata. Monographs in Theoretical Computer Science. Springer, 2009.

8. L. Fleischer and M. Kufleitner. Testing Simon's congruence. In Proc. MFCS 2018, volume 117 of Leibniz International Proceedings in Informatics, pages 62:1-62:13. Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.MFCS.2018.62.

9. S. Gaubert and Max Plus. Methods and applications of (max, +) linear algebra. In Proc. STACS '97, volume 1200 of Lecture Notes in Computer Science, pages 261-282. Springer, 1997. doi:10.1007/BFb0023465.
10 P. Gawrychowski, M. Kosche, T. Koß, F. Manea, and S. Siemer. Efficiently testing Simon's congruence. In Proc. STACS 2021, volume 187 of Leibniz International Proceedings in Informatics, pages 34:1-34:18. Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.STACS.2021.34.

11 J. Goubault-Larrecq and S. Schmitz. Deciding piecewise testable separability for regular tree languages. In Proc. ICALP 2016, volume 55 of Leibniz International Proceedings in Informatics, pages 97:1-97:15. Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.ICALP.2016.97.

12 S. Halfon, Ph. Schnoebelen, and G. Zetzsche. Decidability, complexity, and expressiveness of first-order logic over the subword ordering. In Proc. LICS 2017, pages 1-12. IEEE Comp. Soc. Press, 2017. doi:10.1109/LICS.2017.8005141.

13 B. Heidergott, G. J. Olsder, and J. van der Woude. Max Plus at Work. Modelling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and its Applications. Princeton Series in Applied Mathematics. Princeton University Press, 2006.

14 P. Karandikar, M. Kufleitner, and Ph. Schnoebelen. On the index of Simon's congruence for piecewise testability. Information Processing Letters, 115(4):515-519, 2015. doi:10.1016/j.ipl.2014.11.008.

15 P. Karandikar and Ph. Schnoebelen. The height of piecewise-testable languages and the complexity of the logic of subwords. Logical Methods in Comp. Science, 15(2), 2019. doi:10.23638/LMCS-15(2:6)2019.

16 V. I. Levenshtein. Efficient reconstruction of sequences from their subsequences or supersequences. Journal of Combinatorial Theory, Series A, 93(2):310-332, 2001. doi:10.1006/jcta.2000.3081.

17 M. Lohrey. Algorithmics on SLP-compressed strings: A survey. Groups Complexity Cryptology, 4(2):241-299, 2012. doi:10.1515/gcc-2012-0016.

18 S. Lombardy and J. Mairesse. Max-plus automata. In Jean-Éric Pin, editor, Handbook of Automata Theory. Volume I: Theoretical Foundations, chapter 5, pages 151-188. EMS Press, 2021. doi:10.4171/Automata-1/5.

19 D. G. Northcott. Multilinear Algebra. Cambridge Univ. Press, 1984.

20 P. P. Pach. Normal forms under Simon's congruence. Semigroup Forum, 97:251-267, 2018. doi:10.1007/s00233-017-9910-5.

21 J.-É. Pin. The influence of Imre Simon's work in the theory of automata, languages and semigroups. Semigroup Forum, 98(1-8), 2019. doi:10.1007/s00233-019-09999-8.

22 J.-É. Pin, J. M. Taylor, and M. Atiyah. Tropical semirings. In J. Gunawardena, editor, Idempotency, pages 50-69. Cambridge Univ. Press, 1998. doi:10.1017/CBO9780511662508.004.

23 M. Praveen, Ph. Schnoebelen, J. Veron, and I. Vialard. On the piecewise complexity of words and periodic words. In Proc. SOFSEM 2024, volume 14519 of Lecture Notes in Computer Science, pages 456-470. Springer, 2024. doi:10.1007/978-3-031-52113-3_32.

24 J. Sakarovitch and I. Simon. Subwords. In M. Lothaire, editor, Combinatorics on Words, volume 17 of Encyclopedia of Mathematics and Its Applications, chapter 6, pages 105-142. Cambridge Univ. Press, 1983.

25 Ph. Schnoebelen and J. Veron. On arch factorization and subword universality for words and compressed words. In Proc. WORDS 2023, volume 13899 of Lecture Notes in Computer Science, pages 274-287. Springer, 2023. doi:10.1007/978-3-031-33180-0_21.

26 Ph. Schnoebelen and I. Vialard. On the piecewise complexity of words. Acta Informatica, 62(1), 2025. doi:10.1007/s00236-025-00480-4.

27 I. Simon. Hierarchies of Events with Dot-Depth One. PhD thesis, University of Waterloo, Dept. Applied Analysis and Computer Science, 1972. URL: http://maveric.uwaterloo.ca/reports/1972_Simon_PhD.pdf.
28 I. Simon. Piecewise testable events. In Proc. 2nd GI Conf. on Automata Theory and Formal Languages, volume 33 of Lecture Notes in Computer Science, pages 214–222. Springer, 1975. doi:10.1007/3-540-07407-4_23.

29 I. Simon. Limited subsets of a free monoid. In Proc. FOCS '78, pages 143–150. IEEE Comp. Soc. Press, 1978. doi:10.1109/SFCS.1978.21.

A Proofs omitted from main text

A.1 Proof of Lemma 5.4

► Lemma 5.4. Assume $|\Gamma| = m-1$. Then $\#E_u^\Sigma \le \#E_u^\Gamma + 2m-1$.

We first observe that

$$
M_u^\Sigma = \left( \begin{array}{c|c} M_u^\Gamma & \begin{array}{c} 1 \\ \vdots \\ 1 \\ \vdots \\ 0 \end{array} \end{array} \right),
$$

$$
N_u^\Sigma = \left( \begin{array}{c|c} N_u^\Gamma & \begin{array}{c} 1 \\ \vdots \\ 1 \\ \vdots \\ 0 \end{array} \end{array} \right).
$$

As a consequence, and when $i \le m' \stackrel{\text{def}}{=} m-1$, a $\delta_{i,j}^\Sigma$ in $F_u^\Sigma$ is $\delta_{i,j}^\Gamma$ extended with one $*$. When $i=m$, $\delta_{i,j}^\Gamma$ is $(\alpha_1 \cdots \alpha_{m'} 0)$ where $\alpha_s$ is 1 if $a_s$ occurs in $u(j)$, and is $*$ otherwise. The same reasoning applies to a $\gamma_{i,j}^\Sigma$ in $G_u^\Sigma$, except that now, when $i=m$, one considers occurrences in $u(j)$.

Looking now at $H_u^\Sigma$, a tensor $\delta_{i,j}^\Sigma \otimes \gamma_{i,j}^\Sigma$ with $i \le m'$ is just the corresponding $\eta_{i,j}^\Gamma$ with $2m-1$ extra *'s inserted at fixed positions. Therefore, for $i, i' < m$, the tensors at positions $(i, j)$ and $(i', j')$ are ordered (or incomparable) in $H_u^\Sigma$ exactly as in $H_u^\Gamma$. We also have to consider the new tensors at positions $(m, j)$: they all end with 0 hence cannot dominate any tensor on a line with $i < m$ (these end with *). However they can be incomparable with these and contribute new maximal elements. Now, there can be at most $2m' + 1$ incomparable tensors on the line $i = m$ since they can be ordered with pairs $(p, p') \in P$ as in the proof of Lemma 5.3.

Finally $H_u^\Sigma$ contains all the maximal elements of $H_u^\Gamma$ (duly extended) and at most $2m'+1$, i.e., $2m-1$, new maximal elements taken from the last (new) row. Hence the claim.

A.2 Proof of Theorem 5.5

► Theorem 5.5 (#E<sub>u</sub> is in Ω(m<sup>2</sup>)). For each k = 1, 2, ..., there exists a word u<sub>k</sub> over a k-letter alphabet such that #E<sub>u<sub>k</sub></sub> ≥ k(k + 1).

We have to define a word $u_k$ over a k-letter alphabet and show that $\#E_{u_k} \ge k(k+1)$.

Fix $\Sigma = \{a_1, \dots, a_k\}$, sometimes written $\{A, B, C, \dots\}$ in examples. We let $W_k \stackrel{\text{def}}{=} a_1 a_2 \cdots a_k$ denote the word that lists the $k$ letters in order. For $0 \le j \le k$ we further write $W_{j,k}$ for the suffix $W(k-j, k)$, i.e., the $j$ last letters of $W_k$. We then define $v_k$ and $u_k$ via

$$
v_k \stackrel{\text{def}}{=} W_{1,k} W_{2,k} \cdots W_{k-1,k},
$$

$$
u_k \stackrel{\text{def}}{=} W_k v_k a_1 v_k^R W_k^R .
$$

Observe that $u_k$ is a palindrome. As an example, here are $u_k$ and $v_k$ for $k=4$:

$v_4 = W_{1,4} W_{2,4} W_{3,4} = \text{D CD BCD},$

$$
u_4 = \underbrace{\text{ABCD}}_{W_4} \underbrace{\text{DCBCD}}_{v_4} \text{ A } \underbrace{\text{DCBDCD}}_{v_4^R} \underbrace{\text{DCBA}}_{W_4^R} .
$$
171:18 A Tropical Approach to the Piecewise Complexity of Words

We start by computing the extension matrices associated with various prefixes and suffixes of $u_k$. An easy induction on $k$ provides the following $k$-by-$k$ matrices for any $k \ge 2$:

$$M_{W_k} = N_{W_k^R} = \begin{pmatrix} 1 & 2 & \cdots & 2 \\ \vdots & \vdots & & \vdots \\ 1 & 2 & \cdots & 1 \end{pmatrix},$$

$$N_{W_k} = M_{W_k^R} = \begin{pmatrix} 1 & \cdots & 1 \\ 2 & \cdots & 2 \\ \vdots & \vdots & \vdots \\ 2 & \cdots & 1 \end{pmatrix}.$$

From these, we can deduce the $k$-by-$k$ extension matrices for the $W_{n,k}$ where $0 \le n \le k$:

$$M_{W_{n,k}} = N_{W_{n,k}^R} = \left( \frac{I_{k-n}}{1} \middle| \frac{*}{M_{W_n}} \right),$$

$$M_{W_{n,k}^R} = N_{W_{n,k}} = \left( \frac{I_{k-n}}{1} \middle| \frac{*}{N_{W_n}} \right).$$

Combining the above matrices, we compute the extension matrix for $v_k$:

$$M_{v_k} = \begin{pmatrix} 0 & * & \cdots & * \\ 1 & 1 & 2 & \cdots & 2 \\ 1 & 2 & 2 & 3 & \cdots & 3 \\ 1 & \cdots & 3 & 3 & \cdots & \cdots \\ 1 & \cdots & \cdots & \cdots & \cdots & \cdots \\ 1 & 2 & 3 & \cdots & 3 \end{pmatrix}$$

with 3 as the maximal value, filling the bottom-right part. A consequence is that $M_{W_k v_k a_1}$, obtained as the product $M_{W_k} \cdot M_{v_k} \cdot M_{a_1}$ is the $k$-by-$k$ all-2s matrix.

Let us now compute $N_{v_k}$ and $M_{W_k v_k a_1 v_k^R}$, noting that $W_k v_k a_1 v_k^R$ is $u_k(k)^R$:

$$N_{v_k} = \left( \begin{array}{c|c} \begin{array}{ccccccc} 0 & * & \cdots & * & & & \\ 1 & 1 & 2 & \cdots & k-3 & k-2 & k-1 \\ 1 & 2 & 2 & \cdots & & & \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 1 & 3 & \cdots & k-3 & \cdots & k-2 & k-1 \\ & & & k-2 & k-2 & k-1 & k-1 \\ 1 & 2 & \cdots & k-2 & \cdots & k-1 & k-1 \end{array} & M_{W_k v_k a_1 v_k^R} = \begin{array}{c} \begin{pmatrix} 2 & 3 & \cdots & k & k+1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 2 & 3 & \cdots & k & k+1 \end{pmatrix} \\ \begin{pmatrix} 2 & 3 & \cdots & k & k+1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 2 & 3 & \cdots & k & k+1 \end{pmatrix} \end{array} \right).$$

Finally, for a factorization $u_k = u_k(,n)u_k(n,)$ with $n < k$, we compute $M_{u_k(n,)}$ and $N_{u_k(n,)}$, noting that $u_k(,n) = W_n$ and $u_k(n,)^R = W_k v_k a_1 v_k^R a_k a_{k-1} \cdots a_{n+1}$.

$$M_{u_k(n,)} = \left( \frac{M_{W_n}}{*} \middle| \frac{1}{I_{k-n}} \right), \quad N_{u_k(n,)} = \left( \begin{array}{c|c} 1 & n+n+1+k \\ \begin{array}{c} 2 \\ 3 \\ \vdots \\ 3 \end{array} & \begin{array}{c} n+1 \\ n+3 \\ \vdots \\ n+3 \end{array} \end{array} \right).$$

**Lemma A.1.** $H_{u_k}$ contains all the $M_{u_k(n,)}[\cdot, i] \otimes N_{u_k(n,)}[\cdot, i]$ and the $N_{u_k(n,)}[\cdot, i] \otimes M_{u_k(n,)}[\cdot, i]$ for $0 \le n < i \le k$.

**Proof.** Indeed this just expresses the $\delta_{i,n}$ and $\gamma_{i,n}$ vectors of $F_{u_k}$ and $G_{u_k}$ as columns of the matrices we computed. Note that, in the claim, the products of the first kind are taken from the $k$ first columns of $H_u$, while the products of the second kind come from its $k$ last columns but are expressed in terms of the first columns of $F_{u_k}$ and $G_{u_k}$, taking advantage of the symmetry in $u_k$. ◀
Looking now at the matrix for $M_{u_k(n)}$ we see that, for $n < i$, the $i$th column is $U(i, n)$ in the notation used for Lemma 5.2, while the $i$th column of $N_{u_k(n)}$ is $T(n + 2, k, k)$.

**► Lemma A.2.** *The set*

$$S_k \stackrel{\text{def}}{=} \{ U(i, n) \otimes T(n + 2, k, k), T(n + 2, k, k) \otimes U(i, n) \mid 0 \le n < i \le k \}$$

is an antichain in $H_{u_k}$.

**Proof (Sketch).** We know that these tensors are in $H_{u_k}$ since they are exactly those listed in Lemma A.1, now expressed as $T$ and $U$ patterns. Stated in this form it is easy to see that they are pairwise incomparable, hence form an antichain. ◀

We now conclude with the announced result:

**► Lemma A.3.** $\#E_{u_k} \ge k(k+1)$.

**Proof.** After the above preparations, and since $S_k$ has cardinal $k(k+1)$, it is enough to prove that the tensors in $S_k$ are maximal in $H_{u_k}$. However we are not ready to do precisely that in this extended abstract.

Instead, consider that every $U(i, n)$ for all $0 \le n < k - 1$, $n < i \le k$ contains a $*$. If there exist a factorization $u_k = v'w'$ and some $i' \le k$ such that $U(i, n) \otimes T(n + 2, k, k)$ is strictly dominated by $M_{v'}[\cdot, i'] \otimes N_{w'}[\cdot, i']$, then necessarily $U(i, n) \le M_{v'}[\cdot, i']$, thus $M_{v'}[\cdot, i']$ contains a $*$ at every position where $U(i, n)$ does. Hence we deduce that either $v'$ is a prefix of $u_k(n)$ and $i = i'$, or $v' = v_k(n+1) = v_k(n)a_{n+1}$ with $i = n+1$ and $i' \le n+1$. However, in these few specific cases that are easy to list, we can readily check that the full product $U(i, n) \otimes T(m + 2, k, k)$ is not dominated by $M_{v'}[\cdot, i'] \otimes N_{w'}[\cdot, i']$. So all but two tensors in $S_k$ are already seen to be maximal.

There remains the case $n = k - 1$ and $i = k$. Here it is harder to show that $U(k, k - 1) \otimes T(k + 1, k, k)$, i.e., $\eta_{k,k-1}$, is maximal since this tensor has no $*$ and thus could possibly be dominated by some $\eta_{i',j}$ for any $i', j$ with $k \le j \le |u_k| - k$, i.e., for a factorization $u_k = v'w'$ where both $v'$ and $w'$ contain the full alphabet.

However, and since $\eta_{k,k-1}$, is incomparable with the rest of $S_k$, if $\eta_{k,k-1}$ is not maximal, then $H_{u_k}$ contains a tensor that dominates $\eta_{k,k-1}$, hence that necessarily contains no $*$ and thus does not dominate any other tensor from $S_k$. (The same argument goes for the symmetric tensor on the right-hand side of $H_{u_k}$.) Finally, the announced $k(k+1)$ lower bound on the size of $\#E_{u_k}$ is demonstrated. ◀

## A.3 Proof of Theorem 6.1

**► Theorem 6.1.** $\iota(u) = 0$ iff $*$ occurs in $M_u$. When $*$ does not occur in $M_u$ then $\iota(u)$ is the value of the minimal entry in $M_u$.

First, if $*$ occurs in $M_u$, then $u$ does not contain every letter of the alphabet, hence $\iota(u) = 0$.

In the other cases, we consider the arch factorization of $u$ (see [25]). Observe that when $u$ contains exactly one arch and ends with letter $a_i$, the $i$-th row of $M_u$ is a row of 1, while in the other rows only the numbers 1 and 2 appear.

If $\iota(u) = k \in \mathbb{N}$ then $u$ can be factorized as $u_1 \dots u_k v$ where every $u_j$ is an arch and $v$ does not contain every letter of the alphabet. Let $a_i$ be the last letter of $u_1$. Then observe that, $M_{u_1 \dots u_k}$ contains only the numbers $k$ and $k + 1$, and its $i$-th row is a row of $k$'s. Thus, $M_u = M_{u_1 \dots u_k} \cdot M_v$ contains only the numbers $k$ and $k + 1$, and $M_u[i, j] = k$ for any $j$ such that $a_j$ does not appear in $v$.