Mário Branco

Jean-Eric Pin

M Ário

J J Branco

Jean-Éric Pin

INEQUALITIES FOR ONE-STEP PRODUCTS

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

The concatenation product of languages and its connection with algebra and logic has been a very active research area over the past fifty years. It is often sufficient to consider one-step products of the form L → LaA * where a is a letter of the alphabet A, or their dual forms L → A * aL. For instance, it has been shown [START_REF] Pin | Variétés de langages et variétés de semigroupes[END_REF][START_REF] Weil | Products of languages with counter[END_REF][START_REF] Weil | Closure of varieties of languages under products with counter[END_REF] that a variety of regular languages closed under these two operations is also closed under product. It is also known that a regular language belongs to the smallest variety of languages closed under one-step products if and only if its syntactic monoid is R-trivial. One step products were also used in [START_REF] Thérien | A language theoretic interpretation of the Schützenberger representations with applications to certain varieties of languages[END_REF] to describe the languages whose syntactic monoid is idempotent (see also [START_REF] Brzozowski | Classification of noncounting events[END_REF][START_REF] Eilenberg | Automata, Languages and Machines[END_REF]) and in [START_REF] Cohen | On the expressive power of temporal logic for finite words[END_REF] to get the expressive power of linear temporal logic without until.

The purpose of this article is to conduct a comprehensive study of onestep products, first for arbitrary languages, then for regular languages, using the so called equational approach.

Historical background. In the regular case, the equational approach goes back to Schützenberger's characterization of star-free languages by the profinite equation x ω+1 = x ω [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF]. Two results make it possible to account for similar situations: Eilenberg's variety theorem [START_REF] Eilenberg | Automata, Languages and Machines[END_REF], which gives a bijection between varieties of regular languages and varieties of finite monoids and Reiterman's theorem [START_REF] Reiterman | The Birkhoff theorem for finite algebras[END_REF] which provides a description of varieties of finite monoids by profinite equations.

During the years 1975-2000, much effort was devoted to operations on regular languages, notably concatenation product [START_REF] Straubing | Aperiodic homomorphisms and the concatenation product of recognizable sets[END_REF][START_REF] Pin | Profinite semigroups, Mal'cev products and identities[END_REF]. One-step products were first considered as an exercise in Eilenberg's book [11, Exercise IX. 2.1] and a deep result of [START_REF] Almeida | Profinite categories and semidirect products[END_REF] led to an equational characterization of this operation in the variety setting.

However, varieties of languages soon proved to be an overly constrained concept and a series of generalizations were successively introduced [START_REF] Pin | A variety theorem without complementation[END_REF][START_REF] Ésik | Extended temporal logic on finite words and wreath products of monoids with distinguished generators[END_REF][START_REF] Straubing | On logical descriptions of regular languages[END_REF][START_REF] Pin | Some results on C-varieties[END_REF][START_REF] Gehrke | Duality and equational theory of regular languages[END_REF], each of them leading to an update of the equational approach. The first of these updates [START_REF] Pin | A variety theorem without complementation[END_REF] consisted in replacing profinite equations by profinite inequalities and the last one led to a very concise statement: every lattice of regular languages can be defined by a set of profinite inequalities.

On the other hand, an even more ambitious generalization was proposed in [START_REF] Gehrke | A topological approach to recognition[END_REF]. It applies to arbitrary languages, but the price to pay is to replace profinite words by ultrafilters. Still, a similar result holds: every lattice of languages can be defined by a set of ultrafilters inequalities.

Main results.

Let A be a finite alphabet, let L be a lattice of languages of A * and let a be a letter of A. Let L a be the lattice generated by the languages of the form L or LaA * , where L ∈ L. Let also L 1 be the lattice generated by the union of all lattices L a , for a ∈ A.

Our first main result (Theorem 4.1 and Corollary 4.2) gives ultrafilter inequalities defining L a and L 1 , given the ultrafilter inequalities defining L. A similar result was given in [START_REF] Gehrke | The Schützenberger product for syntactic spaces[END_REF] but our inequalities are simpler and have the advantage to give immediately profinite inequalities in the regular case (Theorem 4.3 and Corollary 4.4). Moreover, our approach is quite generic and could easily be transposed to other settings than one-step products.

Our second main result gives a much smaller basis of profinite inequalities when L is a Boolean algebra of regular languages closed under quotients (Theorem 5.2): The lattice L 1 admits as a base the set of profinite inequalities of the form zx = zx 2 , zxy = zyx and z zx, where x, y and z are profinite words such that the profinite equations z = zx = zy hold in L. The proof relies on the conjunction of two advanced tools, the derived category of a relational morphism and Simon's theorem on the free category on a finite graph, supplemented by a compactness argument.

Our paper is organized as follows. Section 1 gathers the needed topological notions. Section 2 presents the inequality theory for languages. One step products are introduced in Section 3, and Section 4 provides ultrafilter inequalities for L a and L 1 . Section 5 gives a base of profinite inequalities for L 1 when L is a Boolean algebra closed under quotients.

Stone duality and inequalities

In this paper, we denote by S c the complement of a subset S of a set E. We also denote L the topological closure of a subset L of a topological space.

Let A be a finite alphabet. A lattice of languages is a set L of languages of A * closed under finite unions and finite intersections. A lattice closed under complement is a Boolean algebra. It is closed under quotients if, for each L ∈ L and u ∈ A * , the languages u -1 L and Lu -1 are also in L. Recall that u

-1 L = {x ∈ A * | ux ∈ L} and Lu -1 = {x ∈ A * | xu ∈ L}.
Let B be a Boolean algebra of languages of A * . An ultrafilter of B is a non-empty subset γ of B such that:

(1) the empty set does not belong to γ, (2) if K ∈ γ and K ⊆ L, then L ∈ γ (closure under extension)

(3) if K, L ∈ γ, then K ∩ L ∈ γ (closure under intersection), (4) for every L ∈ B, either L ∈ γ or L c ∈ γ (ultrafilter condition). Stone duality tells us that B has an associated compact Hausdorff space S(B), called its Stone space. This space is given by the set of ultrafilters of B with the topology generated by the basis of clopen sets of the form {γ ∈ S(B) | L ∈ γ}, where L ∈ B.

Only two Stone spaces are considered in this paper. The first one is the Stone space of the Boolean algebra of all the subsets of A * , known as the Stone-Čech compactification of A * and denoted by βA * . An important property of βA * is that every map f from A * to a compact space K has a unique continuous extension βf : βX → K.

The second one is the Stone space of the Boolean algebra of all regular subsets of A * . It was proved by Almeida [START_REF] Almeida | Residually finite congruences and quasi-regular subsets in uniform algebras[END_REF] to be equal to the free profinite monoid on A, denoted by A * . Its elements are called profinite words. We refer to [START_REF] Almeida | Finite semigroups and universal algebra[END_REF][START_REF] Pin | Profinite methods in automata theory[END_REF][START_REF] Pin | Equational descriptions of languages[END_REF] for more information on this space, which can also be seen as the completion of the metric space (A * , d), where d is the profinite metric on A * .

Two other facts will be used in this paper. First, if X, Y ⊆ A * , then XY = X Y . Secondly, the monoid A * is equidivisible [START_REF] Almeida | Infinite-vertex free profinite semigroupoids and symbolic dynamics[END_REF]. A monoid M is equidivisible if for every u, v, x, y ∈ M , the equality uv = xy implies that there is t ∈ M such that ut = x and v = ty, or such that xt = u and y = tv. Consequently, usual definitions on words (prefixes, suffixes, factors) extend to profinite words. This is a crucial difference with βA * , which is not even a monoid.

Hyperspace. Let X be a Hausdorff space and let C(X) be the set of its closed subsets1 , called the hyperspace of X. For each open set U , let us set

U -= {C ∈ C(X) | C ∩ U = ∅} U + = {C ∈ C(X) | C ⊆ U }.
The Vietoris topology on C(X) has as a subbase all the sets of the form U + or U -, where U is open [5, p. 47]. It is known that, equipped with the Vietoris topology, C(X) is always a compact space. When X is a metric space, then C(X) is also a metric space. The metric defining the Vietoris topology of the C( A * ) was explicitly given in [START_REF] Pin | A topological approach to transductions[END_REF].

Inequalities on languages

The inequality theory for languages was first introduced in [START_REF] Gehrke | A topological approach to recognition[END_REF] and later used in [START_REF] Gehrke | Ultrafilters on words for a fragment of logic[END_REF][START_REF] Gehrke | The Schützenberger product for syntactic spaces[END_REF][START_REF] Pin | Dual space of a lattice as the completion of a Pervin space[END_REF]. It is based on the following definitions.

Let B be a Boolean algebra of languages of A * , which, in this paper, will either be the set of all languages or the set of all regular languages of A * .

Definition 2.1. Let µ 0 , µ 1 be ultrafilters of B. A language L of B satisfies the ultrafilter inequality µ 0 µ 1 if the condition L ∈ µ 0 implies L ∈ µ 1 , or, equivalently, if the condition µ 0 ∈ L implies µ 1 ∈ L.
When B is the lattice of all regular languages, ultrafilters are profinite words and we use the terms profinite inequality and profinite equation. Definition 2.1 can be extended to sets of languages and to sets of inequalities. Given a subset S of B and an ultrafilter inequality µ 0 µ 1 , we say that S satisfies the ultrafilter inequality µ 0 µ 1 (notation µ 0 S µ 1 ) to mean that every language of S satisfies µ 0 µ 1 . Thus µ 0 S µ 1 if and only if µ 0 ∩ S ⊆ µ 1 ∩ S. It is convenient to write µ 0 = µ 1 as a shortcut for µ 0 µ 1 and µ 1 µ 0 . It is easy to see that a language L of B satisfies the ultrafilter equation µ 0 = µ 1 if and only if L and L c satisfy the ultrafilter inequality µ 0 µ 1 .

The operation L → LaA *

Let a be a letter of A and let u be a word of A * . A word v is said to be an a-prefix of u if va is a prefix of u. Let p a (u) be the set of a-prefixes of u, that is, p a (u) = {v ∈ A * | va is a prefix of u}. We view p a as a transduction from A * into itself. Following the notation introduced in [6], we set, for

L ⊆ A * , p - a (L) = {u ∈ A * | p a (u) ∩ L = ∅} p + a (L) = {u ∈ A * | p a (u) ⊆ L}
The link with the operation L → LaA * comes from the following observation: Proposition 3.1. One has p - a (L) = LaA * and p + a (L) = (L c aA * ) c . We now extend the definition of the set of a-prefixes to βA * and to A * . a-prefixes in βA * . After explaining that βA * is not a monoid, it may seem contradictory to define the set of a-prefixes of an ultrafilter. The key point is that since C(βA * ) is a compact space, any transduction of finite range from A * to itself admits a unique continuous extension from βA * to C(βA * ). This applies in particular to the map p a . Thus if µ is an ultrafilter on A * , we say that βp a (µ) is the set of a-prefixes of µ and by abuse of language, we call a-prefixes of µ an element of βp a (µ). Let a be a letter of A and let L be a lattice of languages. The aim of this section is to find out the ultrafilter inequalities satisfied by L a and L 1 , and, when L is a lattice of regular languages, the profinite inequalities satisfied by these lattices.

4.1. Ultrafilters inequalities. The ultrafilter inequalities satisfied by L a are described in the following theorem. A different description was given in [START_REF] Gehrke | The Schützenberger product for syntactic spaces[END_REF].

Theorem 4.1. Let µ 0 , µ 1 ∈ βA * . The following conditions are equivalent:

(1) The lattice L a satisfies the inequality

µ 0 µ 1 , ( 2
)
The lattice L satisfies the inequality µ 0 µ 1 and, for each a-prefix γ 0 of µ 0 , there exists an a-prefix γ 1 of µ 1 such that L satisfies the inequality γ 0 γ 1 .

Proof. In this proof, S denotes the closure in βA * of a subset S of A * .

Let K 0 = βp a (µ 0 ) and K 1 = βp a (µ 1 ). One can show that, for i = 0, 1, K i is the unique compact subset of βA * such that, for each S ⊆ A * ,

K i ∩ S = ∅ if and only if SaA * ∈ µ i . ( 4.1)
(1) =⇒ [START_REF] Almeida | Finite semigroups and universal algebra[END_REF]. If µ 0 La µ 1 , then, µ 0 L µ 1 since L ⊆ L a . The second part of ( 2) is trivially satisfied if K 0 = ∅. Thus we will now assume that K 0 is nonempty. Then since A * = βA * , K 0 ∩ A * is also nonempty and (4.1) shows that A * aA * ∈ µ 0 . Since µ 0 La µ 1 , one also gets A * aA * ∈ µ 1 and again by (4.1), K 1 , which is equal to K 1 ∩ A * , is nonempty. Let γ 0 ∈ K 0 . We claim that the set

S = {K 1 ∩ L | L ∈ γ 0 ∩ L} has the finite intersection property. Since, for L 1 , L 2 ∈ L, L 1 ∩ L 2 = L 1 ∩ L 2 ,
S is closed under finite intersection and it suffices to prove that S does not contain the empty set. But if L ∈ γ 0 ∩ L, then γ 0 ∈ L and thus K 0 ∩ L = ∅. It follows by (4.1) that LaA * ∈ µ 0 . Now since µ 0 La µ 1 , one also gets LaA * ∈ µ 1 and again by (4.1), K 1 ∩ L = ∅. It follows that the elements of S are all nonempty, which proves the claim. Since C(βA * ) is compact, the intersection of all elements of S is nonempty. Let γ 1 be an element of this intersection. Then since A * ∈ γ 0 ∩ L, one gets in particular

γ 1 ∈ K 1 ∩ A * = K 1 .
It just remains to show that γ 0 L γ 1 . Let L ∈ L. If L ∈ γ 0 , then L ∈ γ 0 ∩ L and thus K 1 ∩ L ∈ S by definition of S. Since γ 1 belongs to all elements of S, we get in particular γ 1 ∈ K 1 ∩ L. It follows that γ 1 ∈ L and thus L ∈ γ 1 as required.

(2) =⇒ [START_REF] Almeida | Residually finite congruences and quasi-regular subsets in uniform algebras[END_REF]. Suppose that (2) holds. Since µ 0 L µ 1 , it just remains to prove that, if L ∈ L and LaA * ∈ µ 0 , then LaA * ∈ µ 1 . Since LaA * ∈ µ 0 , it follows from (4.1) that K 0 ∩ L is nonempty. Let γ 0 ∈ K 0 ∩ L. Now, by (2) there exists γ 1 ∈ K 1 such that γ 0 L γ 1 . Since γ 0 ∈ L, one gets γ 1 ∈ L and hence γ 1 ∈ K 1 ∩ L. It follows by (4.1) that LaA * ∈ µ 1 as required.

Since L 1 is the join of the lattices L a , for a ∈ A, one gets the following corollary.

Corollary 4.2. Let µ 0 , µ 1 ∈ βA * . The following conditions are equivalent:

(1) The lattice L 1 satisfies the inequality µ 0 µ 1 , (2) The lattice L satisfies the inequality µ 0 µ 1 and, for each letter a and for each a-prefix γ 0 of µ 0 , there exists an a-prefix γ 1 of µ 1 such that L satisfies the inequality γ 0 γ 1 .

Profinite inequalities.

The counterparts of Theorem 4.1 and Corollary 4.2 for a lattice L of regular languages are stated below.

Theorem 4.3. Let u 0 , u 1 ∈ A * . The following conditions are equivalent:

(1) The lattice L a satisfies the inequality u 0 u 1 , (2) The lattice L satisfies the inequality u 0 u 1 and, for each a-prefix v 0 of u 0 , there exists an a-prefix v 1 of u 1 such that L satisfies the inequality v 0 v 1 .

Corollary 4.4. Let u 0 , u 1 ∈ A * . The following conditions are equivalent:

(1) The lattice L 1 satisfies the inequality u 0 u 1 , (2) The lattice L satisfies the inequality u 0 u 1 and, for each letter a and each a-prefix v 0 of u 0 , there exists an a-prefix v 1 of u 1 such that L satisfies the inequality v 0 v 1 .

A base of profinite inequalities for L 1

In this section, we assume that L is a Boolean algebra of regular languages closed under quotients. In this case, L 1 is a lattice of regular languages closed under quotients. It follows that the set of profinite inequalities satisfied by L 1 is closed under translations: if u 0 u 1 is satisfied by L 1 , then, for all x, y ∈ A * , the inequality xu 0 y xu 1 y is also satisfied by L 1 .

A set E of profinite inequalities is a base for L 1 if L 1 is the smallest lattice of regular languages closed under quotients satisfying the inequalities of E. The aim of this section is to produce such a base of profinite inequalities.

As a Boolean algebra, L satisfies the profinite inequality u 0 u 1 if and only if it satisfies u 0 = u 1 . The profinite inequalities satisfied by L 1 are described by Corollary 4.4: u 0 L 1 u 1 if and only if (u 0 , u 1 ) satisfies the following conditions:

(C 1 ) u 0 = L u 1 (C 2 )
for each letter a and each a-prefix v 0 of u 0 , there exists an a-prefix v 1 of u 1 such that v 0 L v 1 . Let us consider the following subsets of A * × A * :

E 1 (L) = {(zx 2 , zx) | x, z ∈ A * and z = L zx} E 2 (L) = {(z, zx) | x, z ∈ A * and z = L zx} E 3 (L) = {(zx 0 x 1 , zx 1 x 0 ) | x 0 , x 1 , z ∈ A * and z = L zx 0 = L zx 1 } E(L) = E 1 (L) ∪ E 2 (L) ∪ E 3 (L)
Let us first verify that the inequalities defined by E(L) are all satisfied by L 1 .

Proposition 5.1. Each profinite inequality u 0 u 1 such that (u 0 , u 1 ) ∈ E(L) satisfies Conditions (C 1 ) and (C 2 ) and hence is satisfied by L 1 . This is mainly a consequence of the equidivisibility of A * .

Proof. (1) Suppose that (u 0 , u 1 ) ∈ E 1 (L). Then there exist x, z ∈ A * such that u 0 = zx 2 , u 1 = zx and z = L zx. It follows zx 2 = L zx and thus

u 0 = L u 1 .
Let a be a letter of

A. If v 0 a is a prefix of zx 2 , then either v 0 a is a prefix of zx or zx is a prefix of v 0 . z x x z x p x v 0 a v 0 a First case. Second case.
In the first case, it suffices to take v 1 = v 0 to get an a-prefix of zx such that v 0 = L v 1 . In the second case, v 0 = zxp for some p such that pa is a prefix of

x. Let v 1 = zp. Then v 1 a = zpa is a prefix of zx and since z = L zx, v 0 = L v 1 .
(2) Suppose that (u 0 , u 1 ) ∈ E 2 (L). Then there exist x, z ∈ A * such that u 0 = z, u 1 = zx and z = L zx. Thus the condition u 0 = L u 1 is trivially satisfied.

Let a be a letter of A. If v 0 a is a prefix of z, then v 0 a is also a prefix of zx and it suffices to take v 1 = v 0 to satisfy (C 2 ).

(3) Suppose that (u 0 , u 1 ) ∈ E 3 (L). Then there exist x 0 , x 1 , z ∈ A * such that

u 0 = zx 0 x 1 , u 1 = zx 1 x 0 and z = L zx 0 = L zx 1 . It follows zx 0 x 1 = L zx 1 = L z = L zx 0 = L zx 1 x 0 and thus u 0 = L u 1 .
Let a be a letter of A. If v 0 a is a prefix of zx 0 x 1 , then either v 0 a is a prefix of zx 0 or zx 0 is a prefix of v 0 .

z x 0 p x 1 z x 0 p x 1 v 0 a v 0 a First case. Second case.
In the first case, v 0 = zp for some p such that pa is a prefix of x 0 . Let

v 1 = zx 1 p. Then v 1 a = zx 1 pa is a prefix of zx 1 x 0 and since z = L zx 1 , v 0 = L v 1 .
In the second case, v 0 = zx 0 p for some p such that pa is a prefix of

x 1 . Let v 1 = zp. Then v 1 a = zpa is a prefix of zx 1 x 0 and since z = L zx 0 , v 0 = L v 1 .
We can now state the main result of this section.

Theorem 5.2. The inequalities of the form u 0 u 1 such that (u 0 , u 1 ) ∈ E(L) form a base of profinite inequalities for L 1 . Alternatively, the equalities u 0 = u 1 such that (u 0 , u 1 ) ∈ E 1 (L) ∪ E 3 (L) the inequalities u 0 u 1 such that (u 0 , u 1 ) ∈ E 2 (L) form another base for L 1 .

We first show that the two sets of inequalities proposed in the statement define the same lattice of regular languages (Proposition 5.3).

Proposition 5.3. The two sets of inequalities proposed in the statement of Theorem 5.2 define the same lattice of regular languages.

Proof. Since the second set is larger than the first one, it suffices to show that the inequalities of the second set can be deduced from those of the first set.

The equation zx = zx 2 is equivalent to zx 2 zx and zx zx 2 . The inequality zx 2 zx is given by E 1 (L) and the other one is a consequence of z zx, an inequality given by E 2 (L). Finally, the equation zx 0 x 1 = zx 1 x 0 follows from the inequalities zx 0 x 1 zx 1 x 0 and zx 1 x 0 zx 0 x 1 , both given by E 3 (L).

The end of the proof relies on a technical tool, the derived category of a relational morphims, and on Simon's theorem on free categories over a graph, or more precisely, its ordered version.

Derived category of a relational morphism. We refer to [START_REF] Rhodes | The kernel of monoid morphisms[END_REF][START_REF] Rhodes | The q-theory of finite semigroups[END_REF][START_REF] Steinberg | Categories as algebra. II[END_REF][START_REF] Tilson | Categories as algebra: an essential ingredient in the theory of monoids[END_REF] for more details on this topic. The ordered version was first introduced in [START_REF] Pin | Ordered categories and ordered semigroups[END_REF].

Let M and N be finite ordered monoids and let τ : M → N be a relational morphism. We define a category C τ as follows: its objects are the elements of N and its arrows are of the form

n 0 n 1 (m, n)
where n ∈ τ (m) and n 1 = n 0 n. Composition of arrows is obtained by multiplying their labels:

n 0 n 1 n 2 n 0 n 2 (m, n) (m ′ , n ′ ) (mm ′ , nn ′ ) =
The identity at the object n, denoted by 1 n , is the arrow

n (1, 1)
Two arrows are coterminal if they have same origin and same end. Given two coterminal arrows from n 0 to n 1 , we write

n 0 n 1 (m, n) n 0 n 1 (m ′ , n ′ )
if, for every m 0 ∈ τ -1 (n 0 ), one has m 0 m m 0 m ′ . This defines a preorder on the set of arrows of C τ which is compatible with the product in C τ .

Let ∼ be the congruence associated with . Thus

n 0 n 1 (m, n) n 0 n 1 ∼ (m ′ , n ′ )
if, for all m 0 ∈ τ -1 (n 0 ), one has m 0 m = m 0 m ′ . The derived category of τ , denoted D τ , is the quotient of C τ by ∼. The ordered derived category of τ is the derived category equipped with the order induced by the preorder in C τ .

A result on finite ordered categories Let C be a category and let p be an arrow of the free category over C (that is, a path in the directed graph C). We denote by c(p) the content of p, that is, the set of arrows occurring in p. The following statement [START_REF] Pin | Ordered categories and ordered semigroups[END_REF]Prop. 4.2] is the counterpart for ordered categories of a celebrated theorem of I. Simon on categories. Sketch of the proof of Theorem 5.2. We first give a slightly more precise result when L is a finite Boolean algebra (Proposition 5.5). The general case follows by a compactness argument (omitted).

Proposition 5.5. Let L be a finite Boolean algebra regular languages of A * closed under quotients. Then L 1 is defined by the set of inequalities

u 0 u 1 such that (u 0 , u 1 ) ∈ E(L) ∩ (A * × A * ). Proof. Let E ′ (L) = E(L) ∩ (A * × A * ).
Let L be a regular language of A * satisfying the inequalities defined by E ′ (L). Let us show that L satisfies all the inequalities u 0 u 1 such that Conditions (C 1 ) and (C 2 ) are satisfied. Then n 0 ∈ τ (m 0 ), n 1 ∈ τ (m 1 ) and n = nn 0 = nn 1 . Let z, x 0 and x 1 be words of A * such that η(z) = n, η(x 0 ) = n 0 , µ(x 0 ) = m 0 , η(x 1 ) = n 1 and µ(x 1 ) = m 1 . Then η(zx 0 ) = η(zx 1 ) = η(z), which means that zx 0 = L zx 1 = L z. Since L satisfies the inequalities defined by E ′ (L), one has µ(z) µ(zx 0 ) = µ(zx 2 0 ) and µ(zx 0 x 1 ) = µ(zx 1 x 0 ). Consequently, 1 n r, r 2 ∼ r and rs ∼ sr, which proves the claim. We can now apply Proposition 5.4 to the ordered derived category of τ . Let (u 0 , u 1 ) ∈ A * × A * satisfying Conditions (C 1 ) and (C 2 ).

Let L = {L 1 , • • • , L n }. For 1 i n, let η i : A * → M i be the syntactic morphism of L i and let η : A * → M 1 × • • • × M n be the diagonal morphism defined by η(u) = (η 1 (u), . . . , η n (u)). Let µ : A * → M
With each w = a 1 • • • a n ∈ A * , where a 1 , . . . , a n ∈ A, we associate a path p(w) in D τ as follows: ------------→ η(w). Now u 0 = L u 1 if and only if η(u 0 ) = η(u 1 ), Condition (C 1 ) is equivalent to p(u 0 ) and p(u 1 ) be coterminal, and (C 2 ) is equivalent to c(p(u 0 )) ⊆ c(p(u 1 )). It follows now from Proposition 5.4 that p(u 0 ) p(u 1 ). This means that µ(zu 0 ) µ(zu 1 ) for any z ∈ η -1 (1) and hence µ(u 0 ) µ(u 1 ). Thus L satisfies u 0 u 1 .

Conclusion.

The programme would now be to extend the known results on operations on regular languages to the framework of lattices. So far, only the polynomial closure was understood [START_REF] Branco | Equations for the polynomial closure[END_REF]. This paper solves the case of one-step products, but a challenging problem would be to extend the results of [START_REF] Pin | Profinite semigroups, Mal'cev products and identities[END_REF][START_REF] Straubing | Aperiodic homomorphisms and the concatenation product of recognizable sets[END_REF]

4 .

 4 a-prefixes in A * . It follows from[START_REF] Pin | A topological approach to transductions[END_REF] Theorem 4.1] that a map f : A * → C( A * ) is uniformly continuous if and only if, for every regular language L, f -1 (L) is a regular language 2 . Since p - a (L) = LaA * by Proposition 3.1, this condition is trivially satisfied by p a and hence p a extends uniquely to a (uniformly) continuous map p a : A * → C( A * ). The next proposition gives a direct definition of p a . Proposition 3.2. For each u ∈ A * , p a (u) = {v ∈ A * | there exists w ∈ A * such that u = vaw}. Inequalities for L a , and L 1

Proposition 5 . 4 . 1 )

 541 Let C be a finite ordered category. The following conditions are equivalent: (The local monoids of C satisfy the monoid identities x 2 = x, xy = yx and 1 x. (2) C satisfies the inequality x y for any coterminal arrows x and y of the free category over C such that c(x) ⊆ c(y).

  be the syntactic morphism of L. Finally, let N = η(A * ) and let τ be the relational morphism η • µ -1 : M → N . We claim that every local monoid of D τ satisfies the inequalities x 2 = x, xy = yx and x 1. Let n ∈ N and consider two loops r = (n, (m 0 , n 0 ), n) and s = (n, (m 1 , n 1 ), n) around n. n (m 0 , n 0 ) (m 1 , n 1 )

1 [( 1 ,

 11 a 1 )]∼ -----→ η(a 1 ) [(η(a 1 ),a 2 )]∼ --------→ η(a 1 a 2 ) • • • [(η(a 1 •••a n-1 ),an)]∼

  Definition 2.2. Let E be a set of ultrafilter inequalities. A subset of B satisfies E if it satisfies every inequality of E. The set of languages defined by E is the set of all languages satisfying E. Theorem 2.3. A subset L of B is a sublattice of B if and only if it can be defined by a set of ultrafilter inequalities of the form µ 0 µ 1 , where µ 0 and µ 1 are ultrafilters of B.

	The following result is a consequence of Stone duality, see [14, Theorem 5.1]
	or [22, Theorem 8.3].

  to lattices.

	Classes of languages →	(Positive)	Lattices of
	↓ Operations	Varieties	regular languages
	Lattice generated by one step products	[28, Th. 4.6]	This paper
	Polynomial closure	[27]	[8]
	Closure under product and Boolean operations	[35, 26]	Open

Contrary to a frequent convention, we do include the empty set in C(X).

This is actually a variation on some general results of[START_REF] Michael | Topologies on spaces of subsets[END_REF] and[START_REF] Smyth | Power domains and predicate transformers: a topological view[END_REF] Theorem 1]. See also[START_REF] Bonsangue | Relating multifunctions and predicate transformers through closure operators[END_REF] for a nice survey.

The first author received financial support of FCT, through project UID/MULTI/04621/2013 of CEMAT-Ciências.

The second author received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 670624) and is supported by the DeLTA project (ANR-16-CE40-0007).

Email address: Jean-Eric.Pin@irif.fr