Aloïs Dreyfus

Pierre-Cyrille Héam

Olga Kouchnarenko

Random Grammar-based Testing for Covering All Non-Terminals

Keywords:

In the context of software testing, generating complex data inputs is frequently performed using a grammar-based specification. For combinatorial reasons, an exhaustive generation of the data -of a given size -is practically impossible, and most approaches are either based on random techniques or on coverage criteria. In this paper, we show how to combine these two techniques by biasing the random generation in order to optimise the probability of satisfying a coverage criterion.

I. INTRODUCTION

A. Motivation

Producing trusted software is a central issue in software engineering. Testing remains an inescapable step to ensure software quality. In reaction to the limitations of manual testing, recent years have seen a rise in the research interest for systematic testing frameworks grounded in theory. Random testing is a natural approach, empirically known to detect many kinds of bugs. However, by definition, low-probability behaviours cannot be adequately tested in that way. Conversely, non-random testing tends to focus on a few edge cases of particular interest to the tester, at the expense of all others. Indeed, it can cover various behaviours, but their choice depends on tester's priorities and, in general, each behaviour is tested in a unique way.

In [START_REF] Kouchnarenko | Coverage-biased random exploration of large models and application to testing[END_REF], it is explained how to bias a uniform random testing approach using constraints given by a coverage criterion, in order to optimise the probability of satisfying this criterion. The technique is developed for path generation in a graph. The contribution of the present paper consists in enriching this approach with a coverage criterion on non-terminal symbols of the grammar, allowing the user to apply it to grammar-based testing.

B. Related Work

Grammar-based testing is frequently used for generating structured inputs, as in [START_REF] Purdom | A sentence generator for testing parsers[END_REF] for parser testing or in [START_REF] Daniel | Automated testing of refactoring engines[END_REF] to test refactoring engines (program transformation software). Systematic combinatorial approaches [START_REF] Coppit | Yagg: an easy-to-use generator for structured test inputs[END_REF] lead to a huge number of sequences, and symbolic approaches are frequently preferred [START_REF] Lämmel | Controllable combinatorial coverage in grammar-based testing[END_REF], [START_REF] Majumdar | Directed test generation using symbolic grammars[END_REF], [START_REF] Godefroid | Grammar-based whitebox fuzzing[END_REF]. In [START_REF] Xu | A toolkit for generating sentences from context-free grammars[END_REF], a generic tool for generating test data from grammars has been proposed. This tool does not provide any random feature but is based on rule coverage algorithms and techniques, as defined in [START_REF] Purdom | A sentence generator for testing parsers[END_REF], [START_REF] Lämmel | Grammar testing[END_REF], [START_REF] Zheng | A sentence generation algorithm for testing grammars[END_REF], [START_REF] Alves | A case study in grammar engineering[END_REF].

Random test generation techniques -initially proposed in [START_REF] Duran | A report on random testing[END_REF], [START_REF] Hamlet | Random testing[END_REF] -are frequently used for practical reasons, as in [START_REF] Godefroid | DART: directed automated random testing[END_REF], [START_REF] Oriat | Jartege: A tool for random generation of unit tests for java classes[END_REF], [START_REF] Kouchnarenko | Coverage-biased random exploration of large models and application to testing[END_REF]. Combining random generation and grammarbased testing is explored in [START_REF] Mckenzie | Generating string at random from a context-free grammar[END_REF], [START_REF] Hickey | Uniform random generation of strings in a context-free language[END_REF], [START_REF] Maurer | The design and implementation of a grammar-based data generator[END_REF], [START_REF] Héam | Seed: An easy-to-use random generator of recursive data structures for testing[END_REF], [START_REF] Dadeau | On the use of uniform random generation of automata for testing[END_REF], [START_REF] Héam | A random testing approach using pushdown automata[END_REF], without exploiting any coverage criteria, or using an isotropic random walk as in [START_REF] Enderlin | Grammarbased testing using realistic domains in php[END_REF].

C. Layout

Section II presents the notions and notations used in this paper. Section III explains how to optimise random testing to satisfy a given coverage criterion. The theoretical contributions are provided in Section IV, which shows how to use this technique to optimise the coverage of non-terminal symbols in a grammar-based testing context. An illustrating example is developed in Section V. Finally, Section VI concludes.

II. FORMAL BACKGROUND

A. Context-free Grammars and Random Generation

In this paper, the cardinality of a finite set S is denoted |S|.

a) Context-free Grammars: A context-free grammar is a tuple G = (Σ, Γ, S 0 , R), where Σ and Γ are disjoint finite alphabets, S 0 ∈ Γ is the initial symbol, and R is a finite subset of Γ×(Σ∪Γ) * . The elements of Σ are called terminal symbols, and the elements of Γ are called non-terminal symbols. An element (X, u) of R is called a rule of the grammar and is frequently denoted 1 of the grammar G is a finite sequence x 0 , . . . , x k of words of (Σ ∪ Γ) * such that x 0 = S 0 , x k ∈ Σ * and for every i, x i+1 is a successor of x i . A derivation tree of G is a finite tree whose internal nodes are labelled by letters of Γ, whose leaves are labelled by elements of Σ ∪ {ε}, whose root is labelled by S 0 and satisfying: if a node is labelled by X ∈ Γ and its children are labelled by α 1 , . . . , α k (in this order), then either α 1 = ε and k = 1, or all the α i 's are in Γ∪Σ and (X, α 1 . . . α k ) ∈ R. The size of a derivation tree is given by the number of tree nodes. Note that there is a bijection between the set of complete derivations of a grammar and the set of derivation trees of this grammar. For a context-free grammar G, E n (G) denotes the number of derivation trees of G with n nodes. A derivation tree covers an element X of Γ if at least one of its nodes is labelled by X. For instance, for the tree in Example 1, the elements S and T are covered since they appear in the derivation tree.

X → u. A word w ∈ (Σ ∪ Γ) * is a successor of v ∈ (Σ ∪ Γ) * for the grammar G if there exist v 0 ∈ Σ * , v 1 , v 2 ∈ (Σ ∪ Γ) * , S ∈ Γ such that v = v 0 Sv 1 and w = v 0 v 2 v 1 and S → v 2 ∈ R. A complete derivation
b) Uniform Random Generation: The present issue is, given a positive integer and a context-free grammar, to compute randomly with a uniform distribution a derivation tree of size n of this grammar. We will briefly explain here how to tackle this problem by using well-known counting techniques [START_REF] Flajolet | Analytic Combinatorics[END_REF]. Notice that more advanced techniques allow a faster computation, like in [START_REF] Denise | Uniform random generation of decomposable structures using floating-point arithmetic[END_REF].

As usual, the non-terminals symbols are denoted by capital letters. Given a context-free grammar G = (Σ, Γ, S 0 , R), a non-terminal symbol X in Γ, and a positive integer i, the number of derivation trees of size i generated by (Σ, Γ, X, R) is denoted by x(i), i.e., using the corresponding lowercase letter.

Given a positive integer n, for each symbol S ∈ Γ, the sequence of positive integers s(1), . . . , s(k), . . . is introduced. The recursive computation of these s(i)'s is as follows. For each strictly positive integer k and each rule r = (S, w 1 S 1 . . . w n S n w n+1 ) ∈ R, with w j ∈ Σ * and S i ∈ Γ, let us set

             β r = 1 + n+1 i=1 |w i | α r (k) = i1+i2+...+in=k-βr j=n j=1 s j (i j ) if n = 0 α r (k) = 0 if n = 0 and k = β r α r (β r ) = 1 if n = 0. It is known [23, Theorem I.1] that s(k) = r∈R∩(S×(Σ∪Γ) * ) α r (k).
Since, by hypothesis, there is no rule of the form (S, T ) in R, with S, T ∈ Γ, all i j 's involved in the definition of β r are strictly less than k. This way, the s(i)'s can be recursively computed. Consider for instance the grammar ({a, b}, {X}, X, {r 1 , r 2 , r 3 }) with r 1 = (X, XX) r 2 = (X, a) and r 3 = (X, b). One has where both Z 1 and Z 2 are derivation trees of size 2.

β r1 = 1 + 0 = 1, β r2 = 1 + 1 = 2, β r3 = 1+1 = 2. Therefore x(k) = i+j=k-1 x(i)x(j) if k = 2, and x(2) = 1 + 1 + i+j=2-1 x(i)x(j) = 2, other- wise. It follows that x(1) = 0, x(2) = 2, x(3) = x(1)x(1) = 0, x(4) = x(1)x(2) + x(2)x(1) = 0, x(5) = x(2)x(2) = 4,
In order to generate derivation trees of size n, all s(i) ′ s, for S ∈ Γ and i ≤ n, have to be computed with the

Random Generation

Input: G = (Σ, Γ, X, R) a context-free grammar, n a strictly positive integer. Output: a derivation tree t of G size n. Algorithm:

1. Let {r 1 , r 2 , . . . , r ℓ } be set of the elements of R whose first element is X.

2. If j=ℓ j=1 α rj (n) = 0, then return "Exception". 3. Pick i ∈ {1, . . . , ℓ} with probability P rob(i = j) =

αr i (n) j=ℓ j=1 αr j (n) . 4. Let r i = (X, Z 1 . . . Z k ), with Z j ∈ Σ ∪ Γ. 5. Root symbol of t is X. 6. Children of t are Z 1 , . . . , Z k in this order. 7. Let {i 1 , . . . , i m } = {j | Z j ∈ Γ}. 8. Pick (x 1 , . . . , x m ) ∈ N m such that x 1 + . . . + x m = n -β ri with probability P rob(x 1 = ℓ 1 , . . . , x m = ℓ m ) = j=m j=1 z ij (ℓ j ) α ri (n) .
9. For each i j , the i j -th sub-tree of T is obtained by running the Random Generation algorithm on (Σ, Γ, Z ij , R) and ℓ j .

10. Return t. above method. This can be performed in polynomial time. Afterwards, the random generation is done recursively using the given algorithm in Fig. 1. It is known [START_REF] Flajolet | Analytic Combinatorics[END_REF] that this algorithm provides a uniform generation of derivation trees of size n, i.e. each derivation tree occurs with the same probability. Note that an exception is raised at Step 2 if there is no element of the given size. For the example presented before, there is no element of size 3, then it is impossible to generate a derivation tree of size 3. Running the algorithm on this example with n = 2, one considers at Step 1 the set {r 1 , r 2 , r 3 } since all these rules have X as left element. Since

α r1 (2) = 0, α r2 (2) = 1, α r3 (2) = 1, at Step 3 the probability that i = 1 is 0, the probability that i = 2 is 1/2 and the probability that i = 3 is 1/2. If i = 2 is
picked, the generated tree has X as root symbol and a as unique child. Running the algorithm on this example with n = 3 stops at Step 2 since there is no tree of size 3. When running the algorithm on this example with n = 5, the set {r 1 , r 2 , r 3 } is considered at Step 1. Since α r1 (5) = 4, α r2 (5) = 0, α r3 (5) = 0, i = 1 is picked with probability 1. Therefore, the tree has X as root symbol, and its two children are both labelled by X. Therefore, at Step 7, the considered set is {1, 2}. At Step 8, one has nβ r1 = 5 -1 = 4. The probability that i 1 = 1 and i 2 = 3 is 0 since x(1) = 0. Similarly, the probability that i 1 = 3 and i 2 = 1 is 0 too. Now the probability that i 1 = 2 and i 2 = 2 is 1. Afterwards the algorithm is recursively executed on each child with n = 2: each of the 4 trees is chosen with probability 1/4.

III. MIXING RANDOM TESTING AND COVERAGE

CRITERIA In a context of functional testing, the strength of random testing is to quickly provide many different test data, for each behaviour of the system. Moreover, these test data are independent of the choices of the test designer, and consequently they can catch problem (s)he did not anticipate. For instance, fuzz testing is particularly relevant for testing security requirements [START_REF] Godefroid | Grammar-based whitebox fuzzing[END_REF]. However, random testing can miss an important behaviour occurring with a very small probability. To exploit the advantages of both random testing and deterministic testing, a solution is to combine random generation and coverage criteria.

The general schema for this combination, as described in [START_REF] Kouchnarenko | Coverage-biased random exploration of large models and application to testing[END_REF], is the following: considering a random generation algorithm of test data of size n and a coverage criteria C (each element of C is or is not covered by each possible test), the goal is to use the generation algorithm N times in order to optimise the probability of covering all elements of C. For each element e ∈ C, we denote by p e,n the probability that a generated test of size n covers e. One can easily check that generating N test data independently of C provides a probability of covering C of 1-(1-p min ) N , where p min = min e∈C {p e,n }. This probability is the way to measure the quality of the testing approach, relatively to C. A better way is to repeat N times the following procedure:

1) Pick at random an element e ∈ C with a probability π e , and 2) Generate uniformly a test of size n covering e. This procedure requires to know how to uniformly generate a test of size n covering a given element, and to choose the probabilities π e 's to optimise the probability of covering all elements of C.

Following [START_REF] Kouchnarenko | Coverage-biased random exploration of large models and application to testing[END_REF], the optimisation requires solving the following constraint system: maximise p satisfying p ≤ e∈C π e p e,f,n pe,n for all f ∈ C e∈C π e = 1 where p e,f,n is the probability that a randomly generated test of size n covers both e and f . This linear programming problem can be solved in an efficient way, using simplex-like approaches.

In summary, in order to combine random testing and a coverage criterion, it is required to solve a constraint system and to know 1) how to randomly generate a test of a given size covering a given element, 2) how to compute the p e,n 's; and 3) how to compute the p e,f,n 's.

The rest of the paper is dedicated to the problem of the random generation of execution trees of a grammar, with the coverage criterion All non-terminal symbols. More precisely, given a grammar G = (Σ, Γ, S 0 , R), the coverage criterion being Γ, a test of size n being a derivation tree of G of size n, we say that X ∈ Γ is covered by a test if the derivation tree covers X.

IV. COMPUTING p X,n AND p X,Y,n

In this section G = (Σ, Γ, S 0 , R) is a context-free grammar. We denote by E n (G) the set of derivation trees of size n of G. We respectively denote by E X,n (G) and E X,Y,n (G) the set of derivation trees of size n of G covering X, and covering both X and Y .

Let p X,n be the probability of a randomly generated derivation tree of size n to cover X.

Clearly, if E n (G) is empty then p X,n = 0 [resp. p X,Y,n = 0]. Otherwise, p X,n = |EX,n(G)| |En(G)| [resp. p X,Y,n = |EX,Y,n(G)| |En(G)| ].
Therefore, computing the probability defined in Section III -needed to solve the linear constraint program -reduces to the computation of the cardinality of sets E X,n (G) and E X,Y,n (G).

A. Computing |E X,n (G)| and |E X,Y,n (G)| To compute |E X,n (G)|, we build a grammar G X such that E n (G X
) and E X,n (G) are in bijection (and therefore have the same number of elements).

For every w ∈ (Γ ∪ Σ) * , [w] 0 is recursively defined by:

[ε] 0 = ε, [Zw] 0 = (Z, 0)[w] 0 (with Z ∈ Γ) and [aw] 0 = a[w] 0 (with a ∈ Σ).
Intuitively, [w] 0 is obtained from w by changing each letter of w in Γ by the corresponding pair with 0 as second element. For instance, with the grammar of Example 1, one has [aSbbT ] 0 = a(S, 0)bb(T, 0). For every w ∈ (Γ ∪ Σ) * , [w] 2 is defined exactly in the same way, changing all 0's by 2's.

For every w ∈ (Γ∪Σ) * , {w} 1,2 is defined as the set of words w ′ ∈ (Σ ∪ Γ × {1, 2}) * obtained from w by replacing occurrence of each letter Z of Γ either by (Z, 1) or by (Z, 2), with the restriction that at least one is replaced by (Z, 1). The letters in Σ remain unchanged. For instance, if w = aSbT , then {w} 1,2 = {a(S, 1)b(T, 1), a(S, 2)b(T, 1), a(S, 1)b(T, 2)}. Notice that if w ∈ Σ * then {w} 1,2 = ∅ since the constraint is not satisfied.

Let G X = (Σ, Γ×{0, 1, 2}, (S 0 , 1), R X ) where

R X = R 0 ∪ R 1 ∪ R ′ 1 ∪ R 2 with: • R 0 = {(Z, 0) → [w] 0 | Z → w ∈ R}, • R 1 = {(Z, 1) → w ′ | Z = X and ∃Z → w ∈ R such that w ′ ∈ {w} 1,2 }, • R ′ 1 = {(X, 1) → [w] 0 | X → w ∈ R}, • R 2 = {(Z, 2) → [w] 2 | Z → w ∈ R and Z = X}.
Intuitively, adding the value 0 to a symbol in Γ means that if this rule is used, there exists an occurrence of X at an upper position in the derivation tree. Adding the value 1 to a symbol in Γ means that there is no occurrence of X at an upper position, but there exists an occurrence of X at this or a lower position in the derivation tree. The value 2 means there is no occurrence of X appearing in the tree at an upper or lower position.

Example 2 -G X . Consider the grammar G = ({a, b}, {S, T, X}, S, R) with R = {S → SS, S → aT, S → Xb, T → aa, X → T X, X → b}. The grammar G X has the set of rules as follows: {(S, 0) → (S, 0)(S, 0), (S, 0) → a(T, 0), (S, 0) → (X, 0)b, (T, 0) → aa, (X, 0) → b, (X, 0) → (T, 0)(X, 0)} ∪ {(S, 1) → (S, 1)(S, 1), (S, 1) → (S, 1)(S, 2), (S, 1) → (S, 2)(S, 1), (S, 1) → a(T, 1), (S, 1) → (X, 1)b} ∪ {(X, 1) → b, (X, 1) → (T, 0)(X, 0)} ∪ {(S, 2) → (S, 2)(S, 2), (S, 2) → a(T, 2), (S, 2) → (X, 2)b, (T, 2) → aa}.

Proposition 1 -Bijection. There exists a bijection between E n (G X ) and E X,n (G).

Example 3 illustrates several elements of the following proof.

Proof: Let ϕ be the function from (Γ × {0, 1, 2} ∪ Σ) * into (Γ ∪ Σ) inductively defined by: ϕ(ε) = ε and ϕ(aw

) = aϕ(w) if a ∈ Σ ∪ Γ and ϕ((Z, α)w) = Zϕ(w) if Z ∈ Γ and α ∈ {0, 1, 2}. Intuitively, ϕ is a projection deleting the components in {0, 1, 2}. By construction of G X , if (Z, α) → w is a rule of G X then ϕ((Z, α)) → ϕ(w) is a rule of G. Therefore, if x 0 , . . . , x k is complete derivation of G X , then ϕ(x 0 ), . . . , ϕ(x k ) is a complete derivation of G. Moreover, the initial symbol of G X is (S, 1
) and all rules of R X with a left hand side in (Γ \ {X}) × {1} have a right hand side where an element of Γ × {1} occurs. Therefore, since x k ∈ Σ * , the only way to destroy the component 1 is to use a rule with the left hand side (X, 1). It follows that the derivation tree associated to ϕ(x 0 ), . . . , ϕ(x k ) covers X.

Consequently, ϕ induces a function from

E n (G X ) into E X,n (G). Let x 0 , . . . , x k and x ′ 0 , . . . , x ′ k be complete deriva- tions of G X , such that ϕ(x 0 ), . . . , ϕ(x k ) = ϕ(x ′ 0 ), . . . , ϕ(x ′ k ). Assuming that x 0 , . . . , x k = x ′ 0 , . . . , x ′ k , there exists a minimal index i 0 such that x i0 = x ′ i0 . Since x 0 = (S 0 , 1) = x ′ 0 , i 0 ≥ 1. Therefore x i0-1 = x ′ i0-1 exists. Set x i0-1 = v 0 (Z, α)v 1
, with Z ∈ Γ and α ∈ {0, 1, 2}. One of the following cases arises:

• If α = 0, then there exist Z → w and Z → w ′ in R such that x i0 = v 0 [w] 0 v 1 and x ′ i0 = v 0 [w ′ ] 0 v 1 . Since ϕ(x i0 ) = ϕ(x ′ i0 ), it follows that ϕ([w] 0 ) = ϕ([w′] 0 ). But ϕ([w] 0 ) = w and ϕ([w ′ ] 0 ) = w ′ , proving that x i0 = x ′ i0 , a contradiction. • If α = 2,
then the same proof holds, replacing 0 by 2.

• If α = 1 and Z = X, then, again, the same proof holds.

• If α = 1 and Z = X, then there exist Z → w and Z → w ′ in R such that

x i = v 0 w 1 v 1 and x ′ i = v 0 w 2 v 1 , with w 1 ∈ {w} 1,2 and w 2 ∈ {w ′ } 1,2 . Since ϕ(x i0 ) = ϕ(x ′ i0
), one has w = w ′ . Therefore, w 1 , w 2 ∈ {w} 1,2 . Since w 1 = w 2 , let j be the first letter of w 1 which is different from the corresponding letter in w 2 . By construction of {w} 1,2 , this letter must be in Γ × {1, 2} in both w 1 and w 2 , for instance (T, β 1 ) and (H, β 2 ). Now, since ϕ((T, β 1 )) = ϕ((H, β 2 )), one has T = H. Therefore, without loss of generality we may assume that β 1 = 1 and β 2 = 2. Consequently, x i0 has a prefix of the form v 0 (T, 1): in the derivation tree corresponding to x 0 , . . . , x k , the subtree rooted in this (T, 1) contains an X (by construction of R 1 ). Conversely, x ′ i0 has a prefix of the form v 0 (T, 2): in the derivation tree corresponding to x ′ 0 , . . . , x ′ k , the subtree rooted in this (T, 2) does not contain any X (by construction of R 2 ). It follows that the two corresponding derivations cannot have the same

E n (G X ) into E X,n (G).
Now let y 0 , . . . , y k be complete derivations of G whose corresponding tree t is in E X,n (G). We consider the tree t ′ labelled in Γ × {0, 1, 2} ∪ Σ which has exactly the same structure (the same set of positions) than t and such that:

• If a node of t is labelled by a letter of Σ, then the corresponding node in t ′ has the same label. • If a node ρ of t is labelled by a letter T ∈ Γ, then the node ρ in t ′ is labelled by (T, 1) if there is no X on the path from the root to ρ (excluding ρ), and if the subtree rooted in ρ (including ρ) contains one ρ, at least. It is labelled by (T, 0) if there is at least one X on the path from the root to ρ. Otherwise, it is labelled by (T, 2). One can check that t ′ corresponds to a complete derivation tree of G X whose image by ϕ is exactly the complete execution corresponding to t, proving that ϕ is surjective, which concludes the proof.

Example 3 -Illustration of the proof of Prop. 1. Consider the grammar G = ({a, b}, {S, T, X}, S, R) with R = {S → SS, S → aT, S → Xb, T → aa, X, → T, X → b} of Example 2. Consider the derivation tree of E X,19 (G) depicted in Fig. 2, corresponding to the complete derivation S, SS, SSS, aT SS, aaaSS, aaaXbS, aaabbS, aaabbXb, aaabbT Xb, aaabbaaXb, aaabbaabb.

The associated derivation in G X is (S, 1), (S, 1)(S, 1), (S, 2)(S, 1)(S, 1), a(T, 2)(S, 1)(S, 1), aaa(S, 1)(S, 1), aaa(X, 1)b(S, 1), aaabb(S, 1), aaabb(X, 1)b, aaabb(T, 0)(X, 0)b, aaabbaa(X, 0)b, aaabbaabb, whose derivation tree from E 19 (G X ) is depicted in Fig. 3.

Using Proposition 1 and the results described in Section I, it is possible to compute |E X,n (G)|. If we denote by ℓ the maximal number of elements of Γ (with multiplicity) occurring in a right hand side of G, then G X has O(2 ℓ |R|) rules, whose sizes are bounded by the maximal size of the rules of G. Therefore if ℓ is reasonable, the computation of |E X,n (G)| is tractable in practice, even for a quite large value of n. As mentioned above, the computation of |E X,n (G)| immediately provides p X,n . It is also important to point out that G X allows the uniform random computation of execution trees of G of a given size and covering X.

Since E X,X,n (G) = E X,n (G), computing |E X,X,n (G)| is a direct application of the above techniques. Computing |E X,Y,n (G)|, with Y = X, can almost be done by a similar construction: the difference is that the construction of the rules of the grammar G XY , from the grammar G X , must take into account that both X and Y have to appear in the derivation. Let G XY = (Σ, Γ × {0, 1, 2} × {0, 1, 2}, ((S 0 , 1), 1), R XY ) where

R XY = R 0 ∪ R 1 ∪ R ′ 1 ∪ R 2 with: • R 0 = {((Z, i), 0) → [w] 0 | (Z, i) → w ∈ R X }, • R 1 = {((Z, i), 1) → w ′ | Z = Y and ∃(Z, i) → w ∈ R X such that w ′ ∈ {w} 1,2 }, • R ′ 1 = {((Y, i), 1) → [w] 0 | (Y, i) → w ∈ R X }, • R 2 = {((Z, i), 2) → [w] 2 | (Z, i) → w ∈ R X and Z = Y }.
A proof similar to the one of Proposition 1 allows showing that there is a computable bijection between E n (G XY ) and E X,Y,n (G). Note that the size of G XY is approximatively 4 ℓ times greater than the size of G.

V. EXPERIMENTS

The approach has been evaluated on a simplified version of the grammar of JSON 2 (for JavaScript Object Notation) -a language independent common format for declaring objects. Formally, let us consider the grammar G = (Σ, Γ, Object, R) with Σ having the eight following elements Σ = {, , {, : , }, letter, digit, [, ]}. The set Γ of non-terminal symbols 3 is composed of the elements ′′ Object ′′ , ′′ M embers ′′ , ′′ P air ′′ , ′′ Array ′′ , ′′ Elements ′′ and ′′ V alue ′′ . Finally, the set R contains the following rules: http://www.json.org/ 3 To provide a more readable specification, the convention consisting in using capital letters for non-terminal symbols is not entirely respected here.

• Object → {} | {M embers} • M embers → P air | P air, M embers • P air → letter : V alue • Array → [ ] | • Elements → V alue | V alue, Elements • V alue → letter | Object | digit | Array
In order to optimise the coverage criterion, we have to solve the following system while maximising p satisfying Using a slightly modified version of the Hoa tool ( [START_REF] Enderlin | Hoa project, a set of php libraries[END_REF]), the computation of the probabilities p X,n and p X,Y,n for all X, Y ∈ Γ and n = 20 has been performed efficiently (a few seconds). The system becomes as below, and we have then to solve it while maximising p satisfying

                                                                                                   p ≤ π Object p Object,
                                                                      
π Object + π Members + π P air + π Array +π Elements + π V alue = 1

This linear programming problem can be solved in an efficient way, using simplex-like approaches. We have used the tool lp solve 4 to solve it, and the result is that p = 1 if π Object = 0, π Members = 0, π P air = 0, π Array = 0, π Elements = 1, and π V alue = 0. It means that, for this simple example, the optimised approach to cover all the nonterminals symbols, consists in generating derivation trees covering Elements. Indeed, in this grammar, the generation of a derivation tree covering the non-terminal symbol Elements provides a tree covering all the other non-terminal symbols.

VI. CONCLUSION

In this paper, we have presented a method for exploiting a coverage criterion together with random testing in the context of grammar-based testing. This automatic method lies in building a grammar and then in resolving a linear constraint system, which can be done by adapted tools, even for large values. In the future, we plan to extend the approach to other coverage criteria such as rules coverage, and also to handle attribute grammars with constraints formalising the semantics of context-free languages.

Example 1 -

 1 Context-free grammar. Let us consider the grammar G = ({a, b}, {S, T }, S, R), with R = {S → T b, S → aSb, T → ε}). The sequence S, aSb, aT bb, abb is a complete derivation of the grammar. The associated derivation tree is

  derivation trees of size 5 are the trees of the formX /\ Z1 Z2

Fig. 1 .

 1 Fig. 1. Random Generation algorithm

Fig. 2 .

 2 Fig. 2. Derivation tree of G -Example 3

Fig. 3 .

 3 Fig. 3. Derivation tree of G X -Example 3

2

 2

  Object + π Members + π P air + π Array + π Elements + π V alue = 1

		Object,n p Object,n	+ π Members	p M embers,Object,n p M embers,n
	+π P air	p P air,Object,n pP air,n	+ π Array	p Array,Object,n pArray,n
	+π Elements	p Elements,Object,n p Elements,n	+ π V alue	p V alue,Object,n p V alue,n
	p ≤ π Object	p Object,M embers,n p Object,n	+ π Members	p M embers,M embers,n p M embers,n
	+π P air	p P air,M embers,n pP air,n	+ π Array	p Array,M embers,n pArray,n
	+π Elements	p Elements,M embers,n p Elements,n	+ π V alue	p V alue,M embers,n p V alue,n
	p ≤ π Object	p Object,P air,n p Object,n	+ π Members	p M embers,P air,n p M embers,n
	+π P air	pP air,P air,n pP air,n	+ π Array	pArray,P air,n pArray,n
	+π Elements	p Elements,P air,n p Elements,n	+ π V alue	p V alue,P air,n p V alue,n
	p ≤ π Object	p Object,Array,n p Object,n	+ π Members	p M embers,Array,n p M embers,n
	+π P air	pP air,Array,n pP air,n	+ π Array	pArray,Array,n pArray,n
	+π Elements	p Elements,Array,n p Elements,n	+ π V alue	p V alue,Array,n p V alue,n
	p ≤ π Object	p Object,Elements,n p Object,n	+ π Members	p M embers,Elements,n p M embers,n
	+π P air	p P air,Elements,n pP air,n	+ π Array	p Array,Elements,n pArray,n
	+π Elements	p Elements,Elements,n p Elements,n	+ π V alue	p V alue,Elements,n p V alue,n
	p ≤ π Object	p Object,V alue,n p Object,n	+ π Members	p M embers,V alue,n p M embers,n
	+π P air	p P air,V alue,n pP air,n	+ π Array	p Array,V alue,n pArray,n
	+π Elements	p Elements,V alue,n p Elements,n	+ π V alue	p V alue,V alue,n p V alue,n
	π


Bogdan Chornomaz

A NON-CAPPED TENSOR PRODUCT OF LATTICES

In the lattice theory the tensor product A ⊗ B is naturally defined on (0, ∨)-semilattices. In general, when restricted to lattices this construction will not yield a lattice. However, if the tensor product A ⊗ B is capped, then A ⊗ B is a lattice. It is stated as an open problem in [4] whether the converse is true.

In the present paper we prove that it is not so, that is, there are bounded lattices A and B such that A ⊗ B is not capped, but is a lattice. Furthermore, A has length three and is generated by a nine-element set of atoms, while B is the dual lattice of A.

Introduction

The tensor product of join-semilattices with zero was introduced in J. Anderson and N. Kimura [START_REF] Anderson | The tensor product of semilattices[END_REF] and G.A. Fraser [START_REF] Fraser | The semilattice tensor product of distributive semilattices[END_REF]. The latter paper, in a category-theoretical style approach, defines it as a free object of a special kind. Although this approach can, in principle, be carried over to lattices, this does not look promising. On the other hand, the original definition of tensor product of semilattices can be restricted to lattices, yielding interesting results and problems. This was performed in a number of papers of G.Grätzer and F.Wehrung [START_REF] Grätzer | Tensor products of semilattices with zero, revisited[END_REF][START_REF] Grätzer | A survey of tensor products and related constructions in two lectures[END_REF][START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

In many natural cases the tensor product of lattices appears to be a lattice, for example when both lattices involved are finite. To generalize this situation, G.Grätzer and F.Wehrung introduced the notion of capped tensor product. When the tensor product is capped, it is a lattice. Whether the converse is true is a long-standing conjecture, which we solve in this paper.

The paper [START_REF] Wehrung | Solutions to five problems on tensor products of lattices and related matters[END_REF] gives a good insight into the present state of affairs in the field. This paper is organized as follows. In Section 2 we give basic definitions from lattice theory. In Section 3 we adopt classical results concerning tensor products of lattices from [START_REF] Grätzer | Tensor products of semilattices with zero, revisited[END_REF] and [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF]. This includes the characterization of bi-ideals as homomorphisms of a special kind, antitone step functions and adjustment sequences. Theorem 1 establishes the equivalence between the representations of bi-ideals by homomorphisms and the adjustment sequences.

In Sections 4 and 5 we start to deploy the original technique aiming at a narrow class of normal lattices, which we use later to prove the conjecture. As a prerequisite, in Section 4 we introduce marked lattices and define the family of zig-zag operators acting on them. After that, in Section 5 we define normal lattices as special kinds of marked lattices, and establish some important facts about them. We prove that normal lattices are finitely generated and that all their nontrivial intervals are finite. The essential property of this section is established in Lemma 7, which, informally, states that normal lattices are almost locally finite, that is, every finite subset S of a normal lattice L generates a finite sublattice in a slightly modified lattice L x .

In Section 6 we introduce the infinite normal lattice L ∞ and claim that the tensor product L ∞ ⊗ L op ∞ satisfies the desired properties, namely that it is not capped but is a lattice. Apart from being infinite and normal, the lattice L ∞ possesses another property captured in Lemma 9, namely that an infinite sublattice of L ∞ can be mapped into L ∞ only the trivial way. As a digression, albeit we do not prove that, this property naturally holds for the most of the infinite normal lattices, so in this sense the lattice L ∞ is in no way exceptional.

Note that the technique developed throughout Sections 4, 5 and 6 is independent of those developed in Section 3.

Finally, in Section 7 we bring together the results of Sections 3, 4, 5 and 6 to establish the key properties of L ∞ ⊗ L op ∞ . In Theorems 2 and 3 we prove that there are noncapped elements in L ∞ ⊗ L op ∞ and that all these elements are in a way similar to each other. These results easily yield Theorem 4, which positively solves the conjecture.

Preliminary definitions and formulation of the problem

We start with some basic definitions and notations. A subset S of a poset T is called hereditary iff y ≤ x and x ∈ S implies y ∈ S, for all x, y ∈ T .

We denote by S op the dual poset of a poset S, that is, the same set with order given by

x ≤ S op y ⇔ x ≥ S y.

In an arbitrary poset the height of an element x, denoted h(x), is defined as the supremum of all cardinalities of a chain from a non-minimal element to x. The length of a poset is the supremum of the heights of all its elements. We are following a standard convention of calling elements of height one atoms, additionally we call elements of height two lines.

For a lattice K and x ∈ K let (x] denote the principal ideal generated by x, that is, (x] = {y | y ≤ x}. For lattices K, L and an element (x, y) ∈ K × L we use the notation (x, y] instead of (x, y) to denote the principal ideal.

For a lattice L and a set A ⊆ L we denote by A L the sublattice of L generated by A in L, and by A ∨ and A ∧ the subsets

A ∨ = { B | B is a finite subset of A}, A ∧ = { B | B is a finite subset of A}.
For a (0, 1)-lattice L, (∨, 0)-semilattice K and (∧, 1)-semilattice P we denote by L -, K 0 and P 1 the posets L -{0, 1}, K -{0} and P -{1} correspondingly.

An element x in a complete lattice A is compact iff x ≤ S for some S implies x ≤ T for some finite T ⊆ S. The set of all compact elements of a complete lattice A is denoted by C(K). For every complete lattice A the set C(A) is a (0, ∨)-semilattice. A complete lattice A is called algebraic iff every element is the join of compact elements.

For a (0, ∨)-semilattice K we denote by Id K the complete algebraic lattice of ideals of K ordered by set inclusion. The semilattice K is a subsemilattice of Id K with the canonical embedding given by a → (a].

The tensor product and the capped tensor product are defined in [START_REF] Grätzer | Tensor products of semilattices with zero, revisited[END_REF]. As these definitions are central to the paper, let us recall them.

Let K and L be lattices with zero. The lateral join is the partial function

∨ lat : (K × L) × (K × L) → K × L defined by (x 1 , y 1 ) ∨ lat (x 2 , y 2 ) = (x 1 ∨ x 2 , y 1 ∨ y 2 ) provided either x 1 = x 2 or y 1 = y 2 .
A subset I of K × L is a bi-ideal iff it is hereditary, it contains the set

⊥ K,L = ({0 K } × L) ∪ (K × {0 L }) ,
and it is closed under lateral joins.

The extended tensor product of K and L, denoted by K ⊗ L, is the set of all bi-ideals in K × L ordered by set inclusion. It can easily be seen that K ⊗ L is a complete algebraic lattice. Define the tensor product of K and L, denoted K ⊗ L, as the set of compact elements of K ⊗ L with order inherited from K ⊗ L. It can be easily seen that K ⊗ L is a (0, ∨)-subsemilattice of K ⊗ L. In general, however, K ⊗ L is not a lattice (see Corollary 8.2 in [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF]).

A simple example of a compact bi-ideal in

K × P is a set a ⊗ b, a ∈ K, b ∈ L, called a pure tensor : a ⊗ b = {(x, y) ∈ K × L | x ≤ a, y ≤ b} ∪ ⊥ K,L . Call a compact bi-ideal I ⊆ K × L a capped bi-ideal if it is a finite union of pure tensors, that is I = (a i ⊗ b i | i = 0, . . . , k -1).
Note that the symbol above refers to set-theoretical union. In general, every compact bi-ideal can be represented as

I = (a i ⊗ b i | i = 0, . . . , k -1),
where the join is taken in K ⊗ L. Nevertheless, the set-theoretic representation as a finite union does not necessarily hold.

We call the tensor product K ⊗L capped if all its elements are capped bi-ideals. If the tensor product is capped, then clearly it is a lattice. It is asked in [START_REF] Grätzer | Tensor products of semilattices with zero, revisited[END_REF]Problem 3] whether the converse holds.

Conjecture 1. There are bounded lattices K and L such that K ⊗ L is a lattice, yet the tensor product K ⊗ L is not capped.

The subsequent sections are dedicated to proving that this conjecture is correct.

Preparatory technique

We start with a representation by homomorphisms described in Section 2.3 of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF]. Let A and B be (∨, 0)-semilattices. We consider the set of all semilattice homomorphisms from the semilattice A 0 ; ∨ to the semilattice (Id B; ∩),

A - → ⊗ B = Hom A 0 ; ∨ , (Id B; ∩) ,
ε(ϕ) = {(x, y) ∈ A × B | y ∈ ϕ(x)} ∪ ⊥ A,B . Proposition 1. The map ε is an isomorphism between A - → ⊗ B and A ⊗ B. The inverse map, ε -1 , sends H ∈ A ⊗ B to ε -1 (H) : A 0 → Id B, defined by ε -1 (H)(a) = {x ∈ B | (a, x) ∈ H} . (1)
Proof. See Proposition 2.4 of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

As there is a natural isomorphism between A ⊗ B and B ⊗ A, we can define an isomorphism η from B -→ ⊗ A to A ⊗ B in a similar way as we defined ε, that is

η(ψ) = {(x, y) ∈ A × B | x ∈ ψ(y)} ∪ ⊥ A,B , for any ψ ∈ B - → ⊗ A. Then for every homomorphism ϕ ∈ A - → ⊗ B we define its conjugate ϕ * ∈ B - → ⊗ A as ϕ * = η -1 • ε(ϕ).
Thus, the conjugation defines an isomorphism between A -→ ⊗ B and B -→ ⊗ A. By abuse of terminology, the converse mapping ε -1 • η is also called conjugation. We subsume the notation defined above by stating that the diagram in Figure 1 below commutes.

A ⊗ B A - → ⊗ B B - → ⊗ A ε -1 ε η -1 η • * = η -1 • ε • * = ε -1 • η Figure 1 Proposition 2. Let ϕ be a homomorphism from (A; ∨) to (Id B; ∩), that is, ϕ ∈ A - → ⊗ B. Then y ∈ ϕ(x) iff x ∈ ϕ * (y), for all x ∈ A, y ∈ B. Proof. Indeed, y ∈ ϕ(x) ⇔ (x, y) ∈ ε(ϕ) ⇔ x ∈ ϕ(y).
As we mentioned earlier, all elements of A⊗B are finite joins of pure tensors. The following proposition gives the representation of finite joins in a purely arithmetic way. For every positive integer m, denote by F(m) the free lattice on m generators x 0 , . . . , x m-1 . One can evaluate any element p of F(m) at any m-tuple of elements of any lattice, thus justifying the notation p(a 0 , . . . , a m-1 ). By p op we denote the dual of p. Proposition 3. Let A and B be lattices with zero, let n be a positive integer, let a 0 , . . . , a n-1 ∈ A, and let b 0 , . . . , b n-1 ∈ B. Then

(a i ⊗ b i | i < n) = (p(a 0 , . . . , a n-1 ) ⊗ p op (b 0 , . . . , b n-1 ) | p ∈ F(n))
Proof. See Lemma 2.2, (iii) of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

To argue about whether the tensor product is a lattice we need the following easy result. Proposition 4. A⊗B is a lattice if and only if it is closed under finite intersection.

Proof. See Proposition 2.4 of [START_REF] Grätzer | Tensor products of semilattices with zero, revisited[END_REF]. Proposition 5. Let A and B be lattices with zero and let A be locally finite. Then A ⊗ B is a lattice iff A ⊗ B is a capped tensor product.

Proof. See Theorem 3 of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

The following technique described in Section 6 of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF] enables us to obtain a very useful representation of compact bi-ideals.

Let A and B be lattices with zero. We put (a] • = (a] ∩ A 0 , for all a ∈ A. We denote by Int A the boolean lattice of the powerset of A 0 generated by all sets of the form (a] • , for a ∈ A 0 . Furthermore, we denote by Int * A the ideal of Int A consisting of all X ∈ Int A with X ⊆ (a] • , for some a ∈ A.

The map ξ : A 0 → B is a step function if the range of ξ is finite and the inverse image ξ -1 {b} belongs to Int * A, for all b ∈ B 0 . Proposition 6. For a positive integer n let a 0 , . . . , a n-1 ∈ A and b 0 , . . . , b n-1 ∈ B. Then the map ξ : A 0 → B defined by

ξ(x) = (b i | i < n, x ≤ a i ) , (2)
for all x ∈ A 0 , is an antitone step function. Furthermore,

(x, ξ(x)) ∈ (a i ⊗ b i | i < n) ,
for all x ∈ A 0 .

Proof. See Lemma 6.4 of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

If an antitone function ξ : A 0 → B is obtained by application of formula (2), then we say that an antitone function ψ : B 0 → A is the dual of ξ if it is obtained by application of (2) to elements b i and a i , i < n, that is

ψ(x) = (a i | i < n, x ≤ b i ) .
A join-cover of the element a ∈ A is any finite subset S ⊆ L such that a ≤ S. A join-cover S of a is nontrivial if a ≤ s, for all s ∈ S. Let C(a) denote the set of all finite join-covers and C * (a) the set of all finite nontrivial join-covers of a.

Let ξ : A 0 → B be a map with finite range. Then one-step adjustment of ξ is ξ (1) : A 0 → B defined by

ξ (1) (x) = ξ[S] | S ∈ C(x) , (3)
for all x ∈ A 0 . Note that since the range of ξ is finite, the right hand side of the equation ( 3) is well-defined. Proposition 7. Let ξ : A 0 → B be a map with finite range. Then ξ (1) is antitone and has finite range, and the inequality ξ(x) ≤ ξ (1) (x) holds for all x ∈ A 0 . Furthermore, ξ (1) = ξ iff ξ is a semilattice homomorphism from A 0 ; ∨ to (B; ∧).

Proof. See Remark 6.6 and Lemma 6.8 of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

Similar techniques are used in connection with bounded homomorphisms, see Chapter 2 of [START_REF] Freese | Free lattices[END_REF].

Proposition 8. If ξ is an antitone map with finite range, then the one-step adjustment (3) takes the form:

ξ (1) (x) = ξ(x) ∨ ξ[S] | S ∈ C * (x) . (4)
Proof. See Remark 6.6 of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

Proposition 9. Let ξ : A 0 → B be a step function, then the one-step adjustment ξ (1) of ξ is an antitone step function.

Proof. See Proposition 6.10 of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

Proposition 9 justifies the following definition. Let ξ : A 0 → B be a step function. The adjustment sequence of ξ is the sequence ξ (n) | n < ω defined inductively by ξ (0) = ξ, and ξ (n+1) = (ξ (n) ) (1) , for all n < ω.

Proposition 10. Let ξ : A 0 → B be a step function. Then the adjustment sequence of ξ is increasing, that is, ξ (n) ≤ ξ (n+1) , for all n. Furthermore, if n > 0 then ξ (n) is an antitone step function.

Proof. See Corollary 6.12 of [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

Consider the complete lattice Id B and view the mappings ξ (n) , n < ω as mappings from A 0 to Id B using the canonical embedding of B into Id B. Define the ω-adjustment of ξ as the mapping ξ (ω) : A 0 → Id B defined by

ξ (ω) (x) = (ξ (n) (x) | n < ω), (5)
and the extended adjustment sequence of ξ is the sequence ξ

(α) | α ≤ ω .
Note that the range of ξ (ω) need not be finite, and thus ξ (ω) need not be a step function. However, ξ (ω) is antitone. Also, just as the adjustment sequence, the extended adjustment sequence is increasing.

Proposition 11. The one-step adjustment and the ω-adjustment operations are monotonous, that is, if ξ and ψ are maps with finite range such that ξ ≤ ψ, then ξ (1) ≤ ψ (1) and ξ (ω) ≤ ψ (ω) .

Proof. Follows immediately from formulas (3) and [START_REF] Grätzer | Tensor products and transferability of semilattices[END_REF].

The following theorem establishes connection between the bi-ideals represented as homomorphisms and the extended adjustment sequences.

Theorem 1. Let n < ω, a 0 , . . . , a n-1 ∈ A and b 0 , . . . , b n-1 ∈ B. Let the map ξ : A 0 → B be the map defined by (2). Let I ∈ A ⊗ B be the compact bi-ideal

I = (a i ⊗ b i | i < n),

and let ϕ

I ∈ A - → ⊗ B be the representation of I defined by (1), that is, ϕ I = ε -1 (I). Then (i) ξ (ω) is a homomorphism from A 0 , ∨ to (Id B, ∩), that is, ξ (ω) ∈ A - → ⊗ B, (ii) ϕ I = ξ (ω) . Proof. (i): As ξ (ω) is antitone, then ξ (ω) (x ∨ y) ⊆ ξ (ω) (x) ∩ ξ (ω) (y). On the other hand since {x, y} ∈ C(x ∨ y), then by (3) we infer ξ (ω) (x ∨ y) ⊇ ξ (n+1) (x ∨ y) ⊇ ξ (n) (x) ∩ ξ (n) (y), for all n < ω. But from (5) we get ξ (ω) (x) ∩ ξ (ω) (y) = (ξ (n) (x) | n < ω) ∩ (ξ (n) (y) | n < ω) = (ξ (n) (x) ∩ ξ (n) (y) | n < ω) ⊆ ξ (ω) (x ∨ y),
and the result follows.

(ii): The homomorphism ϕ I is the smallest homomorphism such that for all i < n holds b i ∈ ϕ I (a i ). Thus, ϕ I ≤ ξ (ω) . On the other hand from Proposition 6 follows ξ (0) ≤ ϕ I . The homomorphism ϕ I does not have finite range, but as Id B is a complete lattice then (3) is well-defined for ϕ I . As ϕ I is a homomorphism from A 0 , ∨ to (Id B, ∩) then by Proposition 7 the equality ϕ Remark 1. Under the conditions of Theorem 1, if the lattice B is of finite length then it coincides with Id B. Thus, we can regard ξ (ω) and ϕ I as homomorphisms from A 0 , ∨ to (B, ∧). This applies to all elements of A -→ ⊗ B, that is, we can regard

A - → ⊗ B as A - → ⊗ B = Hom A 0 ; ∨ , (B; ∧) . Corollary 1. Under the conditions of Theorem 1, if φ : B 0 → A is a dual of ξ : A 0 → B, then (i) φ (ω) is a homomorphism from B 0 , ∨ to (Id A, ∩), that is, φ (ω) ∈ B - → ⊗ A, (ii) ϕ * I = φ (ω) .
For an element a of A and an ideal I of B, let us define a bi-ideal a

• ⊗ I as a • ⊗ I = {(x, y) ∈ A × B | x ≤ a, y ∈ I} ∪ ⊥ A,B .
Notice that in general a

• ⊗ I is not a compact bi-ideal, that is, it belongs to A ⊗ B, but not to A ⊗ B.
For every bi-ideal I the following representation trivially holds

I = x • ⊗ ϕ I (x) | x ∈ A ,
where ϕ I = ε -1 (I). However, this representation can be strengthened, as it is shown in the following lemma.

Lemma 1. Under the conditions of Theorem 1, the bi-ideal I can be represented as

I = x • ⊗ ϕ I (x) | x ∈ a i | i < n , x = 0 A .
Proof. Let us denote by J the union from the right hand side of the hypothesis, that is,

J = x • ⊗ ϕ I (x) | x ∈ a i | i < n , x = 0 A . As I = x • ⊗ ϕ I (x) | x = 0 A , the inclusion I ⊇ J trivially holds.
Now, we are going to prove that J is a bi-ideal. As J contains all pairs (a i , b i ) for all i < n, and I is the least bi-ideal containing all such pairs, this would yield I ⊆ J, proving the lemma.

It is obvious that J is hereditary and contains the set ⊥ A,B , so we only need to prove that it is closed under lateral joins.

Let (c, d 1 ) and (c, d 2 ) be elements from J, c = 0 A , d j = 0 B . Then there are two elements x 1 and x 2 from a i | i < n such that c ≤ x j and d j ∈ ϕ I (x j ), for j = 1, 2. Then c < x 1 ∧ x 2 , and as ϕ I is antitone, then d j ∈ ϕ I (x j ) ⊆ ϕ I (x 1 ∧ x 2 ) and so

d 1 ∨ d 2 ⊆ ϕ I (x 1 ∧ x 2 ). As the element x 1 ∧ x 2 is from a i | i < n , then (c, d 1 ∨ d 2 ) lies in J. Now, let (c 1 , d) and (c 2 , d) lie in J, c j = 0 A , d = 0 B .
Then again, there are elements x 1 and x 2 from a i | i < n such that c j ≤ x j and d ∈ ϕ I (x j ), for j = 1, 2.

In this case c 1 ∨ c 2 ≤ x 1 ∨ x 2 and d ∈ ϕ I (x 1 ) ∩ ϕ I (x 2 ) = ϕ I (x 1 ∨ x 2 )
, and so (c 1 ∨ c 2 , d) lies in J. Thus, J is closed under lateral joins and so it is a bi-ideal, which finishes the proof. Now we can apply Remark 1 to obtain Corollary 2. Under the conditions of Theorem 1, if the lattice B is of finite length, then the bi-ideal I can be represented as

I = x ⊗ ϕ I (x) | x ∈ A 0 = (x ⊗ ϕ I (x) | x ∈ a i | i < n , x = 0 A ) .

Marked lattices

A marked lattice is a structure (L, a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , a 9 ), where • L is a lattice of length at most three.

• The elements a 1 , . . . , a 9 , called the marked elements of L, are pairwise distinct atoms of L. • a i ∨ a j = 1 L , for any distinct i, j ∈ {1, . . . , 9}.

Marked lattices will often be denoted in the form L[a 1 , . . . , a 9 ], or simply L if the marked elements are understood from the context. Now, we define operators CW and CCW which transform a marked lattice by adding new elements into it. It should be observed that each of the additional "lines" of the construction is defined by two distinct marked "atoms" x and y, and then the line is denoted xy or, indifferently, yx.

If L[a, b, c, d, e, f, g, h, i] is a marked lattice, then we define the marked lattice K[a , b , c , d , e , f , g , h , i ] = CW(L) in the following way. The elements of K are all elements of L plus:

• candidate lines ab, bc, cd, de, ef, f g, gh, hi and ic,

• candidate lines ce, df, eg, f h, gi, ha, ib, ac and dh,

• candidate atoms ab • ce, bc • df, cd • eg, de • f h, ef • gi, f g • ha, gh • ib, hi • ac
and ic • dh. And the order on K is defined as:

• restricted to L, order of K coincides with the original order of L,

• all new elements lie above the zero and below the unit of L,

• a, b ≤ ab; . . . ; d, h ≤ dh, • ab • ce ≤ ab, ce; . . . ; ic • dh ≤ ic, dh,
• otherwise elements are incomparable.

Finally, we define marked elements by a = ab • ce; . . .

; i = ic • dh.
Similarly, we define the marked lattice P [a , b , c , d , e , f , g , h , i ] = CCW(L) in the following way. The elements of P are all elements of L plus:

• candidate lines ad, be, cf, dg, eh, f i, ga, hb and ia,

• candidate lines ei, f a, gb, hc, id, ae, bf, cg and bd,

• candidate atoms ad • ei, be • f a, cf • gb, dg • hc, eh • id, f i • ae, ga • bf, hb • cg
and ia • bd. The order on P is defined as:

• restricted to L, order of P coincides with the original order of L,

• all new elements lie above the zero and below the unit of L,

• a, d ≤ ad; . . . ; b, d ≤ bd,

• ad • ei ≤ ad, ei; . . . ; ia • bd ≤ ia, bd,

• otherwise elements are incomparable.

And the marked elements are a = ad • ei, . . . , i = ia • bd.

The constructions CW and CCW are illustrated in Figures 2 and3 below. (ii) Atoms and lines of L remain correspondingly atoms and lines in both K and P (except the "degenerate" line 1). (iii) K and P are lattices. (iv) K and P are marked lattices. (v) L is a meet-subsemilattice of both K and P .

a b c d e f g h i ab • ce bc • df cd • eg de • f h ef • gi f g • ha gh • ib hi • ac ic • dh

Proof. (i):

The only element that lies below candidate atoms is the zero element of L, so they are atoms. Now if we take candidate line xy, then there are four elements below it: the zero of L, two marked elements of L, namely x and y, and one candidate atom. Thus, xy is a line.

(ii): Trivial, as there are no new elements added below any atom or any line of L.

(iii): As K and P are bounded posets of finite length then to prove that they are lattices it is sufficient to prove that they are meet-semilattices. All meets between atoms trivially exist, as well as meets between a line and an atom. Now, if we take two lines then there are three possibilities. If we take two lines from L then their meet is preserved from L. If we take two candidate lines then, by the construction of the operators CW and CCW, they meet either at a candidate atom or at a marked element, or else they have no atom in common, in which case they meet at the zero.

Finally, if we take a candidate line l and a line p from L then the only elements that can lie below both of them, except for the zero, are marked elements of L. But as any two distinct marked elements join at the unit, there is at most one marked element of L below p, and so the meet exists.

(iv): Both in K and P the height of the unit element is three. Also any pair of distinct candidate atoms have no common line above them, so they join at the unit. Thus, it is a marked lattice.

(v): Trivial, as there are no new elements added below any atom or any line of L.

Notice that under the conditions of Lemma 2, L is a join-subsemilattice of neither K nor P .

We call an operator on marked lattices a finite zig-zag operator if it can be represented as a finite composition of operators CW and CCW, that is,

Z = k i=1 Z i = Z k • Z k-1 • • • • • Z 1 ,
where k ∈ N and each Z i is either CW or CCW. The number k is called the degree of Z, denoted deg (Z). The operators CW and CCW are themselves finite zig-zag operators of degree one, and we call them primitive zig-zag operators. We denote by Z r...l the operator

Z r...l = l i=r Z i = Z l • Z l-1 • • • • • Z r , where 1 ≤ r ≤ l ≤ deg Z.
We follow the convention of treating the product of zero operators as the identity operator Id, which we thus consider a zig-zag operator of degree 0. With this convention we allow the notation

Z r...r-1 = r-1 i=r Z i = Id .
We define an infinite zig-zag operator Z associated to the sequence of primitive zig-zag operators (Z k ) ∞ k=1 , denoted Z = ∞ i=1 Z i , as an operator which assigns to a marked lattice L the direct limit of the sequence of bounded meet-semilattices

Z 1...k (L) ∞ k=1 , where Z 1...k (L) = k i=1 Z i (L), that is, Z(L) is a poset Z(L) = ∞ k=1 k i=1 Z i (L),
and the partial order on Z(L) is given by

x ≤ Z(L) y ⇔ ∃k : x ≤ Z 1...k (L) y.
The next lemma proves that, thus defined, Z(L) is an infinite bounded lattice of length three. Lemma 3. Let Z be infinite zig-zag operator and let L be a marked lattice. Then Z(L) is an infinite lattice of length three, and Z 1...k (L) is a meet-subsemilattice of Z(L), for every k < ω.

Proof. It follows from Lemma 2, (v) that all meets from Z(L) are preserved in Z 1...k (L), for every positive k. In particular, that the order on Z 1...k (L) is the restriction of the order of Z(L). Then indeed Z(L) is a meet-semilattice and Z 1...k (L) is its meet-subsemilattice. Now, observe that the length of Z(L) is the supremum of lengths of Z 1...k (L) for all k, and so it equals three. Thus, Z(L) is of finite length from which it follows that it is a lattice.

For infinite zig-zag operators we utilize the notation Z k...l in a similar way as we do in the finite case, however, we let l = ∞. Note that in case l is finite, Z k...l is a finite zig-zag operator, while Z k...∞ is an infinite zig-zag operator. We write that Z is a zig-zag operator in case it is not essential for us whether Z is finite or infinite. We say that the degree of an infinite zig-zag operator is ∞.

The following observations of a combinatorial nature about the primitive zig-zag operators will be useful for us in the subsequent sections.

Proposition 12. Let L be a marked lattice and let W be a primitive zig-zag operator. Then for every line l ∈ W(L) -L there is a unique line l * ∈ W(L) -L, called the conjugate of l, such that l and l * meet at an atom in W(L) -L.

For example, for the operator CW the conjugate of the line ab is ce, and the conjugate of ic is dh. Notice also that the equality l = l * * holds for any line l in W(L) -L.

Proposition 13. Let L[a, b, c, d, e, f, g, h, i] be a marked lattice. For a marked element x ∈ L define CW x (correspondingly CCW x) as the number of candidate lines of CW(L) (correspondingly CCW(L)) containing x. Also define θ CW (x) (correspondingly θ CCW (x)) as the subset of those marked elements of L that join with x at a candidate line of CW (correspondingly CCW). Then the values of the functions CW , CCW , θ CW and θ CCW are given in Table 1 Let L[s 0 , . . . , s 8 ] be a marked lattice, let W be a primitive zig-zag operator and let t be a marked element of L [t 0 , . . . , t 8 ] = W(L). Then we define the base of t, denoted Bs W (t), as the following set of marked elements of L:

Bs W (t) = {s i | 0 ≤ i ≤ 8, t ∈ Cn(s i )} . Observe that |Bs CW (t i )| = |Bs CCW (t i )| = 4, for all i ∈ {0, . . . , 8}.
Lemma 4. Let L[s 0 , . . . , s 8 ] be a marked lattice, let W be a primitive zig-zag operator and let L [t 0 , . . . , t 8 ] = W(L). Then the following inequality holds

|Bs W (t i ) ∪ Bs W (t j ) ∪ Bs W (t k )| ≥ 6,
for any distinct i, j, k ∈ {0, . . . , 7}.

Proof. In the following proof all indexes are taken modulo 9. First of all, let us observe that for i ∈ {0, . . . , 7} (but not for i = 8) the base of t i can be represented as

Bs CW (t i ) = {s i , s i+1 , s i+2 , s i+4 } , Bs CCW (t i ) = {s i , s i+3 , s i+4 , s i+8 } .
In the case W = CW from this representation we can infer

|Bs CW (t i ) ∩ Bs CW (t j )| ≤ 2 and thus |Bs CW (t i ) ∪ Bs CW (t j )| ≥ 6,
for any distinct i, j ∈ {0, . . . , 7}.

In the case W = CCW the latter inequality does not hold, as, for example, Bs CCW (t 0 ) ∪ Bs CCW (t 4 ) = {s 0 , s 3 , s 4 , s 7 , s 8 }.

On the other hand we can see that the inequality

|Bs CW (t i ) ∪ Bs CW (t j )| ≤ 5
holds for distinct i, j ∈ {0, . . . , 7} only if |i -j| = 4. As from any three distinct elements i, j, k ∈ {0, . . . , 7} one can always choose a pair that does not satisfy this condition, we infer

|Bs CCW (t i ) ∪ Bs CCW (t j ) ∪ Bs CCW (t k )| ≥ 6,
for any distinct i, j, k ∈ [0, 7], thus finishing the proof.

Normal lattices

We denote by L 0 [a 1 , . . . , a 9 ], or simply L 0 , the marked lattice represented in Figure 4. We call a lattice L normal if there is a zig-zag operator Z L such that L = Z L (L 0 ). We understand by the degree of a normal lattice the minimal degree of the zig-zag operator Z, such that L = Z(L 0 ). We treat a normal lattice of finite degree as marked lattice, that is, we allow a zig-zag operator to be applied to it. Notice also that a normal lattice is of finite degree iff it is finite. Further on, we will work exclusively with normal lattices.

We need the following technical result Lemma 5. Let L be a lattice of length at most three and let x ∈ L -, then the poset obtained from L by removing x, denoted L x , is a lattice.

Proof. Let y, z ∈ L x . If y ∨ L z = w = x then y ∨ L x z = w.
On the other hand, if y ∨ L z = x then y ∨ L x z = 1. Thus, every pair of elements in L x has a join, and the meets are handled dually.

Note that as all normal lattices are of length at most three, then Lemma 5 can be applied to them.

Let L be a normal lattice, x ∈ L -. Define the rank of x, denoted r(x), as

r(x) =      0, x ∈ L 0 ; 2n -1, x ∈ Z L 1...n (L 0 ) -Z L 1...n-1 (L 0 ), x is a line; 2n, x ∈ Z L 1...n (L 0 ) -Z L 1...n-1 (L 0 ),
x is an atom. That way, all atoms in a normal lattice have even rank, all lines (except the "degenerate" line 1 in L 0 ) have odd rank, and, informally speaking, an element of rank k + 1 is generated by elements of rank k.

Let us define a binary relation on a normal lattice L by w y if w and y are comparable elements of L -and r(w) = r(y) -1. We say that a subset C of L is a cone if w y and w ∈ C implies y ∈ C. For a subset S of L we denote by Cn(S) the least cone of L containing S.

Occasionally, we write Cn(x 1 , . . . , x k ) instead of Cn ({x 1 , . . . , x k }) to denote the cone of {x 1 , . . . , x k }. For an element x of L we denote by Cn -(x) the set Cn(x) -{x}. Proposition 14. For any normal lattice L the following statements hold:

(i) Any distinct comparable elements x, y ∈ L -satisfy r(x)r(y) ∈ {-1, 1}, that is, either x y or y x. (ii) Every element x ∈ L -of rank k ≥ 1 has exactly two elements u and v such that u, v x. (iii) Every line of L of rank k ≥ 1 contains exactly three atoms: two of rank k -1 and one of rank k + 1. (iv) Every atom of L is contained in at most seven lines.

Note that in case x is an atom the two elements u and v of (ii) are conjugate lines.

Corollary 3. If L is a normal lattice then all its intervals, except for the trivial interval [0, 1], are finite.

Let us state several trivial observations about cones.

Proposition 15. For any normal lattice L the following statements hold:

(i) All elements of Cn(x) -have rank strictly greater than the rank of x.

(ii) The zero of L lies in Cn(S) only if it lies in S, and similarly for the unit.

In particular, Cn(x) ⊆ L -, for any x ∈ L -. (iii) For all x, y in L, if y ∈ Cn(x) then Cn(y) ⊆ Cn(x). Lemma 6. Let K be a normal lattice, then K -Cn(x) is a sublattice of K x , for all x ∈ K -.

Proof. Suppose, to the contrary, that in K x there is y ∈ Cn(x) such that y = u ∨ v or y = u∧v, for some u, v ∈ K -Cn(x). As the corresponding join or meet is proper, then u, v ∈ K -, and also as Cn(x) ⊆ K -then y ∈ K -. Observe that u and v are comparable to y, thus, by Proposition 14, (i) either u y or y u, and similarly for v. But if y u, then u ∈ Cn(y), which is impossible, and so we get u, v y. Now, by Proposition 14, (ii) u and v are the only elements of K such that u, v y. As u, v / ∈ Cn(x), then we may say that z y, for any z ∈ Cn(x). But, as y = x, this implies y / ∈ Cn(x), a contradiction. Now we need to establish a crucial fact about infinite normal lattices. Lemma 7. Let L be a finite normal lattice and let W be an infinite zig-zag operator, K = W(L). Then L K x is finite, for any x in K -L.

Proof. As the rank of x is greater than the rank of all elements of L then by Proposition 15 we get L ⊆ K -Cn(x). Observe that by Lemma 6 the set K -Cn(x) is a sublattice of K x and so L K x ⊆ K -Cn(x). Thus, to prove the finiteness of L K x it is sufficient to prove the following statement: There exists a positive integer k such that all marked elements of W 1...k (L) belong to Cn(x).

By Proposition 14, (iii) every line l has exactly one atom y of rank r(l) + 1 in Cn(l). For example, if W 1 = CW and the line is ab, then the relevant atom is ab • ce. As Cn(y) ⊆ Cn(l), then, without loss of generality we may assume that x is an atom.

Next, by Proposition 13, for both CW and CCW every marked element participates in the generation of at least three new lines, which in turn participate in Notice that the statement {φ(a n 1 ), . . . , φ(a n 9 )} = {a m 1 , . . . , a m 9 } can be restated as m n 0 = m n 1 = m, for some m. We claim that the proof of this fact can further be reduced to proving the following statement:

If m k 0 < m k 1 for some k then m k+1 0 < m k+1 1 and m k+1 0 ≤ m k 0 . ( †)
Indeed, let us assume that ( †) holds and, arguing by contradiction, suppose that m n 0 < m n 1 . Then iteratively applying ( †) we get m k 0 < m k 1 , for all k ≥ n, and the sequence {m k 0 } ∞ k=n is decreasing and nonnegative. Thus, there is N ≥ n such that all m k 0 are equal to M = m N 0 , for all k ≥ N . By the definition of I k we obtain that P M has a nonempty intersection with φ(P k ), for all k ≥ N . As φ is one-to-one, the sets P k are disjoint for all k, and P M is finite, we get a contradiction. Now, let us prove that ( †) is correct. To simplify the notation, in the proof below we write m 0 instead of m k 0 . Take x, y ∈ P k such that φ(x) ∈ P m0 , φ(y) ∈ P m0+1 , and l = x ∨ y is a line. As x and y have rank 2k then by Proposition 14 the rank of l is 2k + 1 and there is an atom u of rank 2k + 2, that is, u ∈ P k+1 , such that u ≤ l. Applying Proposition 14 once again, we infer that u is the meet of two conjugate lines l and l * of rank 2k + 1. Furthermore, l * is the join of two atoms z and w of rank 2k, that is, z, w ∈ P k , z ∨ w = l * . It is clear that the elements x, y, z, w, u, l and l * are pairwise distinct.

Let us consider the rank of the images of elements x, y, z, w, u, l and l * under the homomorphism φ. As r(φ(x)) = 2m 0 and r(φ(y)) = 2m 0 +2, then r(φ(l)) = 2m 0 +1 and r(φ(u)) = 2m 0 . For the rank of the line φ(l * ) we need to consider two cases: either r(φ(l * )) = 2m 0 -1, or r(φ(l * )) = 2m 0 + 1. However, in the first case we get r(φ(z)) = r(φ(w)) = 2m 0 -2, which is impossible as z and w lie in P k . Thus, r(φ(l * )) = 2m 0 + 1 and out of the atoms φ(z) and φ(w) one (say z) has rank 2m 0 , and another (say w) has rank 2m 0 + 2.

The above argument is illustrated in Figure 5 below.

P k P k+1 l l * u x y z w P m0 P m0+1 φ(l) φ(l * ) φ(u) φ(x) φ(y) φ(z) φ(w) φ Figure 5
All in all, as u ∈ P k+1 and φ(u

) ∈ P m0 , then m 0 ∈ [m k+1 0 , m k+1 1 ], yielding m k+1 0 ≤ m k 0 .
Also notice that as the sets P m0 and φ(P k+1 ) are equal in size, and as in P m0 there are elements φ(x) and φ(z), which do not belong to φ(P k+1 ), then some element of φ(P k+1 ) lies outside of P m0 , thus m k+1 0 < m k+1 1 .

The counterexample

Let L ∞ = ∞ k=1 C k L 0
We finally need to consider the case when φ [P n ] = P n . In the remaining part of the theorem we denote the marked elements of P n by a, b, c, d, e, f, g, h, i.

If

The proof

We are going to prove that the tensor product L ∞ ⊗ L op ∞ is a lattice and that it contains a noncapped compact bi-ideal, confirming Conjecture 1.

Throughout this section in order not to get lost between the order of L ∞ and its dual we will stick to the order of L ∞ . This way, the elements of

L ∞ - → ⊗ L op ∞ , which by Remark 1 lie in Hom L 0 ∞ ; ∨ , L op ∞ ; ∧ L op ∞
, become join-homomorphisms from L 0 ∞ to L ∞ , and correspondingly the elements of

L op ∞ - → ⊗ L ∞ become meet-homo- morphisms from L 1
∞ to L ∞ . Rewritten in these terms, the pure tensor takes form

a ⊗ b = {(x, y) ∈ L ∞ × L ∞ | x ≤ a, y ≥ b} ∪ ⊥ where ⊥ = ({0} × L ∞ ) ∪ (L ∞ × {1}) , for all a, b ∈ L ∞ . Formula (2) takes form ξ(x) = (b i | i < N, x ≤ a i ) , (2 )
for all x ∈ L 0 ∞ , where a i , b i ∈ L ∞ , for i < N . Thus defined, ξ(x) is an isotone step function. Similarly, formulas (3) and ( 4) for one-step adjustment take form

ξ (1) (x) = ξ[S] | S ∈ C(x) , (3 )
ξ (1) (x) = ξ(x) ∧ ξ[S] | S ∈ C * (x) . (4 )
We start with the following technical lemma Lemma 10. Let K be a lattice of length at most three. Then (i) For any x ∈ K -and any y ∈ K, y = x, the following equality holds

C(y) -C(x) = C K x (y) -C(x).
(ii) Let x be an atom and let w be a line in K, x < w. For a subset S ⊆ K let us define the subset S ⊆ K x by S = S, x ∈ S; S -{x} + {w} x ∈ S, then for all y ∈ K x the following equality holds

{S | S ∈ C(y)} = {S | S ∈ C K x (y)}.
We recall that C(a) and C K x (a) are the sets of finite join-covers of a in K and in K x correspondingly. Proof. (i): If a subset A ⊆ K is finite and x ∈ A then either K A = Kx A or K A = x. Thus, for any finite subset S ⊆ K such that S ∈ C(x) we get K S = Kx S, which immediately proves the claim.

(ii): Take y ∈ K x and S ∈ C(y). Then S ≥ S ≥ y and x 0 ∈ S, thus, S ∈ C K x (y) and {S | S ∈ C(y)} ⊆ {S | S ∈ C K x (y)}. To prove the opposite inclusion we take S ∈ C K x (y). Then either K x S = S or S = x, but the latter is impossible as x is join-irreducible. Thus, K x S = S and S ∈ C(y). As S = S we get {S | S ∈ C(y)} ⊇ {S | S ∈ C K x (y)}, and consequently

{S | S ∈ C(y)} = {S | S ∈ C K x (y)}.
The following two theorems establish a crucial property of

L ∞ × L op ∞ , namely, that in L ∞ × L op
∞ there is at least one noncapped compact bi-ideal, and that all noncapped compact bi-ideals are "almost" identical.

Theorem 2. The set E = {(x, y) | x ≤ y} is a noncapped compact bi-ideal in L ∞ × L op ∞ .
Proof. For every element x ∈ L - ∞ the pair (x, x) lies in E. Additionally, x ⊗ x is the only pure tensor which is a subset of E and which contains (x, x) as en element. This means that the smallest representation of E as a union of pure tensors is

E = (x ⊗ x | x ∈ L - ∞ )
, which is obviously infinite, thus proving that E is noncapped.

On the other hand, we use the fact that the elements a 1 , . . . , a 9 generate entire L ∞ , thus by Proposition 3 the set E can be represented as

E = (x ⊗ x | x ∈ L ∞ ) = (p(a 1 , . . . , a 9 ) ⊗ p op (a 1 , . . . , a 9 ) | p ∈ F(n)) = (a i ⊗ a i | i = 1, . . . , 9) .
So, E is a join of the finite number of pure tensors, and thus it is compact.

Lemma 11. Let I be a noncapped compact bi-ideal in L ∞ × L op ∞ , I = (a i ⊗ b i | i < N ) . Let ϕ I = ε -1 (X), ϕ E = ε -1 (E).
Then ϕ I differs from ϕ E only in a finite number of elements.

Proof. Let ξ be the isotone step function from L 0 ∞ to L op ∞ obtained from the elements a i and b i , i < N by formula [START_REF] Fraser | The semilattice tensor product of distributive semilattices[END_REF], that is,

ξ(x) = (b i | i < N, x ≤ a i ) ,
The base of induction is given by ξ (0) x0 (y) = ξ x0 (y) = ξ (0) (y), for all y ∈ (L x0 ∞ ) 0 , which is trivial. On the other hand, by (3 ) we get

ξ (n+1) (y) = ξ (n) [S] | S ∈ C(y) ,
for all n > 0 and all y ∈ (L x0 ∞ ) 0 . If S ∈ C(x 0 ) then ξ (n) [S] = 1, and thus the above statement can be rewritten as

ξ (n+1) (y) = ξ (n) [S] | S ∈ C(y) -C(x 0 ) . By Lemma 10, C(y) -C(x) = C L x ∞ (y) -C(x) and so ξ (n+1) (y) = ξ (n) [S] | S ∈ C L x ∞ (y) -C(x 0 ) = ξ (n) x0 [S] | S ∈ C L x ∞ (y) -C(x 0 ) ,
and by the same argument as above

ξ (n+1) (y) = ξ (n) x0 [S] | S ∈ C L x ∞ (y) = ξ (n+1) x0 (y). Thus, ξ (n) x0 (y) = ξ (n) (y) and consequently ξ (ω) x0 (y) = ξ (ω) (y), for all n > 0 and all y ∈ (L x0 ∞ ) 0 . Notice that ξ (ω) x0 is an element of L ∞ - → ⊗ (L x0 ∞ ) op and ξ (ω) x0 = ε(J) where J is the compact bi-ideal in L ∞ ⊗ (L x0 ∞ ) op , J = (a i ⊗ b i | i < N ) .
Let ψ J : L 1 ∞ → L ∞ be the meet-homomorphism defined by ψ J = η(J) = (ξ (ω) x0 ) * . Using the representation from Corollary 2 we get

J = ψ J (y) ⊗ y | y ∈ b i | i < N L x 0 ∞ = ψ J (y) ⊗ y | y ∈ L k0 L x 0 ∞ . By Lemma 7, the set L k0 L x ∞ is finite, thus J is capped. But from ξ (ω) x0 (y) = ξ (ω) (y) we get I = J ∪ (x 0 ⊗ ϕ I (x 0 )) , thus I is also capped, a contradiction. (vi) ρ (ω) (x) > 0 for all x ∈ L ∞ -L k0 .
Just as in (v), we take x 0 ∈ L ∞ -L k0 such that ρ (ω) (x 0 ) = 0, and by the same argument prove that ρ

(ω) = ρ (ω) x0 . As the bi-ideal J defined by ρ (ω) x0 is capped, then so is I, a contradiction. (vii) For every atom x from L ∞ such that x ∈ L k0 , ξ (ω) (x) is an atom in L ∞ .
Arguing by contradiction, take an atom x 0 ∈ L ∞ , x 0 ∈ L k0 such that u = ξ (ω) (x 0 ) is not an atom. By the above argument 0 < ξ (ω) (x 0 ) < 1, which means that u is a line. Similarly as in (v), we introduce the isotone step function ξ x0 : (L x0 ∞ ) 0 → L ∞ and argue by induction that the equality ξ (n) x0 (y) = ξ (n) (y) holds for all n > 0 and all y ∈ (L x0 ∞ ) 0 . The base of induction, n = 0, is obvious.

Notice that the sequence ξ (k) (x 0 ) | k < ω is decreasing in L ∞ , and all its elements lie in [ξ (ω) (x 0 ), 1] = {u, 1}. Thus, there exists a unique m such that ξ (i) (x 0 ) = 1 for i ≤ m and ξ (j) (x 0 ) = u for j ≥ m + 1. Then by (4 ) we get

u = ξ (m+1) (x 0 ) = ξ (m) [S] | S ∈ C * (x 0 ) .
Thus, there exists a join-cover S 0 ∈ C * (x 0 ) such that u = ξ (m) [S 0 ]. As S 0 is a nontrivial join-cover of x 0 , and as x 0 is an atom, and, consequently, is join-irreducible, it follows that S 0 = l > x 0 . As ξ (k) is isotone, we get ξ (k) (x 0 ) ≤ ξ (k) (l), for all k ≥ 0. On the other hand,

ξ (k) (l) ≤ ξ (m+1) (l) ≤ ξ (m) [S 0 ] = u = ξ (k) (x 0 ), for all k ≥ m + 1. And ξ (k) (l) ≤ 1 = ξ (k) (x 0 ), for all k ≤ m. Thus, ξ (k) (x 0 ) = ξ (k) (l)
, for all k ≥ 0. Notice also, that as ξ (m+1) (l) = u < 1, then by (i) we infer that x 0 < l < 1, thus l is a line. For a subset S ⊆ L ∞ let us define the subset S ⊆ L x0 ∞ by

S = S, x 0 ∈ S; S -{x 0 } + {l} x 0 ∈ S.
Notice that by the above argument we get ξ

(k) [S] = ξ (k) [S], for all k ≥ 0. By Lemma 10, {S | S ∈ C(y)} = {S | S ∈ C L x 0 ∞ (y)}, for all y ∈ L x0 ∞ . Now, let us prove the induction step ξ (n+1) (y) = ξ (n) [S] | S ∈ C(y) = ξ (n) [S] | S ∈ C(y) = ξ (n) x0 [S] | S ∈ C L x 0 ∞ (y) = ξ (n+1) x0 (y),
for all y ∈ L x0 ∞ . Then by the same argument as in (v) we infer that I is capped together with the compact bi-ideal J in L ∞ ⊗ (L x0 ∞ ) op , defined by J = (a i ⊗ b i | i < N ) , a contradiction. (viii) For every line l of L ∞ such that l ∈ L k0 , ρ (ω) (l) is a line in L ∞ .

Same argument as in (vii). (ix) For every line l of L ∞ such that l ∈ L k0+1 , ξ (ω) (l) is a line in L ∞ .

Arguing by contradiction, let us take a line l ∈ L ∞ such that l ∈ L k0+1 and a = ξ (ω) (l) is an atom in L ∞ . Now, take an atom y ≤ l. As l / ∈ L k0+1 and y is comparable with l then y / ∈ L k0 , and so by (vii) the element ξ (ω) (y) is an atom in L ∞ . But ξ (ω) (y) ≤ ξ (ω) (l) = a, and so ξ (ω) (y) = a.

Next, take a line p = l such that p ≥ y and let b = ξ (ω) (p). From the above argument, b is either a line or an atom. As p ≥ y then ξ (ω) (p) = b ≥ ξ (ω) (y) = a, and consequently ρ (ω) (b) ≥ ρ (ω) (a). But by Proposition 2 we get ρ (ω) (a) ≥ l and ρ (ω) (b) ≥ p. Thus ρ (ω) (b) ≥ l ∨ p = 1, a contradiction. (x) For every atom x from L ∞ such that x ∈ L k0+1 , ρ (ω) (x) is an atom in L ∞ .

Same argument as in (ix).

If we take r 0 = k 0 + 2 then ξ (ω) preserves heights of all elements in L ∞ -L r0-1 = L ∞ -L k0+1 . As all atoms and lines of P r0 lie in L ∞ -L r0-1 , then ξ (ω) preserves heights of all elements in P r0 .

We claim that the mappings ξ (ω) and ρ (ω) are one-to-one on P r0 . Indeed, take two distinct elements a 1 , a 2 ∈ P r0 and suppose that ξ (ω) (a 1 ) = ξ (ω) (a 2 ) = b. Then either all three elements a 1 , a 2 and b are atoms, or all three are lines. However, as ξ (ω) is a join-homomorphism then ξ (ω) (a 1 ∨ a 2 ) = b. But then the elements a 1 and a 1 ∨ a 2 have same heights, a contradiction. For ρ (ω) the argument is similar. Take

r 1 = max k | ∃x ∈ L ∞ -L k-1 : ξ (ω) (x) ∈ L r0 , r 2 = max k | ∃x ∈ L ∞ -L k-1 : ρ (ω) (x) ∈ L r0
and r = max(r 0 , r 1 , r 2 ).

Notice that as L r0 is finite and the mappings ξ (ω) and ρ (ω) are one-to-one, then the maximums in the above definitions exist, thus r 1 and r 2 are defined correctly. Then ξ (ω) and ρ (ω) preserve heights on L ∞ -L r , ξ (ω) (x) ∈ L ∞ -L r0 and ξ (ω) (x) ∈ L ∞ -L r0 , for all x ∈ L ∞ -L r , from which it follows that the mappings ρ (ω) • ξ (ω) and ξ (ω) • ρ (ω) also preserve heights on L ∞ -L r . Now we argue that ξ (ω) is a homomorphism on P r . Indeed, we already know that it is a join-homomorphism. From ( ‡) it follows that the inequalities x ≤ ρ (ω) • ξ (ω) (x) and

x ≥ ξ (ω) • ρ (ω) (x) hold, for all x ∈ L - ∞ , whenever ξ (ω) (x), ρ (ω) (x) ∈ L - ∞ . Then, as ξ (ω) • ρ (ω) and ξ (ω) • ρ (ω) preserve heights on L ∞ -L r , it follows that ρ (ω) • ξ (ω) (x) = x and ξ (ω) • ρ (ω) (y) = y, for all x, y ∈ L ∞ -L r . Thus ξ (ω) (a ∧ b) = ξ (ω) ρ (ω) ξ (ω) (a) ∧ ρ (ω) ξ (ω) (b) = ξ (ω) ρ (ω) ξ (ω) (a) ∧ ξ (ω) (b) = ξ (ω) (a) ∧ ξ (ω) (b).

Finally, we see that ξ (ω) is a one-to-one homomorphism from P r to L ∞ , thus, by Lemma 9 the homomorphism ξ (ω) is an identity mapping, which means that ξ (ω) (x) coincides with ϕ E (x) on P r . As L ∞ -P r is finite, this proves the lemma. Theorem 3. For every pair of compact bi-ideals I, J ∈ L ∞ ⊗ L op ∞ , the bi-ideal I ∩ J is compact.

Proof. If both I and J are capped then it is straightforward.

If I is capped and J is not, then one can write I = (x i ⊗ y i | i = 1, . . . , n). Then I ∩J = n i=1 (x i ⊗ y i ∩ J). As all nontrivial intervals in L ∞ and L op ∞ are finite, then every (x i ⊗ y i ∩ J) is a compact bi-ideal, and thus so is their finite union, so I ∩ J is compact.

Finally, if both I and J are not capped, then by Lemma 11 there is a finite k such that ϕ I∩J = ϕ I = ϕ J = ϕ E on L ∞ -L k , and so I ∩ J is also compact.

Finally, by putting together Theorems 2 and 3 we obtain immediately the following solution of Conjecture 1.

Theorem 4. The tensor product L ∞ ⊗ L op ∞ is noncapped and is a lattice.

  ordered componentwise. The arrow indicates the way homomorphisms go. Note that the elements of A -→ ⊗ B are antitone functions. With any element ϕ of A -→ ⊗ B we associate the subset ε(ϕ) of A × B:

=

  ϕ I holds. Thus, ϕ (α) I = ϕ I , for all α < ω+1. But then by Proposition 11 we obtain ξ (ω) ≤ ϕ (ω) I = ϕ I , which completes the proof.

Figure 2 .Figure 3 .

 23 Figure 2. Illustrating the construction CW

1 0a 1 Figure 4 .

 114 Figure 4. The lattice L 0

  Z n+1 = CW then by the above argument we get φ(ab) = ab, and φ(ab * ) = φ(ce) = ce. As φ(c) = φ(h) = 5, we get φ(c) = c, φ(e) = e and φ(h) = h. Now we use θ CW to determine the values of φ on the remaining marked elements. From θ CW (φ(d)) = {c, e, h, φ(f )} we get φ(d) = d and φ(f ) = f . From θ CW (φ(g)) = {e, f, h, φ(i)} we get φ(g) = g and φ(i) = i. And from θ CW (φ(b)) = {c, i, φ(a)} we get φ(b) = b and φ(a) = a. Thus, φ is an identity. If Z n+1 = CCW then by considering CCW we get φ(ch) = ch, and φ(ch * ) = φ(dg) = dg. Thus, either φ(h) = h, or φ(h) = c. But in the latter case we get θ CCW (φ(h)) = {φ(b), φ(c), φ(e)} = {f, g, h}, which is impossible because CCW (b) = 5 and so φ(b) ∈ {a, b}. Thus, φ(h) = h and consequently φ(c) = c. Also from θ CCW (φ(h)) = {φ(b), c, φ(e)} = {b, c, e} we get φ(b) = b, φ(e) = e and as CCW (a) = 5 then φ(a) = a. From θ CCW (φ(g)) = {a, b, c, φ(d)} we get φ(g) = g and φ(d) = d. And from θ CCW (φ(i)) = {a, d, e, φ(f )} we get φ(i) = i and φ(f ) = f . Again, φ is an identity.

Table 1 .

 1 below. The functions CW , CCW , θ CW and θ CCW .

	x CW x CCW x	x θ CW (x)	θ CCW (x)
	a	3	5	a	b, c, h	d, e, f, g, i
	b	3	5	b	a, c, i	d, e, f, g, h
	c	5	3	c a, b, d, e, i	f, g, h
	d	4	4	d c, e, f, h	a, b, g, i
	e	4	4	e	c, d, f, g	a, b, h, i
	f	4	4	f	d, e, g, h	a, b, c, i
	g	4	4	g	e, f, h, i	a, b, c, d
	h	5	3	h a, d, f, g, i	b, c, e
	i	4	4	i	b, c, g, h	a, d, e, f

In particular, CW x = |θ CW (x)| and CCW x = |θ CCW (x)|, for any marked element x of L.

producing three new marked elements, u 1 , u 2 and u 3 . For example, for the atom a and the operator CW the corresponding lines would be ab, ha and ac, and the corresponding atoms would be a 1 = ab • ce, f 1 = f g • ha and h 1 = hi • ac. Thus, Cn(x) ⊇ Cn(u 1 , u 2 , u 3 ).

Again by Proposition 13, only two out of the three elements u 1 , u 2 , u 3 can produce three lines, at least one produce four or more. Say, if we consider the marked elements a, f and h, and the operator is CCW, then there are four lines and, correspondingly, four atoms generated from f , namely lines f a, cf , f i and bf , and atoms b 1 = be • f a, c 1 = cf • gb, f 1 = f i • ae and g 1 = ga • bf . In any case, there are at least four distinct marked elements v

L); this way the elements v 1 , . . . , v 4 lie in {s 0 , . . . , s 8 }. For any i ∈ {0, . . . , 8}, the element t i lies outside of Cn(v 1 , . . . , v 4 ) iff no v j lies in Bs W3 (t i ). As |{s 0 , . . . , s 8 } -{v 1 , . . . , v 4 }| = 5, then by Lemma 4 it follows that at most two elements from t 0 , . . . , t 7 and possibly the element t 8 are outside of Cn(v 1 , . . . , v 4 ). So there are at most three elements outside of Cn(v 1 , . . . , v 4 ), and thus at least six elements w 1 , . . . , w 6 in Cn(v 1 , . . . , v 4 ).

Regarding the example, if we take the marked elements b, c, f , g and the operator CW, then every marked element of CW(L) lies in Cn(b, c, f, g). For the operator CCW, however, there are two marked elements, a 1 = ad • ei and e 1 = ef • gi that lie outside of Cn(b, c, f, g).

Finally, as |Bs W4 (x)| = 4, for any marked element x ∈ W 1...4 (L), and as there are at most three marked elements from W 1...3 (L) outside of Cn(v 1 , . . . , v 4 ), then all marked elements of W 1...4 (L) lie in Cn(v 1 , . . . , v 4 ), and, consequently, in Cn(x).

Lemma 8. Let L be an infinite normal lattice, L = Z(L 0 ), let L n [a n 1 , . . . , a n 9 ] = Z 1...n (L 0 ), and let φ be a one-to-one lattice homomorphism from a n 1 , . . . , a n 9 L to L. Then the following two statements hold:

(i) The heights of elements of L remain unaltered by the homomorphism φ.

(ii) The set {φ(a n 1 ), . . . , φ(a n 9 )} coincides with the set of marked elements of

As the lattice a n 1 , . . . , a n 9 L is infinite, and as all intervals of L, except for [0, 1], are finite, then φ(0) = 0 and φ(1) = 1. Now, suppose that φ(x) = l, for some atom x and line l. But then there is a line p ∈ a n 1 , . . . , a n 9 L , x < p, and so l < φ(p) < 1, which is impossible. Thus, φ(x) is an atom whenever x is an atom, and, by the similar argument, φ(l) is a line whenever l is a line.

(ii): We denote the set of marked elements of Z 1...k (L 0 ) by P k , for any k ≥ 0. Observe that the elements of P k are exactly the elements of L of rank 2k.

For a set X of atoms of L let us regard X as an undirected graph graph with respect to relation R = {(x, y) | x ∨ y is a line}. Then the set P k and, consequently, the set φ (P k ) are connected graphs. Let us denote the set of indexes I k = {i | P i ∩ φ (P k ) = ∅}. Note that if two atoms x ∈ P i and y ∈ P j join at a line, then either i = j ± 1 or i = j. This and the fact that P k is connected imply that I k is an interval in N , which we denote by [m k 0 , m k 1 ].

where

We denote the infinite zig-zag operator

We also denote the marked lattice Z 1...n (L 0 ) by L n , the set of marked elements of L n by P n , and the set of lines from which P n is generated by Q n . This way, P n is the set of all elements of rank 2n, and Q n of rank 2n -1. Now we are going to prove that the only automorphism of L ∞ is the trivial identity automorphism, in fact even a stronger property.

. Then the only one-to-one homomorphism from a n 1 , . . . , a n 9 L∞ to L ∞ is a trivial embedding x → x. Proof. Let φ be a one-to-one homomorphism from a n 1 , . . . , a n 9 L∞ to L ∞ , notice that {a n 1 , . . . , a n 9 } = P n . By Lemma 8 the homomorphism φ preserves heights of the elements of a n 1 , . . . , a n 9 L∞ , and φ[P n ] = P m for some m. Observe that the sets Q k+1 and P k+1 can be expressed as

for any k ≥ 0. From this representation it follows that φ [P n+d ] = P m+d and φ [Q n+d+1 ] = Q m+d+1 , that is, φ establishes a bijection between Q n+d+1 and Q m+d+1 , and between P n+d and P m+d , for any d ≥ 0.

We claim that for all d ≥ 0 and for all x ∈ P n+d the following equality holds

Indeed,

In particular, we get θ Z n+d+1 (x) = θ Z m+d+1 (φ(x)). Notice that as Z n+d+1 and Z m+d+1 are primitive zig-zag operators, then the notation θ Z n+d+1 and θ Z m+d+1 is justified.

Let us consider the case when m = n. We claim that in this case we can choose d ≥ 0 such that Z n+d+1 = CW and Z m+d+1 = CCW. Indeed, take N ≥ |m -n| and denote m 0 = N (N +1) 2 . Then by [START_REF] Grätzer | Tensor products of semilattices with zero, revisited[END_REF] we get Z m0 = CCW, and Z n0 = CW for all n 0 such that n 0 = m 0 and |n 0m 0 | ≤ N . Additionally, let N be big enough so that m < m 0 , and put

Denote the marked elements of P n+d by a, b, c, d, e, f, g, h, i and of P m+d by a, b, c, d, e, f , g, h, i. and let ρ : L 1 ∞ → L ∞ be its dual. Without loss of generality take a i > 0 and b i < 1, for all i < N . By Theorem 1 and Corollary 1, ϕ I = ξ (ω) and ϕ * I = ρ (ω) . We recall that ξ (ω) is a join-homomorphism from L 0 ∞ to L ∞ and ρ (ω) is a meethomomorphism from L 1 ∞ to L ∞ . Notice that both ξ (ω) and ρ (ω) are isotone mappings and the following statement holds (x, y) ∈ I ⇔ x = 0 or ξ (ω) (x) ≤ y ( ‡)

Fix k 0 such that a i , b i ∈ L k0 , for all i < N . Now, step by step, we prove that there is some r 0 such that ξ (ω) preserves heights of all elements in L 0 ∞ , except for the atoms and lines of L r0-1 ; that is, ξ (ω) maps points, lines and the unit of L 0 ∞ to points, lines and the unit of L ∞ correspondingly, or, alternatively, to lines, points and the zero of L op ∞ correspondingly. (i) ξ (ω) (1) = 1.

If ξ (ω) (1) = a < 1 then by ( ‡) we get 1 = ρ (ω) (a). Then

and by Corollary 2 we get

As the interval [0, a] is finite, I is a finite union of pure tensors and thus it is capped, a contradiction.

∞ , and the rest of the proof follows. (iii) ξ (ω) (x) > 0, for all x > 0.

If not, then ρ (ω) (0) ≥ x > 0, a contradiction. (iv) ρ (ω) (x) < 1, for all x < 1.

If not, then ξ (ω) (1) ≤ x < 1, a contradiction. (v) ξ (ω) (x) < 1, for all x ∈ L ∞ -L k0 .

Suppose otherwise, so there is x 0 ∈ L ∞ -L k0 such that ξ (ω) (x 0 ) = 1. Then ξ (n) (x 0 ) = 1, for all n < ω. Notice that x < 1 and x = a i , for all i < N . Let ξ x0 : (L x0 ∞ ) 0 → L ∞ be the isotone step function defined by (2 ), just as the function ξ, but with the domain (L x0 ∞ ) 0 instead of L 0 ∞ , that is

We claim that the following statement is true: For all n > 0 and for all y ∈ (L x0 ∞ ) 0 the equality ξ