# Injective envelopes of transition systems and Ferrers languages

Mustapha Kabil, Maurice Pouzet

► To cite this version:

Mustapha Kabil, Maurice Pouzet. Injective envelopes of transition systems and Ferrers languages. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), 2020, 54, pp.4. 10.1051/ita/2020005. hal-02903903

HAL Id: hal-02903903

https://hal.science/hal-02903903

Submitted on 21 Jul 2020

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
INJECTIVE ENVELOPES OF TRANSITION SYSTEMS
AND FERRERS LANGUAGES*

MUSTAPHA KABIL<fnref n="1" /> AND MAURICE POUZET<fnref n="2" />,**

**Abstract.** We consider reflexive and involutive transition systems over an ordered alphabet A equipped with an involution. We give a description of the injective envelope of any two-element set in terms of Galois lattice, from which we derive a test of its finiteness. Our description leads to the notion of Ferrers language.

**Mathematics Subject Classification.** 06A15, 06D20, 46B85, 68Q70, 68R15.

Received July 4, 2019. Accepted April 21, 2020.

# 1. INTRODUCTION AND PRESENTATION OF THE MAIN RESULTS

This paper is about involutive and reflexive transition systems from a metric point of view. It focuses on injective envelopes and particularly on injective envelopes associated with some special languages as Ferrers language that we introduce at this occasion.

A metric point of view for discrete structures, inspired from the work of Quilliot (1983), was applied first to posets and graphs, by the second author [37] and developed through the theses of Jawhari (1983), Misane (1984) and [23] (1986). It was then extended to transition systems, [38] (1994), [42] (1992), [29] (1998), [30] (2018). In the case of transition systems, this point of view consists to consider arbitrary transition systems as metric spaces. The distance between two states is a language instead of a non-negative real. To a transition system $M := (Q, T)$, with set of states $Q$ and set of transitions $T$ over an alphabet $A$ we associate a map $d_M$ from $Q \times Q$ into the set $\wp(A^*)$ of languages over $A$. The value $d_M(x, y)$ is the language accepted by the automaton $A := (M, \{x\}, \{y\})$ having $x$ as an initial state and $y$ as a final state. The set $\wp(A^*)$ is an ordered monoid, the monoid operation being the concatenation of languages (with neutral element $\square$), the language reduced to the empty word $\square$) and the order the reverse of inclusion. The map $d_M$ has similar properties of an ordinary distance (e.g., it satisfies the triangular inequality). Hence, we may use concepts and techniques of the theory of metric spaces in the study of transition systems as well as classes of transition systems. The basic concepts of the theory of metric spaces, as balls, contraction maps extend to transition systems and more generally to metric spaces

<footnote>* Dedicated to the memory of Maurice Nivat.</footnote>

<footnote>Keywords and phrases: Metric spaces, injective envelopes, transition systems, Ferrers languages, ordered sets, interval orders, well-quasi-order.</footnote>

<footnote n="1">¹ Laboratoire Mathématiques et Applications, Département de Mathématiques, Faculté des Sciences et Techniques, Université Hassan II-Casablanca, BP 146 Mohammédia, Morocco.</footnote>

<footnote n="2">² Univ. Lyon, Université Claude-Bernard Lyon1, CNRS UMR 5208, Institut Camille Jordan, 43 bd. 11 Novembre 1918, 69622 Villeurbanne Cedex, France and Mathematics & Statistics Department, University of Calgary, Calgary, Alberta, Canada.</footnote>

<footnote>** Corresponding author: pouzet@univ-lyon1.fr</footnote>
over $\wp(A^*)$. The category of ordinary metric spaces with the contraction as morphisms enjoy some interesting properties. Some important categorical notions as injective, absolute retract and hyperconvex spaces coincide [1] and every space has an injective envelope, a famous result of Isbell [22]. Essentially, an injective object $E$ has the property that every set of inequalities about distances with parameters in $E$ and which is consistent, in the sense that this set of inequalities has a solution in some isometric extension of $E$, has a solution in $E$; the injective envelope of a metric space $E$ is a minimal isometric extension of $E$ which is injective (see [17] for a survey on these aspects of metric spaces).

It was tempting to extend these results to the category of transitions systems and to the category of metric spaces over $\wp(A^*)$. This was partially done in [38] and developped in [28–30, 42] as a by-product of the theory of metric spaces over a Heyting algebra developped in [23] and [38].

The frame of this theory is the following. A Heyting algebra is a complete lattice $\mathcal{H}$ with a monoid operation (not necessarily commutative) and an involution – which is isotone and reverses the operation. In order to be closer to the operation of concatenation of languages, we denote by $\cdot$ the monoid operation. We denote by 1 the neutral element of the monoid, and we suppose that distributivity law below holds

$$ \bigwedge \{p_i \cdot q : i \in I\} = \bigwedge \{p_i : i \in I\} \cdot q. \qquad (1.1) $$

According to the terminology of Kaarli and Radelecki [25], this structure is the dual of an involutive quantale and, provided that 1 is the least element of the monoid, the dual of an integral involutive quantale (IQ and $I^2Q$ for short), see the recent treatise of quantales [16]. Here we stick to the name of Heyting algebra that we used in a series of papers.

A distance over $\mathcal{H}$ on a set $E$ is a map $d$ from $E \times E$ to $\mathcal{H}$ satisfying the following conditions:

d1) $d(x, y) \le 1$ if and only if $x = y$;

d2) $d(x, y) \le d(x, z) \cdot d(z, y)$;

d3) $d(x, y) = \overline{d(y, x)}$ for all $x, y, z \in E$.

The category of metric spaces over a Heyting algebra $\mathcal{H}$ with the contractions as morphisms was studied in [23] when 1 is the least element of $\mathcal{H}$ and in full generality in [38]. Due to the fact that joins exist in $\mathcal{H}$, this category has products. Due to the distributivity condition, $\mathcal{H}$ can be equipped with a distance $d_{\mathcal{H}}$ and every metric space can be embedded isometrically into a power of that metric space ([38], Prop. 3.5.7, p. 136.) Once retractions and coretractions are defined and isometries are viewed as approximations of coretractions, one can define hyperconvex spaces, injective metric spaces, and absolute retracts. It follows from the embedding result mentioned above that these three types of spaces coincide (see [23], II-2.9 Thm. 1 when 1 is the least element of $\mathcal{H}$ and [38], Thm. 3.5.18, p. 138 in the general case). It was proved in [23], II-3.1, Theorem 2, page 192 that if 1 is the least element of $\mathcal{H}$, every space has an injective envelope.

This can be applied to transition systems. Provided that the alphabet $A$ is equipped with an involution –, the involution is extended to $A^*$ and then to $\wp(A^*)$, and our transition systems $M$ are involutive, in the sense that $(x, a, y) \in T$ if and only if $(y, \bar{a}, x) \in T$, then we have $d_M(x, y) = \overline{d_M(y, x)}$. Here, we consider involutive transition systems that are reflexive, that is every letter occurs to every vertex: $(x, a, x) \in T$ for every $x \in Q$ and $a \in A$. In this case, distances values are final segments of $A^*$ equipped with the subword ordering, that is subsets $F$ of $A^*$ such that $u \in F$ and $u \le v$ for the subword ordering imply $v \in F$. The structure $\mathbf{F}(A^*)$ on the set $F(A^*)$ final segments, whose order is the reverse of the inclusion and operation is the concatenation of initial segments is a Heyting algebra in which the neutral element, namely $A^*$, is the least element. Thus metric spaces over $\mathbf{F}(A^*)$ have an injective envelope and, in addition, each injective envelope comes from a transition systems.

The study of such injective envelope was initiated in [29] and applied to the study of retracts of directed graphs. It was based on the properties of the injective envelope of two-element metric spaces. The obvious reason to consider those is their relative simplicity. A deeper reason is that every injective is a retract of a product of injective envelopes of two-element metric spaces, a fact leading to a test of the finiteness of the injective envelope of a finite metric space (see Thm. 5.4). In the case of ordinary metric space, the injective envelope of
two elements at distance $r$ is a segment of length $r$. In our case, it is a bit more complex but it can be described. Furthermore, it can be constructed by concatenation of special envelopes (Thm. 1.3 below), a fact which leads to the freeness of the monoid $\mathbf{F}(A^*) \setminus \{\emptyset\}$ [30] (the decomposition property behind this construction is given in Section 2.4; it does not hold in every Heyting algebra and requires further investigations).

This work is a continuation of the work published in [28–30]. A large account of its properties was given in [28] and [30]. In this paper, we look at the many facets of this object which have not been published yet.

We start with a characterization of the injective envelope of a two-element metric space in terms of reflexive and involutive transition systems.

If a set of words $F$ is a final segment of $A^*$, the injective envelope $S_F$ of the two-element space $\{x, y\}$ such that $d(x, y) = F$ is associated to an involutive and reflexive transition system. Let $M_F$ be this transition system and $A_F$ be the automaton $(M_F, \{x\}, \{y\})$.

**Theorem 1.1.** Let $\mathcal{A} := (M, \{x\}, \{y\})$ be a reflexive and involutive automaton accepting a final segment $F$ of $A^*$. Then $\mathcal{A}$ is isomorphic to $A_F$ iff for every reflexive and involutive automaton $\mathcal{A}' := (M', \{x'\}, \{y'\})$ which accepts $F$, the following properties hold:

(i) Every automata morphism $f: \mathcal{A} \to \mathcal{A}'$, if any, is an isometric embedding;

(ii) The map $g: \{x', y'\} \to M$ such that $g(x') = x$ and $g(y') = y$ extends to a morphism of automata from $\mathcal{A}'$ to $\mathcal{A}$.

We will obtain this result as a consequence of a characterization of the injective envelope among metric spaces (Thm. 2.1) given in Section 2.

This result does not say much. In order to give a precise description, we develop an approach in terms of Galois correspondence. The general setting of Galois correspondence is also developped under the name of *formal concept analysis*, see Chapter 3 and 7 of [9]. All we need reduces to the following.

To a subset $L$ of $A^*$ we associate the incidence structure $R := (A^*, \rho_L, A^*)$ where $\rho$ is the binary relation on $A^*$ defined by $u\rho_L v$ if the concatenation $uv$ of $u$ and $v$ belongs to $L$. For each $v \in A^*$, let $\rho^{-1}(v) := \{u \in A^* : u\rho_L v\}$ and for $V \subseteq A^*$, let $R_\wedge^{-1}(V) := \bigcap_{v \in V} \rho_L^{-1}(v)$. The collection of all $R_\wedge^{-1}(V)$ for $V \subseteq A^*$, once ordered by inclusion, forms a complete lattice (the meet of a family of members of this collection is their intersection while the join is the meet of members containing the union). This lattice, denoted by $\text{Gal}(R)$ is called the *Galois lattice* associated to the incidence structure $R$. If $L$ is a final segment of $A^*$, say $F$, ordered by the subword ordering, then the members of $\text{Gal}(R)$ are final segments of $A^*$. Being a subset of $\mathcal{H} := \mathbf{F}(A^*)$, $\text{Gal}(R)$ inherits the metric structure $d_\mathcal{H}$ of $\mathcal{H}$ (the definition of the distance $d_\mathcal{H}$ is recalled in Sect. 2.1). Containing $x := A^*$ and $y := F$, two elements which verify $d_\mathcal{H}(x, y) = F$, this metric space, say $S_F$, turns to be the injective envelope of $\{x, y\}$. The distance comes from the transition system $M := (\text{Gal}(R), T)$ where $(X, a, Y) \in T$ if $a \in d(X, Y)$ and the automaton $A_F := (M, \{x\}, \{y\})$ accepts $F$. The inclusion order on $\text{Gal}(R)$ can also be recovered from the distance on $S_F$ and $x$ and $y$: indeed, if $X, Y \in S_F$, then $X \supseteq Y$ if and only if $d(X, X) \leq d(X, Y)$ or, equivalently, $d(X, y) \geq d(Y, y)$ (see Sect. 2.3). Hence, with the elements $x$ and $y$ be given, the injective envelope has a lattice structure. A description is given in Theorem 1.2.

For concrete examples, suppose that $\mathcal{A}$ is an ordered alphabet, that $A^*$ is ordered via the Higman ordering (a generalization of the subword ordering): if $\alpha$ and $\beta$ are two elements in $A^*$ such $\alpha := a_0 \cdots a_{n-1}$ and $\beta := b_0 \cdots b_{m-1}$ then $\alpha \le \beta$ if there is an injective and increasing map $h$ from $\{0, \dots, n-1\}$ to $\{0, \dots, m-1\}$ such that for each $i$, $0 \le i \le n-1$, we have $a_i \le b_{h(i)}$. If the order on $\mathcal{A}$ is the equality relation, the Higman ordering is the subword ordering. For $u \in A^*$, set $\downarrow u := \{v \in A^* : v \le u\}$ and $\uparrow u := \{v \in A^* : u \le v\}$. Let $F$ be a final segment finite union of final segments $F_0, \dots, F_i, \dots, F_{k-1}$ of $A^*$ such that each $F_i$ is generated by a set $X_i$, (i.e., $F_i = \uparrow X_i := \{v \in A^* : u \le v \text{ for some } u \in X_i\}$), of the form $X_i := X_{0,i} \cdots X_{j,i} \cdots X_{n_i,i}$ with $X_{j,i} \subseteq \mathcal{A}$, that is a set of words $u$ of the same length $n_i$, all of the form $u := a_0 a_1 \cdots a_{n_i-1}$ with $a_j \in X_{j,i} \subseteq \mathcal{A}$. As indicated below if the alphabet is finite, this amounts to say that $F$ is finitely generated, a condition that is always realized in this case. Let $\mathbf{n}_0 \otimes \cdots \otimes \mathbf{n}_{k-1}$ be the direct product of $k$ chains $\mathbf{n}_0, \dots, \mathbf{n}_{k-1}$ where $\mathbf{n}_i := \{0, \dots, n_i - 1\}$ is equipped with the natural ordering, and let $\mathbf{F}(\mathbf{n}_0 \otimes \cdots \otimes \mathbf{n}_{k-1})$ be the collection of final segments of $\mathbf{n}_0 \otimes \cdots \otimes \mathbf{n}_{k-1}$ ordered by inclusion.

We prove (see Sect. 5):
<figure><img src="image_2.png" /><figcaption>FIGURE 1.</figcaption></figure>

**Theorem 1.2.** As a Galois lattice, the injective envelope $S_F$ can be identified with an intersection closed subset of the set $\mathbf{F}(\mathbf{n}_0 \otimes \cdots \otimes \mathbf{n}_{k-1})$. Moreover if $\downarrow u_i \cap \downarrow u_j = \{\square\}$ whenever $u_i \in X_i$, $u_j \in X_j$, and $i \neq j$, then $S_F$ identifies to the full set $\mathbf{F}(\mathbf{n}_0 \otimes \cdots \otimes \mathbf{n}_{k-1})$.

We recall that a poset $P$ is *well-quasi-ordered*, in brief w.q.o., if it *well-founded* (every non empty subset contains a minimal element) and contains no infinite antichain. A fundamental result of G. Higman [19] asserts that the free ordered monoid $A^*$ is w.q.o. whenever the alphabet $A$ is w.q.o.. The set of final segments of a w.q.o. set, once ordered by reverse of the inclusion, is *well-founded* [19]. Hence, if our alphabet $A$ is w.q.o., every final segment $F$ of $A^*$ is generated by finitely many words $u_0, \dots, u_{k-1}$, hence has the form mentioned above. Consequently, the corresponding injective envelope is finite. Concerning its size, let us mention that if $k=2$, then $\mathbf{F}(\mathbf{n}_0 \otimes \mathbf{n}_1)$ has size $\binom{n_0+n_1}{n_0}$ [1] (3.16, p. 80). If $n_0 = \dots = n_{k-1} = 2$, then $(\mathbf{F}(\mathbf{n}_0 \otimes \cdots \otimes \mathbf{n}_{k-1}), \supseteq)$ is isomorphic to $\mathrm{FD}(k)$, the free distributive lattice with $k$ generators. It is a famous problem, raised by Dedekind, to give an explicit and workable formula for $\mathrm{FD}(k)$. The largest exact value known is $\mathrm{FD}(8)$ [47]. An asymptotic formula was given by Korshunov in 1981 [32]. For an example, on the two-letter alphabet $A = \{a, b\}$, the words $u_0 := aa$ and $u_1 := bb$ give the lattice (ordered by reverse of inclusion) and graph represented on Figure 1.

Structural properties of transition systems rely upon algebraic properties of languages and conversely. In fact, transition systems can be viewed as geometric objects interpreting these algebraic properties. An illustration of this claim is given by the following result (which is the automaton version of Cor. 4.9 [29]).

**Theorem 1.3.** Let $F$ be a nonempty final segment of $A^*$. If $F$ is the concatenation of final segments $F_1, \dots, F_n$ then the automaton $\mathcal{A}_F := (M_F, \{x\}, \{y\})$ associated to the injective envelope $S_F$ is the concatenation $\mathcal{A}_{F_1} \cdots \mathcal{A}_{F_n}$ of automata $\mathcal{A}_{F_i} := (M_{F_i}, \{x_i\}, \{y_i\})$ associated to the injective envelope $S_{F_i}$, this concatenation being obtained by identifying each $y_i$ with $x_{i+1}$.

The fact that an automaton decomposes into such a concatenation can be viewed directly by looking at states which disconnect the underlying graph. From this follows the uniqueness of such a decomposition. This uniqueness amounts to the fact that the monoid $\mathbf{F}(A^*) \setminus \{\emptyset\}$ is free. A purely algebraic proof of this result is given in [30].

We discuss then the relationship between the minimal deterministic automaton accepting a final segment $F$, say $Min_F$, and the automaton $\mathcal{A}_F$ associated to the injective envelope $S_F$. This minimal automaton is part of $\mathcal{A}_F$, but not in an isometric way ($Min_F$ being deterministic cannot be reflexive, in general it is not involutive). Among involutive and reflexive transition systems accepting a given final segment $F$, we consider those with a minimum number of states and among those, the ones with a maximal number of transitions, that we call Minmax automata. Examples given by Mike Main and communicated by Maurice Nivat [35] show that contrarily to the case of deterministic automata, these automata are not unique.
We introduce Ferrers languages. A language $L$ over $A^*$ is Ferrers if

$$xx' \in L \text{ and } yy' \in L \text{ imply } xy' \in L \text{ or } yx' \in L \text{ for all } x, x', y, y' \in A^*. \qquad (1.2)$$

The class of Ferrers languages is closed under complement but not under concatenation. Still, if $F_1, \dots, F_n$ are Ferrers and each $F_i$ is a final segment of $A^*$ then the concatenation $F_1 \cdots F_n$ is Ferrers (Cor. 6.2).

We prove that a final segment $F$ of $A^*$ is Ferrers if and only if the injective envelope $S_F$ is totally orderable, that is there is a linear order $\le$ on $S_F$ such that $d(x, z) \le d(x, y)$ and $d(z, y) \le d(x, y)$ for all $x \le z \le y$. (Thm. 6.8).

Over a finite alphabet $A^*$, Boolean combinations of final segments of $A^*$ are called piecewise testable languages. They have been characterized by Simon [44] by the fact that their syntactical monoid is $\mathcal{J}$-trivial. The Boolean algebra of piecewise testable languages is included into the Boolean algebra generated by rational Ferrers languages. Indeed, over a finite alphabet, every final segment is a finite union of rational Ferrers languages. But, on an alphabet with at least two letters, there are rational Ferrers languages which are not piecewise testable (e.g., $L := A^*b$ on $A := \{a, b\}$). We do not know if they are dot-depth one.

This paper is organized as follows. Properties of metric spaces over a Heyting algebra and their injective envelopes are summarized in Section 2. In Section 3, we introduce the Heyting algebra $\mathbf{F}(A^*)$. In Section 4 we consider transition systems as metric spaces. In Section 5 we describe the injective envelope of a two-element metric spaces over $\mathbf{F}(A^*)$; we prove Theorems 1.1 and 1.2 and conclude the section by a counterexample about Minmax automata due to M. Main. Ferrers languages are introduced in Section 6.

The results developped here have been presented at the International Conference on Discrete Mathematics and Computer Science (DIMACOS'11) organized by A. Boussairi, M. Kabil, and A. Taik in Mohammedia (Morocco) May, 5-8, 2011. They were never published; a part of it was included into the Thèse d'État defended by the first author [28].

The theme of the research presented here benefited greatly from Maurice Nivat, especially during the years ninety. We have a vivid memory of the numerous exchanges, of his encouragements and his role as referee and member of the jury of the thesis of the fist author in June 1992. We miss his smiling energy. We dedicate this work to his memory.

## 2. METRIC SPACES OVER A HEYTING ALGEBRA

### 2.1. Basic facts

We recall the basic facts we need about metric spaces over a Heyting algebra. We put emphasis on hyperconvex spaces. We refer to [17] for a short survey on hyperconvex spaces in the frame of usual metric spaces. The following is extracted from [30] (for more details, see [29] and the survey paper [31]).

Let $\mathcal{H}$ be a Heyting algebra and let $E$ be a set. A $\mathcal{H}$-distance on $E$ is a map $d: E^2 \to \mathcal{H}$ satisfying the following properties for all $x, y, z \in E$:

$$ (1) \quad d(x, y) = 1 \iff x = y, $$

$$ (2) \quad d(x, y) \le d(x, z) \cdot d(z, y), $$

$$ (3) \quad d(x, y) = d(y, x). $$

The pair $(E, d)$ is called a $\mathcal{H}$-metric space. If there is no danger of confusion we will denote it $E$.

A $\mathcal{H}$-distance can be defined on $\mathcal{H}$. This fact relies on the classical notion of residuation. Let $v \in \mathcal{H}$. Given $\beta \in \mathcal{H}$, each of the sets $\{r \in \mathcal{H} : v \le r \cdot \beta\}$ and $\{r \in \mathcal{H} : v \le \beta \cdot r\}$ has a least element, that we denote respectively $[v \cdot \beta^{-1}]$ and $[\beta^{-1} \cdot v]$ (note that $[\beta^{-1} \cdot v] = [\bar{v} \cdot (\bar{\beta})^{-1}]$). It follows that for all $p, q \in \mathcal{H}$, the set

$$ D(p, q) := \{r \in \mathcal{H} : p \le q \cdot \bar{r} \text{ and } q \le p \cdot r\} $$
has a least element, namely $[\bar{p} \cdot (\bar{q})^{-1}] \vee [p^{-1} \cdot q]$, that we denote $d_{\mathcal{H}}(p, q)$. As shown in [23], the map $(p, q) \to d_{\mathcal{H}}(p, q)$ is a $\mathcal{H}$-distance.

Let $(E, d)$ and $(E', d')$ be two $\mathcal{H}$-metric spaces. A map $f: E \to E'$ is a contraction or a contraction map from $(E, d)$ to $(E', d')$ provided that $d'(f(x), (f(y)) \le d(x, y)$ holds for all $x, y, \epsilon \in E$. In the case of ordinary metric spaces, a widely used term is non-expansive. The map $f$ is an isometry if $d'(f(x), (f(y)) = d(x, y)$ for all $x, y, \epsilon \in E$. We say that $E$ and $E'$ are isomorphic, a fact that we denote $E \cong E'$, if there is a surjective isometry from $E$ onto $E'$.

Let $((E_i, d_i))_{i \in I}$ be a family of $\mathcal{H}$-metric spaces. The direct product $\prod_{i \in I} (E_i, d_i)$, is the metric space $(E, d)$ where $E$ is the cartesian product $\prod_{i \in I} E_i$ and $d$ is the "sup" (or $\ell^\infty$) distance defined by $d((x_i)_{i \in I}, (y_i)_{i \in I}) = \bigvee_{i \in I} d_i(x_i, y_i)$.

For a $\mathcal{H}$-metric space $E$, $x \in E$ and $r \in \mathcal{H}$, we define the ball $B_E(x, r)$ as the set $\{y \in E : d(x, y) \le r\}$. We say that $E$ is convex if the intersection of two balls $B_E(x_1, r_1)$ and $B_E(x_2, r_2)$ is non-empty provided that $d(x_1, x_2) \le r_1 \cdot \bar{r}_2$. We say that $E$ is hyperconvex if the intersection of every family of balls $(B_E(x_i, r_i))_{i \in I}$ is non-empty whenever $d(x_i, x_j) \le r_i \cdot \bar{r}_j$ for all $i, j \in I$. For an example, $(\mathcal{H}, d_{\mathcal{H}})$ is a hyperconvex $\mathcal{H}$-metric space and every $\mathcal{H}$-metric space embeds isometrically into a power of $(\mathcal{H}, d_{\mathcal{H}})$ [23]. This is due to the fact that for every $\mathcal{H}$-metric space $(E, d)$ and for all $x, y \in E$ the following equality holds:

$$d(x, y) = \bigvee_{z \in E} d_{\mathcal{H}}(d(z, x), d(z, y)).$$

The space $E$ is a retract of $E'$, in symbols $E \triangleleft E'$, if there are two contractions $f: E \to E'$ and $g: E' \to E$ such that $g \circ f = id_E$ (where $id_E$ is the identity map on $E$). In this case, $f$ is a coretraction and $g$ a retraction. If $E$ is a subspace of $E'$, then clearly $E$ is a retract of $E'$ if there is a contraction from $E'$ to $E$ such $g(x) = x$ for all $x \in E$. We can easily see that every coretraction is an isometry. A metric space is an absolute retract if it is a retract of every isometric extension. The space $E$ is said to be injective if for all $\mathcal{H}$-metric spaces $E'$ and $E''$, each contraction $f: E' \to E$ and every isometry $g: E' \to E''$ there is a contraction $h: E'' \to E$ such that $h \circ g = f$. We recall that for a metric space over a Heyting algebra $\mathcal{H}$, the notions of absolute retract, injective, hyperconvex and retract of a power of $(\mathcal{H}, d_{\mathcal{H}})$ coincide [23].

## 2.2. Injective envelope

A contraction $f: E \to E'$ is essential if for every contraction $g: E' \to E''$, the map $g \circ f$ is an isometry if and only if $g$ is isometry (note that, in particular, $f$ is an isometry). An essential contraction $f$ from $E$ into an injective $\mathcal{H}$-metric space $E'$ is called an injective envelope of $E$. We will rather say that $E'$ is an injective envelope of $E$. We can view an injective envelope of a metric space $E$ as a minimal injective $\mathcal{H}$-metric space containing (isometrically) $E$. Two injective envelopes of $E$ are isomorphic via an isomorphism which is the identity over $E$. This allows to talk about "the" injective envelope of $E$; we will denote it by $\mathcal{N}(E)$. A particular injective envelope of $E$ will be called a representation of $\mathcal{N}(E)$. The construction of injective envelope is based upon the notion of minimal metric form. A weak metric form is every map $f: E \to \mathcal{H}$ satisfying $d(x, y) \le f(x) \cdot f(y)$ for all $x, y \in E$. This is a metric form if in addition $f(x) \le d(x, y) \cdot f(y)$ for all $x, y \in E$. Equivalently, $f$ is a metric form if and only if $d_{\mathcal{H}}(d(x, y), f(x)) \le f(y)$ for all $x, y \in E$. Alternatively, $f$ is a metric form if there is some isometric extension $E'$ of $E$ and $u \in E'$ such that $f(x) = d(x, f(u))$ for every $x \in E$ (see [29], Lem. 1.2 p. 156). A (weak) metric form is minimal if there is no other (weak) metric form $g$ satisfying $g \le f$ (that is $g(x) \le f(x)$ for all $x \in E$). Since every weak metric form dominates a metric form, the two notions of minimality coincide. As shown in [23] every $\mathcal{H}$-metric space has an injective envelope; the space of minimal metric forms is a representation of it, (cf. [29], Thm. 2.2).

We give below a new characterization of the injective envelope.

**Theorem 2.1.** Let $(E, d)$ be a metric space over $\mathcal{H}$ and $X \subseteq E$. Then $(E, d)$ is isomorphic to the injective envelope of $(X, d_{\uparrow X})$ iff for every metric space $(E', d')$, $X' \subseteq E'$, every isometry $f: (X, d_{\uparrow X})$ onto $(X', d'_{\uparrow X'})$:
(i) Every contraction map $\bar{f} : (E, d) \to (E', d')$, if any, which extends $f$ is an isometric embedding of $(E, d)$ into $(E', d')$;

(ii) The isometry $f^{-1}$ extends to a contraction map from $(E', d')$ into $(E, d)$.

*Proof.* Suppose that $(E, d)$ is isomorphic to the injective envelope of $(X, d_{\uparrow X})$. Since $(E, d)$ is injective, the isometry $f^{-1}$ extends to a contraction map from $(E', d')$ into $(E, d)$. This proves that (ii) holds. The proof that (i) holds relies on the properties of metric forms. To prove that $f$ is an isometry embedding amounts to prove the equality:

$$d'(f(x), f(y)) = d(x, y) \tag{2.1}$$

for all $x, y \in E$. Set $X'' := f(X)$. For every $x \in E$, let $h_x : X \to \mathcal{H}$ and $g_x : X \to \mathcal{H}$ be the maps defined by setting $h_x(z) = d(z, x)$ and $g_x(z) = d'(f(z), f(x))$ for $z \in X$. Since $E$ is the injective envelope of $X$, $h_x$ is a minimal metric form; since $f$ is a contraction and induces an isometry from $X$ onto $X''$, the map $g_x$ is a metric form below $h_x$, hence $h_x = g_x$. It follows that

$$d(z, x) = d(f(z), f(x)) \tag{2.2}$$

for every $z \in X$.

Let $x, y \in E$. By construction of the injective envelope, its elements identify to minimal metric forms over $X$, hence $x$ and $y$ identify respectively to $h_x$ and $h_y$ and

$$d(x, y) = d_{\mathcal{H}}(h_x, h_y) := \sup\{d_{\mathcal{H}}(d(z, x), d(z, y)) : z \in X\}. \tag{2.3}$$

Set $\alpha := d'(f(x), f(y))$. Let $z \in E$. By definition, $d_{\mathcal{H}}(d'(f(z), f(x)), d'(f(z), f(y))) = \min D(d'(f(z), f(x)), d'(f(z), f(y)))$ where $D(d'(f(z), f(x)), d'(f(z), f(y))) = \{r \in \mathcal{H} : d'(f(z), f(x)) \le d'(f(z), f(y)) \cdot \bar{r} \text{ and } d'(f(z), f(y)) \le d'(f(z), f(x)) \cdot r\}$. From the triangular inequality, we have $d'(f(z), f(y)) \le d'(f(z), f(x)) \cdot \alpha$ and $d'(f(z), f(x)) \le d'(f(z), f(y)) \cdot \bar{\alpha}$. Hence, $\alpha \in D(d'(f(z), f(x)), d'(f(z), f(y)))$. The inequality

$$d_{\mathcal{H}}(d'(f(z), f(x)), d'(f(z), f(y))) \le \alpha$$

follows. Consequently,

$$\sup\{d_{\mathcal{H}}(d'(f(z), f(x)), d'(f(z), f(y))) : z \in E\} \le \alpha.$$

With Equalities (2.2) and (2.3) we get: $d(x, y) = \sup\{d_{\mathcal{H}}(d(z, x), d(z, y)) : z \in E\} \le \alpha$. Since $f$ is a contraction, we have $\alpha \le d(x, y)$. Thus $d(x, y) = \alpha$ that is Equality (2.1) holds.

Conversely, suppose that (i) and (ii) hold. Let $(E', d')$ be the injective envelope of $(X, d_{\uparrow X})$ and $f$ be the identity map from $(X, d_{\uparrow X})$ onto itself. Applying (ii), the map $f^{-1}$ extends to a contraction map $g$ from $(E', d')$ into $(E, d)$. Since $(E', d')$ is injective, the map $f$ extends to a contraction map $\bar{f}$ from $(E, d)$ into $(E', d')$. The map $f \circ g$ is a contraction and is the identity on $X$. Since $(E', d')$ is the injective envelope of $(X, d_{\uparrow X})$, $f \circ g$ is the identity on $E'$ (note that elements of $E'$ identify to minimal metric forms over $X$), hence $g$ is injective and $f$ is surjective. Now by (i), $f$ is an isometry on its image. Hence $f$ is an isometry of $(E, d)$ onto $(E', d')$. Thus $(E, d)$ is the injective envelope of $(X, d_{\uparrow X})$ as claimed. $\square$

## 2.3. Injective envelope of two-element metric spaces

Up to Theorem 2.7, we include the few facts we need about injective envelopes of two-element metric spaces (see [29] for proofs).

Let $\mathcal{H}$ be a Heyting algebra and $v \in \mathcal{H}$. Let $E := \{x, y\}$ be a two-element $\mathcal{H}$-metric space such that $d(x, y) = v$. We denote by $\mathcal{N}_v$ the injective envelope of $E$. We give three representations of it. For the first one, we consider
the set of minimal metric forms over E. That is, in this case, the set of minimal pairs $h := (h_x, h_y) \in \mathcal{H}^2$ such that $h_x \cdot \bar{h}_y \ge v$, the set $\mathcal{H}^2$ being equipped with the product ordering. Each element $z \in N_v$ identifies to the pair $(d_{\mathcal{N}_v}(x, z), d_{\mathcal{N}_v}(y, z))$; in particular, $x$ and $y$ identify to $(1, \bar{v})$ and to $(v, 1)$ respectively. We equip $\mathcal{H}^2$ with the supremum distance:

$$d_{\mathcal{H}^2}((u_1, u_2), (u'_1, u'_2)) := d_{\mathcal{H}}(u_1, u'_1) \vee d_{\mathcal{H}}(u_2, u'_2).$$

With the induced distance, $\mathcal{N}_v$ becomes a metric space. If $(h_x, h_y)$ and $(h'_x, h'_y)$ are two elements of $\mathcal{N}_v$, their distance is $d_{\mathcal{H}}(h_x, h'_x) \vee d_{\mathcal{H}}(h_y, h'_y)$. In fact,

$$d_{\mathcal{H}}(h_x, h'_x) = d_{\mathcal{H}}(h_y, h'_y). \qquad (2.4)$$

The proof is easy: We prove that if $h_x \le h'_x \cdot \bar{r}$ for some $r \in \mathcal{H}$, then $h'_y \le h_y \cdot r$. This and the corresponding inequality with $y$ replacing $x$ will leads to (2.4). Suppose that $h_x \le h'_x \cdot \bar{r}$. We have $v \le h_x \cdot \bar{h}_y \le h'_x \cdot \bar{r} \cdot \bar{h}_y$ and thus $r \le h'_x \cdot \bar{r} \cdot \bar{h}_y$. Since $v \le h'_x \cdot \bar{h}'_y$, we have $v \le h'_x \cdot (\bar{h}'_y \wedge (\bar{r} \cdot \bar{h}_y))$ by distributivity. Since $(h'_x, h'_y)$ is a minimal metric form above $v$, we have $\bar{h}'_y = \bar{h}'_y \wedge (\bar{r} \cdot \bar{h}_y)$, that is $h'_y \le h_y \cdot r$.

Due to the fact that in a minimal metric form $(h_x, h_y)$ each component determines the other, we may prefer an other presentation of $\mathcal{N}_v$ as a subset of $\mathcal{H}$. Set $S_v := \{[v \cdot \beta^{-1}] : \beta \in \mathcal{H}\}$; equipped with the ordering induced by the ordering over $\mathcal{H}$ this is a complete lattice. A pair $(h_x, h_y)$ belongs to $\mathcal{N}_v$ if and only if $h_x = [v \cdot \bar{h}_y^{-1}]$ and $\bar{h}_y = [h_x^{-1} \cdot v]$. This yields a correspondence between $\mathcal{N}_v$ and $S_v$.

Now, in several instances, e.g. in the case of the sum of two metric spaces (see Sect. 2.4), it is preferable to consider the set $C_v$ of of all pairs $(u_1, u_2) \in \mathcal{H}^2$ such that $v \le u_1 \cdot u_2$. Once equipped with the ordering induced by the product ordering on $\mathcal{H}^2$, we can consider the set $\mathcal{N}'_v$ of its minimal elements. Each minimal element $(u_1, u_2)$ yields the minimal metric form $(u_1, \bar{u}_2)$ (and conversely). The distance over $\mathcal{H}^2$ is different from the previous case. We have to equip $\mathcal{H}^2$ with the product of the distance $d_{\mathcal{H}}$ with the distance $d'_{\mathcal{H}}$ defined on $\mathcal{H}$ by $d'_{\mathcal{H}}(u_2, u'_2) := d_{\mathcal{H}}(\bar{u}_2, \bar{u}'_2)$.

We list some basic facts about injective envelopes.

**Lemma 2.2.** ([29], Lem. 2.3, Prop. 2.7) The space $\mathcal{N}_v$ equipped with the supremum distance and the set $S_v$ equipped with the distance induced by the distance over $\mathcal{H}$ are injective envelopes of the two-element metric spaces $\{(1, v), (v, 1)\}$ and $\{1, v\}$ respectively. These spaces are isometric to the injective envelope of $E := \{x, y\}$.

**Theorem 2.3.** ([29], Thm. 2.9) Let $E$ be a $\mathcal{H}$-metric space. If $E$ is the injective envelope of a two-element set then $E$ contains no proper isometric subspace.

**Proposition 2.4.** ([29], Cor. 3.3) The following properties are equivalent:

(i) The injective envelope of any finite metric space is finite;

(ii) The injective envelope of any two-element metric space is finite.

**Definition 2.5.** A metric space is linearly orderable if there is a linear ordering $\le$ on $E$ such that $d(x, z) \le d(x, y)$ and $d(z, y) \le d(x, y)$ for all $x, y, z \in E$ with $x \le z \le y$.

**Proposition 2.6.** ([29], Fact 5) Let $u \in \mathcal{H}$. The space $S_u$ is linearly orderable if and only if the ordering is induced by the order on $\mathcal{H}$ or by its reverse.

We say that a metric space is *finitely indecomposable* if for every finite family $(E_i)_{i \in I}$ of metric spaces, $E \triangleleft \prod_{i \in I} E_i$ implies $E \triangleleft E_i$ for some $i \in I$. This notion was used by E. Corominas for posets [8].

**Theorem 2.7.** ([29], Thm. 3.8) Let $E$ be a finite absolute retract. The following properties are equivalent:

(i) $E$ is finitely indecomposable;
(ii) *E* is the injective envelope of a two-element metric space {x, y} such that the distance *d*(x, y) is join-irreducible in *H*.

**2.4. Sum of metric spaces**

Let $(E_1, d_1)$ and $(E_2, d_2)$ be two disjoint $\mathcal{H}$-metric spaces and let $x_1 \in E_1, x_2 \in E_2$. If we endow the set $\{x_1, x_2\}$ with a $\mathcal{H}$-distance $d'$, then we can define a $\mathcal{H}$-distance $d$ on $E := E_1 \cup E_2$ as follows:

- If $x, y \in E_i$ with $i \in \{1, 2\}$ then $d(x, y) = d_i(x, y)$;

- If $x \in E_i$, $y \in E_j$ with $i, j \in \{1, 2\}$ and $i \neq j$, then $d(x, y) = d_i(x, x_i) \cdot d'(x_i, x_j) \cdot d_j(x_j, y)$. In particular, we can identify $x_1$ and $x_2$ which amounts to set $d'(x_1, x_2) = 0$ in the above formula.

If $E_1$ and $E_2$ are not disjoint, we replace it by two disjoint copies $E'_1, E'_2$ (eg $E'_i := E_i \times \{i\}$). Identifying the corresponding elements $x'_1, x'_2$, we obtain a $\mathcal{H}$-metric space that we denote $(E_1, d_1) \cdot (E_2, d_2)$. Alternatively, we may suppose that $E_1$ and $E_2$ have only one element in common, say $z_{1,2}$, and we define the distance $d$ on $E_1 \cup E_2$ by setting $d(x, y) := d_i(x, z_{1,2}) \cdot d_j(z_{1,2}, y)$ if $x \in E_i$, $y \in E_j$, $i \neq j$, and $d(x, y) := d_i(x, y)$ if $x, y \in E_i$.

We consider now objects consisting of a $\mathcal{H}$-metric space and two distinguished elements. Given two such objects, say $\underline{E}_1 := ((E_1, d_1), x_1, y_1)$ and $\underline{E}_2 := ((E_2, d_2), x_2, y_2)$, set $\underline{E}_1 \cdot \underline{E}_2 := ((E, d), x, y)$ where $(E, d)$ is the space obtained by taking disjoint copies $(E'_1, d'_1)$ and $(E'_2, d'_2)$ of $(E_1, d_1)$ and $(E_2, d_2)$, respectively, and by identifying the corresponding elements $y'_1$ and $x'_2$ and setting $x := x'_1$ and $y := y'_2$.

**Definition 2.8.** Let $\mathcal{H}$ be Heyting. A pair $(v_1, v_2) \in \mathcal{H}^2$ is summable if $S_{v_1 \cdot v_2}$ is isomorphic to $S_{v_1} \cdot S_{v_1}$.

**Definition 2.9.** Let $\mathcal{H}'$ be an initial segment of $\mathcal{H}$ which is also a submonoid. We say that $\mathcal{H}'$ has the decomposition property if every pair $(v_1, v_2) \in \mathcal{H}' \times \mathcal{H}'$ is summable.

**2.5. Examples**

Several examples of metric spaces over a Heyting algebra are given in [23]. We briefly examine some of these examples w.r.t. to their injective envelopes and the sum operation. Ordinary metric spaces enter in this frame. Add a largest element $+\infty$ to the set $\mathbb{R}^+$ of non-negative reals, extend the $+$ operation in the natural way, take the identity for the involution. Then $\mathbb{R}^+ \cup \{+\infty\}$ becomes a Heyting algebra and the metric spaces over it are just direct sums of ordinary metric spaces. The injective envelope of such a space is the direct sum of the injective envelope of its factors. The injective envelope of a two-element metric spaces $E := \{x, y\}$ with $r := d(x, y)$ is isometric to the segment $[0, r]$ si $r < +\infty$ and to $E$ if $r = +\infty$. Trivially, $\mathbb{R}^+$ has the decomposition property. The sum of two convex (resp. injective) metric spaces with a common vertex is convex (resp. injective). The reader will find in [12] a description of injective envelopes of finite ordinary metric spaces and interesting combinatorial properties as well (see also [13]).

Now, let $\mathcal{H} := \{a, b, 0, 1\}$ ordered by $0 < a, b < 1$ and $a$ incomparable to $b$. The operation is the join, the involution exchange $a$ and $b$. Metric spaces over $\mathcal{H}$ correspond to ordered sets. As shown by Banaschewski and Bruns, every poset $P$ has an injective envelope, namely its MacNeille completion [2]. Hence, if $P$ has two elements, its injective envelope is $P$ whenever these two elements are comparable, otherwise this is $P$ augmented of a smallest and a largest element. Convexity property does not hold for $\mathcal{H}$, hence the sum of two injective with a common element does not need to be injective.

Next, suppose that $\mathcal{H}$ is a complete meet-distributive lattice, the operation is the join and the involution is the identity. For example, if $\mathcal{H} := \mathbb{R} \cup \{+\infty\}$, metric spaces over $\mathcal{H}$ are direct sums of ultrametric spaces. Metric spaces over Boolean algebras have been introduced by Blumenthal [3]. Let $B$ be a Boolean algebra, let the operation be the supremum and the involution be the identity. Although $B$ is not necessary complete, residuation allows to define a distance on $B$ setting $d_B(p, q) := p\Delta q$ where $\Delta$ denotes the symmetric difference. From this follows that the interval $[0, u] := \{v \in B: 0 \le v \le u\}$ with the distance induced by $d_B$ is the injective envelope of every pair $\{p, q\}$ of vertices of $B$ such that $p \wedge q = 0$ and $p \vee q = u$. Hence if $B$ is finite, the number of elements of the injective envelope of a 2-element metric space is a power of 2 hence the decomposition property does not hold. In Section 3, we give an example for which this decomposition property holds, namely the algebra
F° (A*) (for more examples of generalisations of metric spaces, see [4] Chapter XV (e.g., p. 331, Sect. 131), [5] Part 1 Lattice theory, [34] and the encyclopedia of distances [10].

### 3. THE HEYTING ALGEBRA $\mathbf{F}(A^*)$

Let $A$ be a set. Considering $A$ as an *alphabet* whose members are *letters*, we write a word $\alpha$ with a mere juxtaposition of its letters as $\alpha = a_0a_1...a_{n-1}$ where $a_i$ are letters from $A$ for $0 \le i \le i-1$. The integer $n$ is the length of the word $\alpha$ and we denote it $|\alpha|$. Hence we identify letters with words of length 1. We denote by $\square$ the empty word, which is the unique word of length zero. The *concatenation* of two word $\alpha := a_0 \cdots a_{n-1}$ and $\beta := b_0 \cdots b_{m-1}$ is the word $\alpha\beta := a_0 \cdots a_{n-1}b_0 \cdots b_{m-1}$. We denote by $A^*$ the set of all words on the alphabet $A$. Once equipped with the concatenation of words, $A^*$ is a monoid, whose neutral element is the empty word, in fact $A^*$ is the *free monoid* on $A$. A *language* is any subset $X$ of $A^*$. We denote by $\mathcal{P}(A^*)$ the set of languages. We will use capital letters for languages. If $X, Y \in \mathcal{P}(A^*)$ we may set $XY := \{\alpha\beta : \alpha \in X, \beta \in Y\}$ (and use $Xy$ and $xY$ instead of $X\{y\}$ and $\{x\}Y$). Sometimes, we denote $\alpha \cdot \beta$, resp., $X \cdot Y$, the concatenation of two words, resp., two sets of words. The operation on subsets extends the concatenation operation on $A^*$. With it, the set $\mathcal{P}(A^*)$ is a monoid (the set $\{\square\}$ is the neutral element). Ordered by inclusion, this is a (join) lattice ordered monoid. Indeed, concatenation distributes over arbitrary union, namely:

$$ (\bigcup_{i \in I} X_i)Y = \bigcup_{i \in I} X_iY. $$

This monoid is residuated. Let $X, Y, Z \in \mathcal{P}(A^*)$. As it is customary, we set $X^{-1}Z := \{y \in A^* : Xy \subseteq Z\}$ and $ZY^{-1} := \{x \in A^* : xY \subseteq Z\}$. We recall that

$$ X(X^{-1}Z) \subseteq Z \text{ and } (ZY^{-1})Y \subseteq Z. \qquad (3.1) $$

Let $L$ be a subset of $A^*$. Set $\rho_L := \{(x, y) \in A^* \times A^* : xy \in L\}$. Then $R := (A^*, \rho_L, A^*)$ is an incidence structure and, with the notation above, $R(x) = x^{-1}L$ and $R^{-1}(y) = Ly^{-1}$. Thus, Gal$(R)$, the Galois lattice of $R$, is the set $\{LY^{-1} : Y \subseteq A^*\}$ ordered by inclusion. This is a complete lattice. The meet is the intersection, the largest element is $A^*$.

In the sequel, we study the metric structure of Gal$(R)$ when $L$ is a final segment $F$ of the monoid $A^*$, this monoid being equipped with the Higman ordering. We suppose from now that the alphabet $A$ is ordered and equipped with an involution $\overline{\cdot}$ preserving the order. The involution extends to $A^*$: we set for every $\alpha := a_0 \cdots a_{n-1}, \overline{\alpha} := \overline{a_{n-1}} \cdots \overline{a_0}$. Note that $\alpha\beta = \overline{\beta\alpha}$ for all $\alpha, \beta \in A^*$. We order $A^*$ with the Higman ordering. Then $A^*$ becomes an ordered monoid with respect to the concatenation of words. Let $\mathbf{F}(A^*)$ be the collection of final segments of $A^*$ (that is $X \in \mathbf{F}(A^*)$ if $X \subseteq A^*$ and $\alpha \le \beta, \alpha \in X$ implies $\beta \in X$). The set $\mathbf{F}(A^*)$ is stable w.r.t. the concatenation of languages: if $X, Y \in \mathbf{F}(A^*)$, then $XY \in \mathbf{F}(A^*)$. Clearly, the neutral element is $A^*$. The set $\mathbf{F}(A^*)$ ordered by inclusion is a complete lattice (the join is the union, the meet is the intersection). Concatenation distributes over union. Order $\mathbf{F}(A^*)$ by reverse of the inclusion, denote $X \le Y$ instead of $X \supseteq Y$, extend the involution $\overline{\cdot}$ to $\mathbf{F}(A^*)$, set $\overline{X} := \{\overline{\alpha} : \alpha \in X\}$, denote by $X \cdot Y$ the concatenation $XY$ and set $1 := A^*$ then:

**Proposition 3.1.** *The structure $\mathbf{F}(A^*) := (\mathbf{F}(A^*), \le, \cdot, 1, \overline{\cdot})$ is a Heyting algebra.*

We may then define metric spaces over $\mathbf{F}(A^*)$ and study injective objects and particularly injective envelopes.

N.B. As suggested by a referee, instead of the concatenation of languages one could consider their shuffle (it turns out that shuffle and Higman ordering were two of the ingredients of [39]) but it can be premature to say more.

According to Corollary 4.9 page 177 of [29] we have:
**Theorem 3.2.** Let $F, F_1, F_2$ be final segment of $A^*$ such that $F = F_1 \cdot F_2$. If $F \neq \emptyset$ then

$$F = F_1 \cdot F_2 \iff S_F \cong S_{F_1} \cdot S_{F_2}$$

According to Definition 2.9, this means that $\mathbf{F}^\circ(A^*) := \mathbf{F}(A^*) \setminus \{\emptyset\}$ has the decomposition property.

Among metric spaces over $\mathbf{F}(A^*)$ are those coming from reflexive and involutive transition systems. They are introduced in the next section.

## 4. TRANSITION SYSTEMS AS METRIC SPACES

Let $A$ be a set. A transition system on the alphabet $A$ is a pair $M := (Q, T)$ where $T \subseteq Q \times A \times Q$. The elements of $Q$ are called states and those of $T$ transitions. Let $M := (Q, T)$ and $M' := (Q', T')$ be two transition systems on the alphabet $A$. A map $f: Q \to Q'$ is a morphism of transition systems if for every transition $(p, a, q) \in T$, we have $(f(p), a, f(q)) \in T'$. When $f$ is bijective and $f^{-1}$ is a morphism from $M'$ to $M$, we say that $f$ is an isomorphism. The collection of transition systems over $A$, equipped with these morphisms, form a category. This category has products. If $(M_i)_{i \in I}$ is a family of transition systems, $M_i := (Q_i, T_i)$, then their product $M$ is the transition system $(Q, T)$ where $Q$ is the direct product $\prod_{i \in I} Q_i$ and $T$ is defined as follows: if $x := (x_i)_{i \in I}$ and $y := (y_i)_{i \in I}$ are two elements of $Q$ and $a$ is a letter, then $(x, a, y) \in T$ if and only if $(x_i, a, y_i) \in T$ for every $i \in I$.

An automaton $\mathcal{A}$ on the alphabet $A$ is given by a transition system $M := (Q, T)$ and two subsets $I, F$ of $Q$ called the set of initial and final states. We denote the automaton as a triple $(M, I, F)$. A path in the automaton $\mathcal{A} := (M, I, F)$ is a sequence $c := (e_i)_{i \in n}$ of consecutive transitions, that is of transitions $e_i := (q_i, a_i, q_{i-1})$. The word $\alpha := a_0 \cdots a_{n-1}$ is the label of the path, the state $q_0$ is its origin and the state $q_n$ its end. One agrees to define for each state $q$ in $Q$ a unique null path of length 0 with origin and end $q$. Its label is the empty word $\square$. A path is successful if its origin is in $I$ and its end is in $F$. Finally, a word $\alpha$ on the alphabet $A$ is accepted by the automaton $\mathcal{A}$ if it is the label of some successful path. The language accepted by the automaton $\mathcal{A}$, denoted by $L_{\mathcal{A}}$, is the set of all words accepted by $\mathcal{A}$. Let $\mathcal{A} := (M, I, F)$ and $\mathcal{A}' := (M', I', F')$ be two automata. A morphism from $\mathcal{A}$ to $\mathcal{A}'$ is a map $f: Q \to Q'$ satisfying the two conditions:

1. $f$ is morphism from $M$ to $M'$;

2. $f(I) \subseteq I'$ and $f(F) \subseteq F'$.

If, moreover, $f$ is bijective, $f(I) = I'$, $f(F) = F'$ and $f^{-1}$ is also a morphism from $\mathcal{A}'$ to $\mathcal{A}$, we say that $f$ is an isomorphism and that the two automata $\mathcal{A}$ and $\mathcal{A}'$ are isomorphic.

To a metric space $(E, d)$ over $\mathcal{F}(A^*)$, we may associate the transition system $M := (E, T)$ having $E$ as set of states and $T := \{(x, a, y) : a \in d(x, y) \cap A\}$ as set of transitions. Notice that such a transition system has the following properties: for all $x, y \in E$ and every $a, b \in A$ with $b \ge a$:

1) $(x, a, x) \in T$;

2) $(x, a, y) \in T$ implies $(y, \bar{a}, x) \in T$;

3) $(x, a, y) \in T$ implies $(x, b, y) \in T$.

We say that a transition system satisfying these properties is reflexive and involutive (cf. [29, 42]). Clearly if $M := (Q, T)$ is such a transition system, the map $d_M: Q \times Q \to \mathcal{F}(A^*)$ where $d_M(x, y)$ is the language accepted by the automaton $(M, \{x\}, \{y\})$ is a distance. We have the following:

**Lemma 4.1.** Let $(E, d)$ be a metric space over $\mathcal{F}(A^*)$. The following properties are equivalent:

(i) The map $d$ is of the form $d_M$ for some reflexive and involutive transition system $M := (E, T)$;

(ii) For all $\alpha, \beta \in A^*$ and $x, y \in E$, if $\alpha \cdot \beta \in d(x, y)$, then there is some $z \in E$ such that $\alpha \in d(x, z)$ and $\beta \in d(z, y)$.

This is Lemma 4.2, page 172 of [29]. Implication (i) ⇒ (ii) is obvious. For the reader's convenience, we recall the proof of implication (ii) ⇒ (i). Let $M := (E, T)$ where $T := \{(x, a, y) : a \in d(x, y) \cap A\}$. We observe
first that $d_M(x, y) \subseteq d(x, y)$ for every $x, y \in E$. This is easy. Let $\alpha \in d_M(x, y)$. By definition, there is a path $c := p_0 a_0 p_1 a_1 \dots a_{n-1} p_n$, such that $p_0 = x, p_n = y, \alpha = a_0 a_1 \dots a_{n-1}$ and $(p_i, a_i, p_{i+1}) \in T$ for each $i$. By definition $a_i \in d(p_i, p_{i+1})$. From the triangular inequality we get $d(x, y) \ge d(p_0, p_1) \dots d(p_{n-1}, p_n)$, hence $\alpha = a_0 \dots a_{n-1} \in d(x, y)$. We prove that the reverse inclusion holds by recurrence on the length of words. Let $\alpha \in d(x, y)$. If $\alpha$ is the empty word, then $x = y$ hence by definition of $d_M$, it belongs to $d_M(x, y)$. If $\alpha$ is a letter, then $x \alpha y \in T$ hence $\alpha \in d_M(x, y)$. If $\alpha := a_0 \dots a_{n-1} \in d(x, y)$ with $n \ge 2$ and $a_i \in A$ for each $i$ then by (ii) applied to $a_1$ and $a_2 \dots a_{n-1}$ there is some $z \in E$ such that $a_0 \in d(x, z)$ and $a_1 \dots a_{n-1} \in d(z, y)$. Via the recurrence hypothesis, $a_0 \in d_M(x, y)$ and $a_1 \dots a_{n-1} \in d_M(z, y)$. By the triangular inequality, $\alpha := a_0 \dots a_{n-1} \in d_M(x, y)$, as required.

The category of reflexive and involutive transition systems with the morphisms defined above identify to a subcategory of the category having as objects the metric spaces and morphisms the contractions. Indeed:

**Fact 1.** Let $M_i := (Q_i, T_i) (i = 1, 2)$ be two reflexive and involutive transition systems. A map $f: Q_1 \to Q_2$ is a morphism from $M_1$ to $M_2$ if only if $f$ is a contraction from $(Q_1, d_{M_1})$ to $(Q_2, d_{M_2})$.

From this fact, we can observe that if $(M_i)_{i \in I}$ is a family of transition systems $M_i := (Q_i, T_i)$ then the metric space $(Q, d)$ associated to the transition system $\prod_{i \in I} M_i$, product of the $M_i$'s, is the product of metric spaces $(Q_i, d_i)$ associated to the transition systems $(Q_i, T_i)$.

Condition (ii) stated in Lemma 4.1 is a weak form of convexity. Since injective objects are hyperconvex, they are convex. Thus, they satisfy this weak form of convexity property. Hence, their distance is the distance associated with a transition system. In particular, if $F$ is a final segment of $A^*$, the distance $d$ on the injective envelope $S_F$ coincide with the distance $d_F$ associated with the transition system $M_F := (S_F, T_F)$ where

$$T_F := \{(p, a, q) : a \in d(p, q) \cap A\}.$$

We denote by $\mathcal{A}_F$ the automaton $(M_F, \{x\}, \{y\})$, where $x := A^*$ and $y := F$.

From the existence of the injective envelope, we get:

**Theorem 4.2.** For every $F \in \mathbf{F}(A^*)$ there is an involutive and reflexive transition system $M := (Q, T)$, an initial state $x$ and a final state $y$ such that the language accepted by the automaton $\mathcal{A} = (M, \{x\}, \{y\})$ is $F$. Moreover, if $A$ is well-quasi-ordered then we may choose $Q$ to be finite.

*Proof.* Take $M := M_F$, $x := A^*$ and $y := F$. If $A$ is well-quasi-ordered then $A^*$ is also well-quasi-ordered (Higman [19]), hence the final segment $F$ has a finite basis, that is, there are finitely many words $\alpha_0, \dots, \alpha_{n-1}$ such that $F = \{\alpha : \alpha_i \le \alpha$ for some $i < n\}$. $\square$

Since the distance of an injective object in the category of metric spaces over $\mathbf{F}(A^*)$ is the distance associated with a transition system, we may reproduce Theorem 2.1 almost verbatim. We get:

**Theorem 4.3.** Let $M := (Q, T)$ be a transition system, $X \subseteq Q$. Then $(M, d_M)$ is isomorphic to the injective envelope of $(X, d_{M \upharpoonright X})$ iff for every reflexive and involutive transition system $M' := (Q', T')$, $X' \subseteq Q'$, every isometry $f: (X, d_{M \upharpoonright X})$ onto $(X', d_{M' \upharpoonright X'})$:

(i) Every contraction map $\bar{f} : (M, d_M) \to (M', d_{M'})$, if any, which extends $f$ is an isometric embedding of $(M, d_M)$ into $(M', d_{M'})$;

(ii) The isometry $f^{-1}$ extends to a contraction map from $(M', d_{M'})$ into $(M, d_M)$.

Taking for $X$ a 2-element subset $\{x, y\}$ of $Q$, Theorem 4.3 translates to Theorem 1.1 stated in the introduction.

## 4.1. Minimal automaton and minmax automata

We suppose now that the alphabet $A$ is finite. We refer to [43], Section 3.3 pages 111-118 for the construction of the minimal state deterministic automaton. If $F \in \mathbf{F}(A^*)$ and $u \in A^*$, the left residual is $u^{-1}F := \{v \in A^* : uv \in F\}$. The minimal automaton $Min_F$ recognizing $F$ has $Q_F := \{u^{-1}F : u \in A^*\}$ as set of states. Its initial state is $x := F$, its final state is $y := A^*$ and the transition function $\delta_F$ associate to the pair $(u^{-1}F, a) \in Q_F \times A$ the state $(ua)^{-1}F$.
One can check that:

**Lemma 4.4.** The map $i : \text{Min}_F \to \mathcal{A}_F$ defined by $i(Y) := \bigcap_{y \in Y} Fy^{-1}$ is a morphism of automata.

*Proof.* Suppose that $(u^{-1}F, a, (ua)^{-1}F)$ is a transition in the automaton $\text{Min}_F$. We prove that $(i(u^{-1}F), a, i((ua)^{-1}F))$ is a transition in the automaton $\mathcal{A}_F$. This is equivalent to $a \in d(i(u^{-1}F), i((ua)^{-1}F))$. The last condition amounts to 1) $i(u^{-1}F)a \subseteq i((ua)^{-1}F)$ and 2) $i((ua)^{-1}F\bar{a} \subseteq i(u^{-1}F)$. For 1), let $v \in i(u^{-1}F)$, we claim that $va \in i((ua)^{-1}F)$, that is for each word $w$, if $uaw \in F$, then $vaw \in F$. Since $v \in i(u^{-1}F)$, from $uaw \in F$, we have $vaw \in F$, as required. The inclusion 2) follows directly from the fact that $F$ is a final segment. The equalities $i(F) = \mathcal{A}^*$ and $i(\mathcal{A}^*) = F$ are obvious. $\square$

In general, the transition system associated to $\text{Min}_F$ is neither reflexive nor involutive. Among all involutive and reflexive transition systems $M := (Q, T)$ with initial state $x$ and final state $y$ such that the language accepted by the automaton $(M, \{x\}, \{y\})$ is $F$, we select those with the least number of states and among those transition systems, we select those with a maximum number of transitions; we call minmax transition systems these transition systems. The automaton corresponding to a minmax transition system is a minmax automaton. In other terms, an automaton $\mathcal{A} := (M, \{x\}, \{y\})$ is minmax if (a) it is reflexive and involutive, (b) for every reflexive and involutive automaton $\mathcal{A}' = (M', \{x'\}, \{y'\})$ such that $d_M(x, y) = d_{M'}(x', y')$, one has $|Q| \le |Q'|$, moreover (c) $|Q| = |Q'|$ implies $|T| \ge |T'|$.

**Proposition 4.5.** Let $M := (Q, T)$ be transition system and $F$ be a final segment of $\mathcal{A}^*$. If $\mathcal{A} := (M, \{x\}, \{y\})$ is a minmax automaton which accepts $F$, then $\mathcal{A}$ is isomorphic to an induced automaton $\mathcal{A}'$ of $\mathcal{A}_F$, that is there is some $Q' \subseteq S_F$ containing $\mathcal{A}^*$ and $F$ such that the automaton $\mathcal{A}' := (M_{F \upharpoonright Q'}, \{\mathcal{A}^*\}, \{F\})$ is isomorphic to $\mathcal{A}$.

*Proof.* To the automaton $\mathcal{A} := (M, \{x\}, \{y\})$, we associate the metric space $(Q, d_M)$ induced by $M$. Identifying $x$ with $\mathcal{A}^*$ and $y$ with $F = d_M(x, y)$, the space $S_F$ identifies with the injective envelope of the 2-element space $\{x, y\}$. Let $i$ be the identity mapping on $\{x, y\}$. This is a partial contraction from $(Q, d_M)$ into $S_F$. Since $S_F$ is injective, this partial map extends to a contraction $f$ defined on $Q$. Since $f$ is a contraction, this map is an automata morphism. Let $Q' := f(Q)$ and consider the transition system $M' := (Q', S_F \upharpoonright Q')$. We have $F = d(x, y) \le d_{M'}(x, y) \le d_M(x, y) = F$. Thus $d_{M'}(x, y) = F$. Since $|Q|$ is minimal, it follows that $|Q| = |Q'|$ proving that $f$ is injective. Now since $|T|$ is maximum, we have $|T_{F \upharpoonright Q'}| = |T|$ proving that $f$ is an automata isomorphism from $\mathcal{A}$ to $\mathcal{A}' := (M', \{x\}, \{y\})$. $\square$

Let $M_1 := (Q_1, T_1)$ and $M_2 := (Q_2, T_2)$ be two transition systems such that $Q_1$ and $Q_2$ have only the element $z$ in common. Let $\mathcal{A}_1 := (M_1, \{x\}, \{z\})$ and $\mathcal{A}_2 := (M_2, \{z\}, \{y\})$ be two automata. We denote $\mathcal{A}_1 \cdot \mathcal{A}_2$ the automaton $(M, \{x\}, \{y\})$ where $M = (Q, T)$ $Q = Q_1 \cup Q_2$ and $T = T_1 \cup T_2$.

**Theorem 4.6.** Let $F$ be a non-empty final segment of $\mathcal{A}^*$. If $F = F_1 \cdot F_2$, with $F_1$ and $F_2$ final segments of $\mathcal{A}^*$, then an automaton $\mathcal{A}$ with initial state $x$ and final state $y$ accepting $F$ is minmax if and only if it decomposes into $\mathcal{A}_1 \cdot \mathcal{A}_2$ where $\mathcal{A}_1$ and $\mathcal{A}_2$ are two minmax automata accepting respectively $F_1$ between $x$ and $z$ and $F_2$ between $z$ and $y$.

*Proof.* From Theorem 3.2, we have $S_{F_1} \cdot S_{F_2} \cong S_{F_1 \cdot F_2}$. According to Proposition 4.5, a minmax automaton $\mathcal{A}$ accepting $F$ is a subautomaton of $\mathcal{A}_F = \mathcal{A}_{F_1} \cdot \mathcal{A}_{F_2}$. Thus $\mathcal{A}$ decomposes into $\mathcal{A}_1 \cdot \mathcal{A}_2$ where $\mathcal{A}_1$ is a subautomaton of $\mathcal{A}_{F_1}$ and $\mathcal{A}_2$ is a subautomaton of $\mathcal{A}_{F_2}$. Since $\mathcal{A}$ is minmax, both $\mathcal{A}_1$ and $\mathcal{A}_2$ are minmax. Conversely, assume that $\mathcal{A}_1$ and $\mathcal{A}_2$ are minmax. Let $\mathcal{A}$ be a minmax automaton accepting $F_1 \cdot F_2$. Then $\mathcal{A}$ decomposes into $\mathcal{A}'_1 \cdot \mathcal{A}'_2$ where $\mathcal{A}'_1$ and $\mathcal{A}'_2$ are minmax. The automaton $\mathcal{A}_1$ and $\mathcal{A}'_1$ (resp. $\mathcal{A}_2$ and $\mathcal{A}'_2$) have the same number of states and transitions. That is $\mathcal{A}_1 \cdot \mathcal{A}_2$ is minmax. $\square$

**Example 4.7.** (Mike Main, 1989, communicated by Maurice Nivat [35]). We give an example of two non-isomorphic minmax automata accepting the same language $L \in F(\mathcal{A}^*)$.

Let $\mathcal{A} = \{a, b, c, a', b', c'\}$ with $\bar{a} = a', \bar{b} = b'$ and $\bar{c} = c'$. Consider the automata represented on Figure 2. To each of these automata, we associate the involutive and reflexive automata obtained by replacing each transition
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Mike Main’s examples.</figcaption></figure>

$(p, \alpha, q)$ by $(p, \alpha, q)$ and $(q, \bar{\alpha}, p)$ and adding a loop at every vertex. The language accepted by each of these automata between $x$ and $y$ is $L = \uparrow \{ab, ac, ba, bc, ca, cb\}$. As it is easy to check, these automata are minmax but not isomorphic.

# 5. A DESCRIPTION OF THE INJECTIVE ENVELOPE

We describe the injective envelope $S_F$ in Galois lattice terms. We derive a test of its finiteness which leads to the notion of Ferrers language.

## 5.1. Incidence structures

We recall first some basic facts about incidence structures, Galois lattices and Ferrers relations. We follow the exposition given in [40].

An incidence structure $R$ is a triple $(V, \rho, W)$ where $\rho$ is a subset of the product $V \times W$. We set $\rho^{-1} := \{(x, y) : (y, x) \in \rho\}$ and $R^{-1} := (W, \rho^{-1}, V)$, that we call the dual of $R$. We denote by $\neg \rho$ the relation $V \times W \setminus \rho$ and $\neg R$ the resulting incidence structure.

A subset of $V \times W$ of the form $X \times Y$ is a rectangle. Let $(X, Y) \in \wp(V) \times \wp(W)$. We set $R_{\wedge}(X) := \{y \in W : xpy$ for all $x \in X\}$, $R_{\wedge}^{-1}(Y) := \{x \in V : xpy$ for all $y \in Y\}$. We recall that the set $X \times Y$ is a maximal rectangle included into $\rho$ if and only if $X = R_{\wedge}^{-1}(Y)$ and $Y = R_{\wedge}(X)$. The Galois lattice Gal$(R)$ of $R$ is the collection, ordered by inclusion, of subsets of $V$ of the form $R_{\wedge}^{-1}(Y)$ for $Y \in \wp(W)$. This is a complete lattice; the largest element is $V (= R_{\wedge}^{-1}(\emptyset))$. Then, Gal$(R^{-1})$ is the collection, ordered by inclusion, of subsets of $W$ of the form $R_{\wedge}(X)$ for $X \in \wp(V)$. We recall the important fact that Gal$(R)$ and Gal$(R^{-1})$ are dually isomorphic. Since Gal$(R)$ consists of intersections of sets of the form $R^{-1}(y)$ for $y \in W$, Gal$(R)$ is finite if and only if the set of $R^{-1}(y)$ for $y \in W$ is finite; since Gal$(R)$ is dually isomorphic to Gal$(R^{-1})$, it is finite if and only if the set of $R(x)$ for $x \in V$ is finite.

We give two examples from the theory of ordered sets.

**Fact 2.** If $R := (P, \leq, P)$ is an ordered set, then $P$ identifies to the subset $\text{down}(P) := \{\downarrow x : x \in P\}$ of principal initial segments of $P$; the Galois lattice Gal$(R)$, is the *MacNeille completion of P*, a complete lattice containing $P$ in which every member is a join and a meet of elements of $P$. And Gal$(\neg R)$ is the set of final segments of $P$ ordered by inclusion.

Now, we mention the facts we need.

Let $R := (V, \rho, W)$ and $R' := (V', \rho', W')$ be two incidence structures. According to Bouchet [6], a coding from $R$ into $R'$ is a pair of maps $f: V \to V'$, $g: W \to W'$ such that

$$xpy \iff f(x) \rho'g(y).$$
Bouchet's Coding Theorem [6] below is a striking illustration of the links between coding and embedding.

**Theorem 5.1.** Let $(T, \leq)$ be a complete lattice and $R$ be an incidence structure. Then $R$ has a coding into $(T, \leq, T)$ if and only if $\text{Gal}(R)$ is embeddable in $T$.

The basic facts about coding we need are the following:

**Fact 3.** Let $(f, g)$ be a coding from $R$ into $R'$.

(a) $(f, g)$ is a coding from $\neg R$ to $\neg R'$;

(b) $\text{Gal}(R)$ is embeddable into $\text{Gal}(R')$;

(c) If $f$ is surjective, then $\text{Gal}(R)$ identifies with an intersection closed subset of $\text{Gal}(R')$.

*Proof.* (a) Immediate consequence of the definition.

(b) Follows from Bouchet's Theorem.

(c) The map $X \to X' = R_\wedge^{-1}(R'_\wedge(X))$ is an embedding from $\text{Gal}(R)$ into $\text{Gal}(R')$ which preserves non-empty intersections. If $f$ is surjective, then the least element of the Galois lattice is preserved, hence $\text{Gal}(R)$ identifies with an intersection closed subset of $\text{Gal}(R')$. $\square$

**Fact 4.** Let $(f_i, g_i)_i$ be a family of codings from $(V, \rho_i, W)$ into $(V_i, \theta_i, W_i)$. Then, the pair $(\Pi_i f_i, \Pi_i g_i)$ is a coding from $(V, \cup_i \rho_i, W)$ into $(\Pi_i V_i, \neg \Pi_i \neg \theta_i, \Pi_i W_i)$.

*Proof.* Clearly $(\Pi_i f_i, \Pi_i g_i)$ is a coding from $(V, \cap_i \rho_i, W)$ into $(\Pi_i V_i, \Pi_i \theta_i, \Pi_i W_i)$. Indeed, if $x := (x_i)_i$ and $y := (y_i)_i$, then $x \Pi_i \theta_i y$ means $x_i \theta_i y_i$ for all $i$. From Fact 3 (a) we get that $(\Pi_i f_i, \Pi_i g_i)$ is a coding from $(V, \cup_i \rho_i, W)$ into $(\Pi_i V_i, \neg \Pi_i \neg \theta_i, \Pi_i W_i)$. $\square$

**Corollary 5.2.** If for every $i$, $V_i = W_i$ and $\theta_i$ is of the form $\neg \leq_i$ for some ordering $\leq_i$ on $V_i$, then there is a coding from $(V, \cup_i \rho_i, W)$ into $(\Pi_i V_i, \neg \leq, \Pi_i V_i)$ where $\leq$ is the product ordering on $\Pi_i V_i$.

**Fact 5.** Let $R := (V, \rho, W)$ be an incidence structure. Then $\text{Gal}(R)$ is finite if and only if $\text{Gal}(\neg R)$ is finite.

*Proof.* For each $y \in V$, $(\neg R)^{-1}(y) = V \setminus R^{-1}(y)$. Since $\text{Gal}(R)$ is made of intersections of sets of the form $R^{-1}(y)$, if $\text{Gal}(R)$ is finite, the collection of such sets is finite, hence the collection of sets of the form $(\neg R)^{-1}(y)$ is finite too. Since $\text{Gal}(\neg R)$ is made of intersections of these sets, it is finite. $\square$

**Fact 6.** Let $R_i := (V_i, \rho_i, W_i)$ be a family of incidence structures. Then $\text{Gal}(\Pi_i R_i)$ embeds into $\Pi_i \text{Gal}(R_i)$.

*Proof.* Let $y := (y_i)_i \in \Pi_i W_i$. We have $(\Pi_i R_i)^{-1}(y) = \Pi_i R_i^{-1}(y_i)$. Hence, if $p_j : \Pi_i V_i \to V_j$ denotes the $j$th projection, then for each $X \in \text{Gal}(\Pi_i R_i)$, we have $(p_i(X))_i \in \Pi_i \text{Gal}(R_i)$. This defines an embedding, proving our claim. If each member $X$ of $\text{Gal}(\Pi_i R_i)$ is non-empty, then this embedding is an isomorphism. $\square$

**Fact 7.** Suppose $V_i = V, W_i = W$ for each $i \in I$ and $I$ finite. If $\text{Gal}(R_i)$ is finite for each $i \in I$, then $\text{Gal}((V, \cup_i \rho_i, W))$ is finite.

*Proof.* According to Fact 5, this amounts to prove that $\text{Gal}((V, \cap_i \neg \rho_i, W))$ is finite. Fact 4 yields that $(V, \cup \rho_i, W)$ has a coding into $(V^V, \neg \Pi_i \neg \rho_i, W^W)$. According to (a) of Fact 3, $(V, \cap \neg \rho_i, W)$ has a coding into $(V^V, \Pi_i \neg \rho_i, W^W) \equiv \Pi_i (V, \neg \rho_i, W)$. According to (b) of Fact 3, $\text{Gal}((V, \cap_i \neg \rho_i, W))$ embeds into $\text{Gal}(\Pi_i (V, \neg \rho_i, W))$, which in turns embeds into $\Pi_i \text{Gal}(V, \neg \rho_i, W)$ from Fact 6. From Fact 5, each $\text{Gal}(V, \neg \rho_i, W)$ is finite. The result follows. $\square$

## 5.2. Languages and their Galois lattices

Galois lattices arose from group theory and geometry. We show here how they interact with language theory. We represent subsets of the free monoid by incidence structures as follows.
Let A be an alphabet and L be a subset of A*. Denoting by xy the concatenation of the words x, y ∈ A*, define a binary relation ρ_L on A* by:

$$x\rho_L y \iff xy \in L$$

and set $R_L := (A^*, \rho_L, A^*)$.

We mention without proof some properties of this association.

It preserves Boolean operations, that is:

**Fact 8.**

(1) $\rho_{A^* \setminus L} = A^* \times A^* \setminus \rho_L$. Hence, $R_{A^* \setminus L} = \neg R_L$.

(2) $\rho_{\cup_i L_i} = \cup_i \rho_{L_i}$ and $\rho_{\cap_i L_i} = \cap_i \rho_{L_i}$

Not every binary relation $\rho$ on $A^*$ can be of the form $\rho_L$. For an example, if $\rho$ contains a pair $(u, v)$ with $u, v \in A^*$, then $\rho$ contains $\rho_{\{w\}}$ where $w := uv$. In fact, if $\rho$ is a binary relation on $A^*$, set $\pi_\rho := \{uv : (u, v) \in \rho\}$; then $\rho_{\pi_\rho}$ is the least binary relation of the form $\rho_L$ containing $\rho$. In particular, $\rho_{\{w\}}$ is the least relation of the form $\rho_L$ containing a pair $(u, v)$ such that $w = uv$.

In the Boolean lattice made of relations of the form $\rho_L$, the atoms are of the form $\rho_{\{w\}}$ where $w$ is any word in $A^*$. They form a partition of $A^* \times A^*$. Every binary relation of the form $\rho_L$ is an union of some blocks of this partition.

We will say more about this association in Section 6.

We conclude this subsection by the following property.

If B is a subset of $A^*$, we set $R_L \upharpoonright B := (B, \rho_L \cap B \times B, B)$.

**Fact 9.** The Galois lattices of $R_L$ and $R_L \upharpoonright A^* \setminus L$ are isomorphic provided that $L$ is a final segment of $A^*$.

*Proof.* Observe that for every subset $X$ of $A^*$, we have: $R_\wedge^{-1}(R_\wedge(X)) = R_\wedge^{-1}(R_\wedge(X \setminus L))$. $\square$

**5.3. Proof of the first part of Theorem 1.2**

From Corollary 5.2, and c) of Fact 3, in order to prove the first part of Theorem 1.2, namely that $S_F$ can be identified to an intersection closed subset of the set $F(\mathbf{n}_0 \otimes \cdots \otimes \mathbf{n}_{k-1})$, all that we need is to prove that for each $i$, there is a coding $(f_i, g_i)$, with $f_i$ surjective, from $(A^*, \rho_{Fi}, A^*)$ into $(\mathbf{n}_i, \neg \leq, \mathbf{n}_i)$. But, this is false. From Fact 9, a coding from $(A^* \setminus F, \rho_{Fi}, A^* \setminus F)$ into $(\mathbf{n}_i, \neg \leq, \mathbf{n}_i)$ suffices. Let $X_0, \dots, X_{n-1}$ be non-empty subsets of $A$ and let $X := X_0 \cdots X_{n-1}$ (that is the set of words $x_0 \cdots x_{n-1}$ with $x_i \in X_i$) and let $F := \upharpoonright X$. Let $\mathbf{n} := \{0, \dots, n-1\}$ be equipped with the natural ordering. Let $f : A^* \setminus F \to \mathbf{n}$ and $g : A^* \setminus F \to \mathbf{n}$ defined as follows: For $v \in A^* \setminus F$, if there is $m \in \mathbb{N}$ such that $v \in \upharpoonright (X_0 \cdots X_{m-1})$ then $f(v)$ is the largest $m$ having this property, otherwise $f(v) = 0$. For $w \in A^* \setminus F$, if there is $p \in \mathbb{N}$ such that $w \in \upharpoonright \{X_{p-1} \cdots X_{n-1}\}$ then $g(v)$ is the least $p$ having this property, otherwise $g(v) = n-1$. By a straightforward verification, we have the following:

**Fact 10.** The map $f$ is surjective and the pair $(f, g)$ form a coding from $(A^* \setminus F, \rho_F, A^* \setminus F)$ into $(\mathbf{n}, \neg \leq, \mathbf{n})$.

This proves the first part of Theorem 1.2.

**5.4. Proof of the second part of Theorem 1.2**

Let $F := F_0 \cup \dots \cup F_{k-1}$, let $X_i \subseteq F$ such that $F_i = \upharpoonright X_i$ and let $X_{i_0}, \dots, X_{i_{n-1}} \subseteq A$ such that $X_{i_0} \cdots X_{i_{n-1}} = X_i$. From Fact 10 above, for each $i$, we have a coding $(f_i, g_i)$ from $(A^* \setminus F_i, \rho_{Fi}, A^* \setminus F_i)$ into $(\mathbf{n}_i, \neg \leq, \mathbf{n}_i)$. The restrictions of $f_i$ and $g_i$ to $A^* \setminus F$ give a coding that we still denote $(f_i, g_i)$ from $(A^* \setminus F_i, \rho_{Fi}, A^* \setminus F_i)$ into $(\mathbf{n}_i, \neg \leq, \mathbf{n}_i)$ and $f_i$ is still surjective. From Fact 4, $(\Pi f_i, \Pi g_i)$ is a coding from $R_F := (A^* \setminus F, \cup \rho_{Fi}, A^* \setminus F)$ into $R' := (\mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1}, \neg \leq, \mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1})$ where $\leq$ is the natural ordering on the direct product $\mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1}$. Since for each $i, f_i$ is surjective, $\Pi f_i$ is surjective (indeed, for $(m_0, \dots, m_{k-1}) \in \mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1}$, the $k$-uple
$(u_0, \dots, u_{k-1})$, where $u_0 \in f_0^{-1}(m_0), \dots, u_{k-1} \in f_0^{-1}(m_{k-1})$, belongs to $A^* \setminus F_0 \times \dots \times A^* \setminus F_{k-1})$ and from (c) of Fact 3, $\mathrm{Gal}(R_F)$ is identified with an intersection closed subsets of $\mathrm{Gal}(R')$ which is $\mathbf{F}(\mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1})$ by Fact 2. $\square$

### 5.5. An explicit isomorphism

For reader's convenience, let us describe explicitly the isomorphism between $S_F$ and an intersection closed subset of $\mathbf{F}(\mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1})$. For sake of simplicity, let us suppose that $F$ is finitely generated (which is the case if $A$ is w.q.o.). Let $u_0, \dots, u_{k-1} \in A^*$, $n_0 := |u_0|, \dots, n_{k-1} := |u_{k-1}|$, and $F := \uparrow \{u_0, \dots, u_{k-1}\}$. Let $v \in A^*$; for each $i \in \{0, \dots, k-1\}$, let $v_i''$ be the largest suffix of $u_i$ such that $v_i'' \le v$ and let $v_i'$ be the unique prefix of $u_i$ such that $u_i = v_i' v_i''$. Set $s(v) := \{x := (x_0, \dots, x_{k-1}) \in \mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1} \text{ such that } x_i < |v_i| \text{ for all } i\}$ and $\tau(v) := \mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1} \setminus s(v)$.

Define $\varphi : S_F \to \mathbf{F}(\mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1})$ by setting

$$ \varphi(X) := \bigcap_{v \in A^*, X \subseteq \rho^{-1}(v)} \tau(v). $$

For $w := w_0 \dots w_m \in A^*$ and $\ell < |w|$, let $w_\ell = w_0 \dots w_{\ell-1}$ be the restriction of $w$ to the first $\ell$ letters. Let $x := (x_0, \dots, x_{k-1}) \in \mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1}$, let $\mu(x) = \uparrow \{u_{i|x_{i-1}} : 0 \le i \le k-1\}$ be the final segment of $A^*$ generated by words of the form $u_{i|x_{i-1}}$.

Define $\Psi : \mathbf{F}(\mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1}) \to S_F$ by setting

$$ \Psi(Y) := \bigcap_{x \in \mathbf{n}_0 \otimes \dots \otimes \mathbf{n}_{k-1} \setminus Y} \mu(v). $$

The maps $\varphi$ and $\Psi$ preserve intersections and $\Psi \circ \varphi = \mathrm{id}_{S_F}$.

### 5.6. Finiteness of the injective envelope

**Proposition 5.3.** Let $F$ be a final segment of $A^*$. The following conditions are equivalent:

(i) The injective envelope $S_F$ is finite;

(ii) $F$ is finite union $F = F_0 \cup \dots \cup F_i \cup \dots \cup F_{k-1}$ of final segments, each $F_i$ is generated by a set $X_i$ of words $u$ of the same length $n_i$, all of the form $u := u_0 \dots u_j \dots u_{n_i-1}$ with $u_j \in X_{j,i} \subseteq A$.

*Proof.* (i) $\Rightarrow$ (ii). Let us suppose that $S_F$ is finite. Let $A_F$ be the corresponding reflexive and involutive automaton with an initial state $x := A^*$ and a final state $y := F$. Let $Q_F^*$ be the set of finite sequences $s := (s_0, \dots, s_n)$ such that all $s_i$ are distinct states, $s_0 := x, s_n := y, (s_i, a_i, s_{i+1}) \in T_F$ for some letter $a_i$. Since $S_F$ is finite this set is finite too. For each $s := (s_0, \dots, s_n)$ let $X_{s_j} := \{a \in A : (s_j, a, s_{j+1}) \in T_F\}$ and let $X_s := \{a_0 \dots a_{n-1} : a_j \in X_{s_j}\}$ and let $F_s := \uparrow X_s$. It is easy to check that $F = \bigcup_{s \in Q_F} F_s$, hence has the form mentioned above.

(ii) $\Rightarrow$ (i). Apply Theorem 1.2. $\square$

**Theorem 5.4.** Let $\mathcal{H} := \mathbf{F}(A^*)$ be the Heyting algebra made of final segments of $A^*$. The following conditions are equivalent:

(i) $A$ is well-quasi-ordered;

(ii) The injective envelope $\mathcal{N}(E)$ of every finite metric space $E$ is finite.

*Proof.* $\neg (i) \iff \neg (ii)$. Let $F$ be a final segment of $A^*$. According to Proposition 5.3, the injective envelope $S_F$ is infinite whenever for each decomposition $F = \cup F_i$, some $F_i$ cannot be generated by a set of words having a bounded length. This is the case if $F$ is generated by an infinite antichain $X$ made of words of unbounded length. If $A$ is not w.q.o., then there is an infinite bad sequence of letters, say $a_0, \dots, a_n, \dots$. The set $X = \{a_0, a_1 a_2, a_3 a_4 a_5, a_6 a_7 a_8 a_9, \dots\}$ is such an example.
(i) $\implies$ (ii). According to Proposition 2.4, it suffices to show that the injective envelope of a two-element metric space is finite. Let $F$ be a final segment of $A^*$. If $A$ is w.q.o., $F$ satisfies condition (ii) of Proposition 5.3, hence $S_F$ is finite. $\square$

**Comments.** Proposition 5.3 and Theorem 5.4 are special instances of two basic facts of language theory concerning rational languages, namely Myhill-Nerode Theorem (see [43] Thm. 2.3, p. 247) and a result of Ehrenfeucht-Haussler-Rozenberg ([15], Thm. 3.3; see [43] Thm. 5.3, p. 296). For brevity, let us put these results together in the context of monoids. Let us recall that if $L$ is a subset of a monoid $M$, the residuals of $L$ are sets of the form $Lv^{-1} := \{u \in M : uv \in L\}$ for $v \in M$ and of the form $u^{-1}L := \{v \in M : uv \in L\}$ for $u \in M$. The syntactic congruence of $L$ is the largest congruence $\equiv_L$ on $M$ for which $L$ is an union of classes. The set $L$ is recognisable if it is the union of classes of a congruence on $M$ which has finitely many classes alias finite index). The aforementioned results read as follows:

**Theorem 5.5.** For a subset $L$ of a monoid $M$, the following properties are equivalent:

(i) $L$ is recognisable;

(ii) The set of residuals $\{Lv^{-1} : v \in M\}$ is finite;

(iii) The set of residuals $\{u^{-1}L : u \in M\}$ is finite;

(iv) The syntactic congruence $\equiv_L$ has finite index;

(v) $L$ is a final segment of a well-quasi-ordered set on $M$ which is compatible with the monoid operation.

The equivalences from (i) to (iv) is Myhill-Nerode Theorem. The equivalence with (v) is Ehrenfeucht-Haussler-Rozenberg Theorem.

Let $R := (M, \rho_L, M)$ be the incidence structure where $\rho_L := \{(u, v) \in M \times M : uv \in L\}$. Then $u\rho_L v \iff uv \in L$ and $R(u) = u^{-1}L$, $R^{-1}(v) = Lv^{-1}$ for all $u, v \in M$. Conditions (ii) and (iii) in the theorem above express both that the Galois lattice $Gal(R)$ is finite.

According to Higman's Theorem, if the alphabet $A$ is w.q.o., $A^*$ equipped with the Higman ordering is w.q.o. Since this ordering is compatible with concatenation, we may apply (v) to every final segment $F$ of $A^*$, obtaining that the Galois lattice $Gal(R)$ is finite. Since the domain of this lattice is $S_F$, implication (i) $\implies$ (ii) of Theorem 5.4 follows.

# 6. INTERVAL ORDERS, FERRERS RELATIONS AND INJECTIVE ENVELOPE

In this section we characterize a natural class of envelopes $S_F$, namely those that are linearly orderable (cf. Def. 2.5). These are precisely the spaces associated with final segments $F$ such that the relation $\rho_F$ is Ferrers (Thm. 6.8).

We record the characterization of interval orders and Ferrers relations. These two notions are intertwined. Interval orders are those orderings for which the irreflexive part is a Ferrers relation. Ferrers relations have been introduced by J.Riguet [41]. Interval orders are studied by Fishburn in [18]. Part of the characterization of these relations given below is due to Wiener [48]. Let $C$ be a chain; an interval of $C$ is any subset of $I$ such that

$$x \in I, y \in I \text{ and } x \le z \le y \text{ imply } z \in I. \qquad (6.1)$$

The collection $\text{Int } C$ of non-empty intervals of $C$ is ordered by domination as follows:

$$X \le Y \text{ if } X = Y \text{ or } x < y \text{ for all } x \in X, y \in Y. \qquad (6.2)$$

Let $P$ be a poset. The ordering on $P$, or $P$ itself, is an interval order if $P$ is order isomorphic to a collection of non-empty intervals of some chain $C$, ordered by condition (6.2).

To each incidence structure $R := (V, \rho, W)$ we associate a poset $B(R) := (P, \le)$ defined as follows:
The domain of $P$ is $V \times \{0\} \cup W \times \{1\}$, for $u = (x, i)$, $v = (y, j) \in P$, the order relation is defined by:

$$u \leq v \text{ if } x = y \text{ or } i < j \text{ and } xpy. \qquad (6.3)$$

Let $R := (V, \rho, W)$ be an incidence structure. We say that $R$ is *Ferrers* or $\rho$ is a *Ferrers relation* if $R$ satisfies one of the following conditions (see [18]):

**Proposition 6.1.** Let $R := (V, \rho, W)$ be an incidence structure. The following conditions are equivalent:

(i) The set $\{R(x) : x \in V\}$ is totally ordered by inclusion;

(ii) The set $\{R^{-1}(y) : y \in W\}$ is totally ordered by inclusion;

(iii) The Galois lattice Gal($R$) is totally ordered by inclusion;

(iv) $R$ has a coding into a chain;

(v) The poset $B(R)$ does not embed the direct sum $2 \oplus 2$ of two copies of the 2-element chain 2;

(vi) The ordering on $B(R)$ is an interval order;

(vii) $xpy$ and $x'py'$ imply $xpy'$ or $x'py$ for all $x, x' \in V$, $y, y' \in W$.

We say that a language $L$ is *Ferrers* if the relation $\rho_L$ is *Ferrers*.

According to condition (vii) of Proposition 6.1, this amounts to the following condition:

$$xx' \in L \text{ and } yy' \in L \text{ imply } xy' \in L \text{ or } yx' \in L \text{ for all } x, x', y, y' \in A^*. \qquad (6.4)$$

The study of Ferrers relations leads to the notion of *Ferrers dimension* of a binary relation: the least number of Ferrers relations whose intersection is this relation. The study of this notion, initiated by Bouchet in his thesis [6], yields numerous interesting results (e.g., see [7, 11]). This suggests to look at the same direction in the theory of languages. But, we may notice that contrarily to the case of relations, not every language is Ferrers, or is an intersection of Ferrers languages. In fact, if $w$ is any word, $\rho_{\{w\}}$ is a Ferrers relation only if $w = \square$ (indeed, let $R := (A^*, \rho_{\{w\}}, A^*)$, then $\text{Gal}(R) = \{\{u\} : u \text{ prefix of } w\} \cup \{\emptyset, A^*\}$, thus if $w \neq \square$, the Galois lattice has at least two incomparable elements, namely $\{w\}$ and $\{\square\}$ plus a top and a bottom, thus it is not a chain). Thus, if $w \neq \square$, $\{w\}$ is not a Ferrers language and since it is a singleton, it is not a union of Ferrers languages, hence its complement $A^* \setminus \{w\}$ is not an intersection of Ferrers languages.

Since the complement of a Ferrers relation is Ferrers, the complement of a Ferrers language is Ferrers (apply (1) of Fact 8). The concatenation of two Ferrers languages is not Ferrers in general. For a simple minded example, let $A := \{a, b\}$, let $U := \{a^n : n \geq 2\}$, $U' := \{b^n : n \geq 2\}$. Each of these languages is Ferrers, but the concatenation $UU'$ is not: let $x := a^2b, y := b$ and $x' := a, y' := ab^2$. Then $xy = x'y' = a^2b^2 \in UU'$ but neither $xy' = a^2bab^2$ nor $x'y = ab$ belong to $UU'$.

Recall that for two words $u$ and $v$, $u$ is a prefix of $v$ if $v = uw$ for some word $w$; similarly, $u$ is a suffix of $v$ if $v = wu$ for some word $w$.

**Fact 11.** Let $U$ and $U'$ be two subsets of $A^*$. If $U, U'$ are Ferrers and $U$ is a final segment for the prefix ordering or $U'$ is a final segment for the suffix ordering then the concatenation $UU'$ is Ferrers.

*Proof.* Let $L := UU'$, let $xx' \in L$ and $yy' \in L$. We prove that either $xy'$ or $x'y$ belong to $L$. There are four cases to consider; we only consider two, the others being similar.

**Case 1.** $x = x_1x_2, y = y_1y_2$ with $x_1, y_1 \in U$ and $x_2x' \in U'$ and $y_2y' \in U'$. Since $U'$ is Ferrers, either $x_2y' \in U'$ or $y_2x' \in U'$. In the former case $xy' \in UU'$ whereas in the latter $yx' \in UU'$.

**Case 2.** $x = x_1x_2, y' = y'_1y'_2$ with $x_1 \in U, y'_1 \in U, x_2x' \in U'$ and $y'_2 \in U'$. If $U$ is a final segment for the prefix ordering, then $x_1x_2y'_1 \in U$ since $x_1$ belongs to $U$ and is a prefix of $x_1x_2y'_1$. Thus $xy' = x_1x_2y'_1y'_2 \in UU'$. If $U'$ is a final segment for the suffix ordering, then $x_2y'_1y'_2 \in U'$ since $y'_2$ belongs to $U'$ and is a suffix of $y'_2$. Thus $xy' = x_1x_2y'_1y'_2 \in UU'$.

**Corollary 6.2.** The concatenation of finitely many Ferrers final segments of $A^*$ is a Ferrers final segment.
We recall that an ideal of an ordered set $P$ is any non-empty initial segment $\mathcal{I}$ which is up-directed (that is any two elements $x$ and $y$ of $\mathcal{I}$ have an upper bound $z$ in $\mathcal{I}$). Filters are defined dually. Ideals of $P$ are the join-irreducible elements of the lattice $I(P)$ of initial segments of $P$. Ideals of the poset $A^*$ equipped with the Higman ordering have been described when $A$ is finite by Jullien [24] and by us [26] when $A$ is an ordered alphabet possibly infinite. According to Jullien, an *elementary ideal* of $A^*$ is any set of the form $J \cup \{\square\}$ for some non empty ideal $J$ of $A$, a *star-ideal* is any set of the form $\mathcal{I}^*$ for some initial segment $\mathcal{I}$ of $A$. Products of ideals are ideals. It is proved in [26] that every ideal is a finite product of elementary and star-ideals if and only if the alphabet is well-quasi-ordered.

**Fact 12.** Ideals and filters of $A^*$ are Ferrers.

*Proof.* Let $\mathcal{I}$ be an ideal of $A^*$. Suppose $xx', yy' \in \mathcal{I}$. We prove that $xy'$ or $yx' \in \mathcal{I}$. Let $z \in \mathcal{I}$ such that $xx', yy' \le z$. Let $z_1$ be the least prefix of $z$ such that $x, y \le z_1$ and $z_2$ the corresponding suffix, i.e., $z = z_1z_2$. If $x' \le z_2$ or $y' \le z_2$, then since $x, y \le z_1$ then $xy'$ or $yx' \in \mathcal{I}$. If not, then since $xx' \le z$ and $yy' \le z$, we have $x, y \le z_1$, where $z_1$ is obtained from $z_1$ by deleting its last letter. This contradicts the choice of $z_1$. Hence, $\mathcal{I}$ is Ferrers. Let $\mathcal{F}$ be a filter of $A^*$. Let $xx', yy' \in \mathcal{F}$. Let $z \in \mathcal{F}$ such that $z \le xx'$ and $z \le yy'$. Write $z = z^x z^{x'}$ with $z^x \le x$, $z^{x'} \le x'$ and $z = z^y z^{y'}$ with $z^y \le y$, $z^{y'} \le y'$. Either $z^{y'} \le z^{x'}$ or $z^{x'} \le z^{y'}$. In the first case, since $z^y \le y$ and $z^{y'} \le z^{x'} \le x'$ we have $z = z^y z^{y'} \le yx'$, hence $yx' \in \mathcal{F}$. In the second case we obtain similarly $xy' \in \mathcal{F}$. Hence $\mathcal{F}$ is Ferrers. $\square$

For every $u \in A^*$, the initial segment $\downarrow u$ of $A^*$ is an ideal and the final segment $\uparrow u$ of $A^*$ is a filter, hence:

**Corollary 6.3.** For every $u \in A^*$, the initial segment $\downarrow u$ of $A^*$ and the final segment $\uparrow u$ of $A^*$ are Ferrers.

Since $\{u\} = \downarrow u \cap \uparrow u$, we have:

**Corollary 6.4.** For every $u \in A^*$, $\{u\}$ is an intersection of two Ferrers languages and $A^* \setminus \{u\}$ is an union of two Ferrers languages.

If $A$ is w.q.o., every final segment is finitely generated and every ideal is a finite union of ideals, hence from the second part of Corollary 6.3 and from the first part of Fact 12, we obtain.

**Corollary 6.5.** If $A$ is w.q.o., every final segment if a finite union and a finite intersection of Ferrers languages.

From Corollary 6.2 and Fact 12 follows:

**Proposition 6.6.** Final segments of $A^*$ which are finite product of complement of ideals of $A^*$ are Ferrers.

According to Corollary 6.4, for every $u \in A^*$, $A^* \setminus \{u\}$ is an union of two Ferrers languages, hence:

**Proposition 6.7.** Every language is a union, possibly infinite, of a family of intersections of two Ferrers languages.

According to Corollary 6.5, if the alphabet is w.q.o. (and particularly, if it is finite), Boolean combinations of final segments, alias piecewise testable languages, are Boolean combination of rational Ferrers languages.

- If the alphabet $A$ consists of one letter, say $a$, these two Boolean algebras coincide. Indeed, if $L$ is Ferrers then with respect to the natural order on $A^* := \{a^n : n \in \mathbb{N}\}$, it is convex. Otherwise, there are $n < p < m \in \mathbb{N}$ such that $a^n, a^m \in L$, $a^p \notin L$. Choosing $n, m$ with the difference $m-n$ minimum, we have $a^q \notin L$ for $n < p < m$. Let $X := (a^n)^{-1}L$ and $Y := (a^{m-1})^{-1}L$. Then $\square$ and $a^{m-n} \in X$ but $a \notin X$, whereas $a \in Y$ but $\square \notin Y$. Hence, $X$ and $Y$ are incomparable with respect to inclusion, contradicting the fact that $L$ is Ferrers. Being convex, $L$ is the intersection of an initial segment with a final segment, thus it is piecewise testable.

- If $A := \{a, b\}$, with $a \neq b$, then $L := A^*b$ is rational and Ferrers and not piecewise testable. Indeed, let $Q_L := \{u^{-1}L : u \in A^*\}$, then $Q_L$ has two elements, namely $L$ and $L' := \{\square\} \cup L$ (in fact $a^{-1}L = L$, $b^{-1}L = L'$, $a^{-1}L' = L$, $b^{-1}L' = L'$. The fact that $L$ is not piecewise testable follows from Stern'criterium ([45], Thm. 1.2): the sequence $(u_n)_{n \in \mathbb{N}}$ defined by $u_{2n} := (ba)^n b$ and $u_{2n+1} := (ba)^{n+1}$ is increasing for the subword ordering while $u_{2n} \in L$ and $u_{2n+1} \notin L$ for all $n \in \mathbb{N}$.

The language $L$ above has dot-depth one. Is this general? That is:
**Question.** Do rational Ferrers languages have dot-depth one?

We relate Ferrers piecewise testable languages and structural properties of transition systems.

**Theorem 6.8.** Let $F$ be a final segment of $A^*$. The following conditions are equivalent:

1. $F$ is a Ferrers language;

2. The space $S_F$ is linearly orderable.

*Proof.* Propositions 6.1 and 2.6. □

**Corollary 6.9.** The finitely indecomposable absolute retracts are linearly orderable.

*Proof.* Let $E$ be a finitely indecomposable absolute retract. From Theorem 2.7, $E$ is isomorphic to $S_F$ where $F$ is join-irreducible in the lattice $F(A^*)$ ordered by reverse of inclusion. The fact that $F$ is join-irreducible amounts to the fact that $A^* \setminus F$ is an ideal of $A^*$. According to Fact 12, $A^* \setminus F$ is Ferrers. Hence, its complement $F$ is Ferrers. The result follows from Theorem 6.8. □

*Acknowledgements.* We are very pleased to thank the referees of this paper for their suggestions and corrections.

## REFERENCES

[1] N. Aronszajn and P. Panitchpakdi, Extensions of uniformly continuous transformations and hyperconvex metric spaces. *Pac. J. Math.* **6** (1956) 405–439.

[2] B. Banaschewski and G. Bruns, Categorical characterization of the MacNeille completion. *Arch. Math. Basel* **18** (1967) 369–377.

[3] L.M. Blumenthal, Boolean geometry. *Rend. Circ. Mat. Palermo* **2** (1952) 343–360.

[4] L.M. Blumenthal, Theory and Applications of Distance Geometry, 2nd edn. Chelsea Publishing Co., New York (1970) xi+347.

[5] L.M. Blumenthal and K. Menger, Studies in Geometry, W. H. Freeman and Co., San Francisco, California (1970) xiv+512.

[6] A. Bouchet, Codages et Dimensions de Relations Binaires, Orders: Description and Roles. In Vol. 23 of *Annals of Discrete Mathematics*. Edited by M. Pouzet and D. Richard. Elsevier, Amsterdam, The Netherlands (1984) 387–396.

[7] O. Cogis, On the Ferrers dimension of a digraph. *Discrete Math.* **38** (1982) 47–52.

[8] E. Corominas, Sur les ensembles ordonnés projectifs et la propriété du points fixe. *C. R. Acad. Sci. Paris, Série A* **311** (1990) 199-204.

[9] B.A. Davey and H.A. Priestley, Introduction to Lattices and Order, 2nd edn. Cambridge University Press, New York (2002) xii+298.

[10] M. Deza, E. Deza, Encyclopedia of Distances, 4th edn. Springer, Berlin (2016) xxii+756.

[11] J.P. Doignon, A. Ducamp, J.C. Falmagne, On realizable biorders and the biorder dimension of a relation. *J. Math. Psych.* **28** (1984) 73–109.

[12] A.W.N. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups, a note on combinatorial properties of metric spaces. *Adv. Math.* **53** (1984) 321–402.

[13] A.W.N. Dress, Towards a classification of transitive group actions on finite metric spaces. *Adv. Math.* **74** (1989) 163–189.

[14] D. Duffus, I. Rival, A structure theory of ordered sets. *J. Discrete Math.* **35** (1981) 53–118.

[15] A. Ehrenfeucht, D. Haussler and G. Rozenberg, On regularity of context-free languages. *Theor. Comput. Sci.* **27** (1983) 311–332.

[16] P. Eklund, J. Gutiérrez García, U. Höhle and J. Kortelainen, Semigroups in Complete Lattices: Quantales, Modules and Related Topics, Developments in Mathematics. Springer, Berlin (2018).

[17] R. Espínola and M.A. Khamsi, Introduction to Hyperconvex Spaces, in Handbook of Metric Fixed Point Theory. Kluwer Academic Publisher, Dordrecht (2001) 391–435.

[18] P.C. Fishburn, Interval Orders and Interval Graphs. Wiley, Hoboken, NJ, USA (1985).

[19] G. Higman, Ordering by divisibility in abstract algebra. *Proc. London Math. Soc.* **3** (1952) 326–336.

[20] A. Hudry, Rétractions, corrétractions et envelope injective d'une algèbre de transitions. *Discrete Math.* **247** (2002) 117–134.

[21] A. Hudry, Injective envelope and parallel decomposition of a transition system. *Discrete Math.* **289** (2004) 45–61.

[22] J.R. Isbell, Six theorems about injective metric spaces. *Comment. Math. Helv.* **39** (1964) 65–76.

[23] E. Jawhari, D. Misane and M. Pouzet, Retracts graphs and ordered sets from the metric point of view. *Contemp. Math.* **57** (1986) 175–226.

[24] P. Jullien, Sur un théorème d'extension dans la théorie des mots. *C. R. Acad. Sci. Paris Série* **266** (1968) 851–854.

[25] K. Kaarli and S. Radeleczki, Representation of integral quantales by tolerances. *Algebra Universalis* **79** (2018) 5.

[26] M. Kabil, M. Pouzet, Une extension d'un théorème de P. Jullien sur les âges de mots. *RAIRO: ITA* **26** (1992) 449–482.
[27] M. Kabil and M. Pouzet, Indécomposabilité et irréductibilité dans la variété des rétractes absolus des graphes réflexifs. *C. R. Acad. Sci. Paris Série A* **321** (1995) 499-504.

[28] M. Kabil, *Une approche métrique de l'indécomposabilité et de l'irréductibilité dans la variété des rétractes absolus des graphes et des systèmes de transitions*. Thèse de doctorat d'État, Université Hassan II Aïn Chock, Casablanca, Morocco, 19 Décembre (1996).

[29] M. Kabil and M. Pouzet, Injective envelope of graphs and transition systems. *Discrete Math.* **192** (1998) 145–186.

[30] M. Kabil, M. Pouzet and I.G. Rosenberg, Free monoids and metric spaces. *Euro. J. Combinatorics* **80** (2019) 339–360

[31] M. Kabil and M. Pouzet, Geometric Aspects of Generalized Metric Spaces: Relations with Graphs, Ordered Sets and Automata, Chap.11, in New Trends in Analysis and Geometry, edited by A.H Alkhaldi, M.K. Alaoui and M.A. Khamsi. Cambridge Scholars Publishing, Cambridge (2020) 319–377.

[32] A.D. Korshunov, The number of monotonic Boolean functions. *Problemy Kibern* **38** (1981) 5–108.

[33] M. Lothaire, Combinatorics on Words, Encyclopedia Mathematics Applied, Addison-Wesley, Boston, USA (1983) 17.

[34] K. Menger, Probabilistic geometry. *Proc. Natl. Acad. Sci. USA* **37** (1951) 226–229.

[35] M. Nivat, Personnal communication (1989).

[36] R. Nowakowski and I. Rival, The smallest graph variety containing all paths. *J. Discrete Math.* **43** (1983) 185–198.

[37] M. Pouzet, Une Approche Métrique de la Rétraction dans les Ensembles Ordonnés et les graphes, (French) [A Metric Approach to Retraction in Ordered Sets and Graphs] *Proceedings of the conference on infinitistic mathematics* (Lyon, 1984), 59–89, *Publ. Dép. Math. Nouvelle Sér. B*, 85-2, *Univ. Claude-Bernard, Lyon* (1985).

[38] M. Pouzet and I.G. Rosenberg, General metrics and contracting operations. *Discrete Math.* **130** (1994) 103–169.

[39] M. Pouzet, When is the orbit algebra of a group an integral domain? Proof of a conjecture of P. J. Cameron. *Theor. Inform. Appl.* **42** (2008) 83–103.

[40] M. Pouzet and H. Si Kaddour, N. Zaguia, Finite dimensional scattered posets. *Euro. J. Combinatorics* **37** (2014) 79–99.

[41] J. Riguet, Les relations de Ferrers. *C. R. Acad. Sci. Paris Série A* **232** (1951) 1729-1730.

[42] F. Saïdane, *Graphe et languages: une approche metrique*. Thèse de doctorat, Université Claude-Bernard, Lyon, France (1991).

[43] J. Sakarovitch, Elements of Automata Theory, Translated from the 2003 French original by Reuben Thomas. Cambridge University Press, Cambridge (2009).

[44] I. Simon, Piecewise Testable Events, Automata Theory and Formal Languages (Second GI Conf., Kaiserslautern, 1975), In Vol. 33 of *Lecture Notes in Comput. Sciences*. Springer, Berlin (1975) 214–222.

[45] J. Stern, Characterizations of some classes of regular events. *Theor. Comput. Sci.* **35** (1985) 17–42.

[46] G. Viennot, *Factorisations des Monoides*. Thèse de 3ème cycle, Paris, Janvier (1971).

[47] D. Wiedemann, A computation of the eight Dedekind number. *Order* **8** (1991) 5–6.

[48] N. Wiener, A contribution to the theory of relative position. *Proc. Camb. Philos. Soc.* **17** (1914) 441–449.