Machine learning algorithms use error function minimization to fit a large set of parameters in a preexisting model. However, error minimization eventually leads to a memorization of the training dataset, losing the ability to generalize to other datasets. To achieve generalization something else is needed, for example a regularization method or stopping the training when error in a validation dataset is minimal. Here we propose a different approach to learning and generalization that is parameter-free, fully discrete and that does not use function minimization. We use the training data to find an algebraic representation with minimal size and maximal freedom, explicitly expressed as a product of irreducible components. This algebraic representation is shown to directly generalize, giving high accuracy in test data, more so the smaller the representation. We prove that the number of generalizing representations can be very large and the algebra only needs to find one. We also derive and test a relationship between compression and error rate. We give results for a simple problem solved step by step, hand-written character recognition, and the Queens Completion problem as an example of unsupervised learning. As an alternative to statistical learning, algebraic learning may offer advantages in combining bottom-up and top-down information, formal concept derivation from data and large-scale parallelization.

§ INTRODUCTION

Algebras have played an important role in logic and top-down approaches in Artificial Intelligence (AI) [1]. They are still an active area of research in information systems, for example in knowledge representation, queries and inference [2]. Machine learning (ML) branched out from AI as a bottom-up approach of learning from data. Here we show how to use an algebraic structure [3] to learn from data. This research programme may then be seen as a proposal to naturally combine top-down and bottom-up approaches. More specifically, we are interested in an approach to learning from data that is parameter-free and transparent to make analysis and formal proofs easier. Also, we want to explore the formation of concepts from data as transformations that lead to a large reduction of the size of an algebraic representation.

We show how to express learning problems as elements and relationships in an extended semilattice algebra. We give a concrete algebraic algorithm, the Sparse Crossing, that finds solutions as sets of atomic elements, or atoms. Learning takes place by algebraic transformations that minimize the number of atoms. The algorithm is stochastic and discrete with no floating point operations.

The algebraic approach has important differences to more standard approaches. It does not use function minimization. Minimizing functions has proven very useful in ML. However, the functions typically used have complex geometries with local minima. Navigating these surfaces often requires large datasets and special methods to avoid getting stuck in the local minima. These surfaces depend on many parameters that might need tuning with heuristic procedures.

Instead of function minimization, our algebraic algorithm uses cardinal minimization. i.e. minimization of the number of atoms. It learns smoothly, with error rates in the test set decreasing with the number of training examples and with no risk of getting trapped in local minima. We found no evidence of overfitting using algebraic learning, so we do not use a validation dataset. Also, it is parameter-free, so there is no need to prealocate parameter values like a network architecture, with the algebra growing by itself using the training data.

We studied Algebraic Learning in four examples to illustrate different properties. We start with the toy supervised problem of learning to classify images by whether they contain a vertical bar or not. The simplicity of this problem allows for analysis. We show how algebraic learning explicitly finds that the positive examples are indeed those that contain a vertical bar. We show also that the number of solutions with low error is astronomically large and the learning algorithm just needs to find one of them. This might also be the case in other systems, but for algebras it can be demonstrated.

Algebraic Learning is designed to compress training examples into atoms and not directly aimed at reducing the error. For this reason, we had to establish a relationship between compression and accuracy. We found that an algebra picked at random among the ones obeying the training examples has an error rate in test data inversely proportional to compression. We tested this theoretical result against experimental data obtained applying the Sparse Crossing algorithm to the problem of distinguishing images with even number of vertical bars from those with an odd number of bars. We found that Sparse Crossing is as at least as efficient in transforming compression into accuracy and fits very well the theoretical result when error rate is small.

We also tested the performance of algebraic learning in handwritten character classification. We used a single abstraction stage (a single processing layer) operating in raw data, without preprocessing and with a training set that contains miss-labels. Algebraic learning achieves a good accuracy of about $99\%$ when distinguishing a digit from the rest. This is done with no overfitting and even when accuracy is not an explicit target of the algorithm.

Our last example is the $N$-blocked $M\times M$ Queens Completion problem. Starting from $N$ blocked queens on an $M\times M$ chessboard, we need to place $M-N$ queens on the board in non-attacking positions. We encode board and attack rules as algebraic relations, and show that Algebraic Learning generates complete solutions for the standard $8 \times 8$ board and also in larger boards. Learning in this example is unsupervised, with the algebra learning the structure of the search space.

§ THE EMBEDDING ALGORITHM

§.§ A toy problem illustrating algebraic learning

Consider the very simple problem of learning how to classify $2 \times 2$ images in which pixels can be in black or white. We will learn how to classify these images into two classes using as training data the following five examples

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[thick] (3,0)–(5,0);
[thick] (4,0)–(4,2);
[thick] (5,0)–(5,2);
[thick] (3,0)–(3,2);
[thick] (3,2)–(5,2);
[thick] (3,1)–(5,1);

[fill=black] (4,0) rectangle (5,2);

[thick] (5.5,-0.5)–(5.5,2.5);

[thick] (6,0)–(8,0);
[thick] (6,0)–(6,2);
[thick] (8,0)–(8,2);
[thick] (6,1)–(8,1);
[thick] (6,2)–(8,2);
[thick] (7,0)–(7,2);

[fill=black] (6,1) rectangle (7,2);
[fill=black] (7,0) rectangle (8,1);

[thick] (9,0)–(11,0);
[thick] (10,0)–(10,2);
[thick] (11,0)–(11,2);
[thick] (9,0)–(9,2);
[thick] (9,2)–(11,2);
[thick] (9,1)–(11,1);

[fill=black] (10,1) rectangle (11,2);

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

We label the two examples on the left as belonging to the  positive class because they include a black vertical bar, and name them as $T_{1}^{+}$ and $T_{2}^{+}$. The three examples on the right are the  negative class, $T_{1}^{-}$, $T_{2}^{-}$ and $T_{3}^{-}$. Our goal is to build an algebra that can learn from the training how to classify new images as belonging to the positive or negative class.

§.§ Elements of the algebra

To embed a problem into an algebra we need the algebra to have at least one operator that is idempotent, associative and commutative. In this paper we use semilattices, the simplest algebraic structures with such operator.

We will have three types of elements: constants, terms and atoms. Constants are the primitive description elements of our embedding problem. For images, for example, constants can be each of the pixels in black or white. For our $2 \times 2$ images we would then have the $8$ constants

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

that we write as $c_{1}$ to $c_8$.

The terms are formed by operating constants with the merge (or idempotent summation) operation, for which we use the symbol $\odot$.  This is our binary operation that is commutative, associative and idempotent. In the case of terms describing images, terms are sets of pixels. For example, the first example in the training set is a term that can be expressed as the merge of four constants as

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[text width=0.1cm] at (2.9,0.9)

[thick] (4.25,1.5)–(5.25,1.5);
[thick] (4.25,0.5)–(5.25,0.5);
[thick] (4.25,0.5)–(4.25,1.5);
[thick] (5.25,0.5)–(5.25,1.5);

[fill=black] (4,0.25) rectangle (4.5,0.75);

[text width=0.1cm] at (6,0.9)

[thick] (7.25,1.5)–(8.25,1.5);
[thick] (7.25,0.5)–(8.25,0.5);
[thick] (8.25,0.5)–(8.25,1.5);
[thick] (7.25,0.5)–(7.25,1.5);

[fill=black] (7,1.25) rectangle (7.5,1.75);

[text width=0.1cm] at (9,0.9)

[thick] (10.25,1.5)–(11.25,1.5);
[thick] (10.25,0.5)–(11.25,0.5);
[thick] (11.25,0.5)–(11.25,1.5);
[thick] (10.25,0.5)–(10.25,1.5);

[fill=white] (11,1.25) rectangle (11.5,1.75);

[text width=0.1cm] at (12.25,0.9)

[thick] (13.5,1.5)–(14.5,1.5);
[thick] (13.5,0.5)–(14.5,0.5);
[thick] (14.5,0.5)–(14.5,1.5);
[thick] (13.5,0.5)–(13.5,1.5);

[fill=white] (14.25,0.25) rectangle (14.75,0.75);

Atoms are elements created by the learning algorithm, and we reserve greek letters for them. Similarly to terms being a merge of constants, $\odot_{i} c_{i}$, each constant is a merge of atoms, $\odot_{i} \phi_{i}$. A term is therefore also a merge of atoms.

An idempotent operator defines a partial order. Specifically, the merge operator allows us to establish the inclusion relationship $<$ between elements $a$ and $b$ of the algebra, $a<b$, iff $a \odot b = b$. Take as example our first training image, which was the merge of four constants, $T_{1}^{+}=c_{1} \odot c_{2} \odot c_{7} \odot c_{8}$. Any of these constants, say $c_{1}$, obeys $c_{1} < T_{1}^{+}$, because $c_{1} \odot T_{1}^{+}=T_{1}^{+}$. Similarly, for a constant made of atoms, each of these atoms is in or included in the constant.

The training set of the algebra consists of a set $R$ of positive and negative relations of the form $(v<T_{1}^{+})$ or $\neg(v<T_{3}^{-})$ where $v$ is a constant, one we want to describe to our algebra by using examples and counterexamples.

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[text width=0.1cm] at (-3,1)
[text width=0.1cm] at (-1.7,1)

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

[text width=0.1cm] at (9,1)
[text width=0.1cm] at (10.7,1)

The learning algorithm transforms semilattices into other semilattices in a series of steps until finding one that satisfies the training set $R$. Using Model Theory[4] jargon, we want to find a model of the theory of semilattices extended with a set of literals (the training set $R$).

§.§ Graph of the algebra

We use a graph to make the abstract notion of algebra more concrete and computationally amenable. Nodes in the graph $G$ are elements of the algebra. An enormous amount of terms can be defined from a set of constants. The graph has nodes only for the subset of terms mentioned in the training relations plus the pinning terms, terms that are calculated by the embedding algorithm and that we introduce later. We do not need to have a node for each possible term or element of the algebra.

A directed edge $a \rightarrow b$ is used to represent some of the inclusion relationships between elements, but not all,

\begin{equation}
a\rightarrow b \,\, \Rightarrow \,\, a < b,
\end{equation}

where the implication only holds left to right. We add to the graph edges pointing from the component constants of a term to the node of the term. If a term $T$ is defined as the merge of constants $c_i$ then

\begin{equation}
T\equiv \odot_i c_i \,\, \Rightarrow \,\, \forall i(c_i \rightarrow T).
\end{equation}

If all the component constants of a term $T$ are also component constants of another term $S$ we add the edge $T \rightarrow S$.  We always use edges if any of the elements involved are atoms,

\begin{equation}
\phi \rightarrow b \,\, \Leftrightarrow \,\, \phi < b.
\end{equation}

Graph edges can be seen as a graphical representation of an additional relation defined in our algebra that is transitive but not commutative. Graphs represent algebras only when they are transitively closed with respect to the edges. Directed edges are typically represented with arrows. However, to avoid clutter we use simple straight lines instead of arrows pointing upwards in the figures, which is unambiguous because $G$ is acyclic.  Also to avoid clutter, in the drawings we do not plot all implicit edges (for example, from atoms to terms). We also add a $0$ atom included in all constants. This is not strictly necessary but will make exposition simpler. Our starting graph has already the form

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[thick] (3,0)–(5,0);
[thick] (4,0)–(4,2);
[thick] (5,0)–(5,2);
[thick] (3,0)–(3,2);
[thick] (3,2)–(5,2);
[thick] (3,1)–(5,1);

[fill=black] (4,0) rectangle (5,2);

[thick] (5.5,-0.5)–(5.5,2.5);

[thick] (6,0)–(8,0);
[thick] (6,0)–(6,2);
[thick] (8,0)–(8,2);
[thick] (6,1)–(8,1);
[thick] (6,2)–(8,2);
[thick] (7,0)–(7,2);

[fill=black] (6,1) rectangle (7,2);
[fill=black] (7,0) rectangle (8,1);

[thick] (9,0)–(11,0);
[thick] (10,0)–(10,2);
[thick] (11,0)–(11,2);
[thick] (9,0)–(9,2);
[thick] (9,2)–(11,2);
[thick] (9,1)–(11,1);

[fill=black] (10,1) rectangle (11,2);

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-0.3)–(0.25,-3.7);
[thin] (1,-0.3)–(2,-3.7);
[thin] (1,-0.3)–(10.75,-3.7);
[thin] (1,-0.3)–(12.5,-3.7);

[thin] (4,-0.3)–(5.5,-3.7);
[thin] (4,-0.3)–(3.75,-3.7);
[thin] (4,-0.3)–(7.25,-3.7);
[thin] (4,-0.3)–(9,-3.7);

[thin] (7,-0.3)–(2,-3.7);
[thin] (7,-0.3)–(5.5,-3.7);
[thin] (7,-0.3)–(7.25,-3.7);
[thin] (7,-0.3)–(10.75,-3.7);

[thin] (10,-0.3)–(3.75,-3.7);
[thin] (10,-0.3)–(7.25,-3.7);
[thin] (10,-0.3)–(9,-3.7);
[thin] (10,-0.3)–(12.5,-3.7);

[thin] (13,-0.3)–(5.5,-3.7);
[thin] (13,-0.3)–(7.25,-3.7);
[thin] (13,-0.3)–(9,-3.7);
[thin] (13,-0.3)–(10.75,-3.7);

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (6.7,-7.6)

[thin] (7,-7)–(-3,-5.3);

[thin] (7,-7)–(12.5,-5.3);
[thin] (7,-7)–(10.75,-5.3);
[thin] (7,-7)–(9,-5.3);
[thin] (7,-7)–(7.25,-5.3);
[thin] (7,-7)–(5.5,-5.3);
[thin] (7,-7)–(3.75,-5.3);
[thin] (7,-7)–(2,-5.3);
[thin] (7,-7)–(0.25,-5.3);

From the edges we define the partial order $<$ as

\begin{equation}
\label{inclusionDef}
\forall\phi ((\phi \not\rightarrow a) \vee (\phi \rightarrow b)) \,\, \Leftrightarrow \,\, a < b,
\end{equation}

where the universal quantifier runs over all atoms. The formula says that $a<b$ if and only if all the atoms edged to $a$ are also edged to $b$.

When the graph is transitively closed it describes an algebra we call $M$. This algebra evolves during the learning process producing a model of the training relations $R$ at the end of the embedding. When we talk about $M$ we mean the algebra described by the graph at a given stage of the algorithm.

§.§ The dual algebra

The algebraic manipulations we need to do are easier to perform using not only the algebra $M$ but also an auxiliary structure $M^{*}$. This $M^{*}$ is a semilattice closely related (but different) to the dual of $M$ [3], that we still call the dual and whose properties we detail in this section. We also use an extended algebraic structure $S$ that contains both semilattices $M$ and $M^*$, which have universes that are disjoint sets, i.e, an element of $S$ is either and element of $M$ or an element of $M^*$. The unary function $[ \ ]$ defined for $S$ maps the elements of $M$, say $a$ and $b$, into the elements $[a]$ and $[b]$ in $M^*$, that we call duals of $a$ and $b$. The duals of constants and terms are always constants and the dual of atoms are a new kind of element we name dual-of-atom. $M^{*}$ has constants, dual-of-atoms and atoms but it does not contain terms. Atoms of $M^{*}$ are not duals of any element of $M$. We refer to $M^{*}$ as the dual algebra and to $M$ as the master algebra.

Our algebra $S$ is characterized by the transitive, noncommutative relation $\rightarrow$, the partial order $<$ and the unary operator $[ \ ]$. Besides the transitivity of $\rightarrow$ and the definition of $<$ given by Equation (<ref>) we introduce the additional axiom,

\begin{equation}
a\rightarrow b \,\, \Rightarrow \,\, [b] \rightarrow [a],
\end{equation}

that, again, only works from left to right. It means that the edges of the graph of $M$ are also edges of the graph of $M^*$ albeit reversed.

The auxiliary semilattice $M^*$ contains the images of the elements of $M$ under the unary operator $[ \ ]$, and has the reversed edges of $M$ plus some additional edges of its own and its own atoms. We introduced edges in $M$ to encode definitional relations like how a given training image (a term) is made up of particular pixels constants. In $M^*$ we add additional edges for the positive order relations of $R$ such as $v<T_{1}^{+}$,

\begin{equation}
[T_{1}^{+}] \rightarrow [v].
\end{equation}

Positive order relations of our choosing are encoded with edges in $M^*$ and emerge in $M$ as reversed order relations, i.e. we get $(v<T_{1}^{+})$ from $[T_{1}^{+}] \rightarrow [v]$ at some point of the embedding process.

The graph of the dual $M^*$ has all the reversed edges of $M$ plus the edges corresponding to the positive order relations of $R$ and it should be also transitively closed. In this classification example, our training relations establish that $v$ is included in the positive training terms $T_{1}^{+}$ and $T_{2}^{+}$, so there are edges from the duals of both terms to the dual of $v$. Note again that these type of edges for relations of $R$ are not in the graph of $M$.

[thick] (0,-11)–(2,-11);
[thick] (1,-11)–(1,-9);
[thick] (2,-11)–(2,-9);
[thick] (0,-11)–(0,-9);
[thick] (0,-9)–(2,-9);
[thick] (0,-10)–(2,-10);

[fill=black] (0,-11) rectangle (1,-9);

[thick] (3,-11)–(5,-11);
[thick] (4,-11)–(4,-9);
[thick] (5,-11)–(5,-9);
[thick] (3,-11)–(3,-9);
[thick] (3,-9)–(5,-9);
[thick] (3,-10)–(5,-10);

[fill=black] (4,-11) rectangle (5,-9);

[thick] (5.5,-11.5)–(5.5,-8.5);

[thick] (6,-11)–(8,-11);
[thick] (7,-11)–(7,-9);
[thick] (8,-11)–(8,-9);
[thick] (6,-11)–(6,-9);
[thick] (6,-9)–(8,-9);
[thick] (6,-10)–(8,-10);

[fill=black] (6,-10) rectangle (7,-9);
[fill=black] (7,-11) rectangle (8,-10);

[thick] (9,-11)–(11,-11);
[thick] (10,-11)–(10,-9);
[thick] (11,-11)–(11,-9);
[thick] (9,-11)–(9,-9);
[thick] (9,-9)–(11,-9);
[thick] (9,-10)–(11,-10);

[fill=black] (10,-10) rectangle (11,-9);

[thick] (12,-11)–(14,-11);
[thick] (13,-11)–(13,-9);
[thick] (14,-11)–(14,-9);
[thick] (12,-11)–(12,-9);
[thick] (12,-9)–(14,-9);
[thick] (12,-10)–(14,-10);

[fill=black] (13,-11) rectangle (14,-10);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-8.7)–(0.25,-5.3);
[thin] (1,-8.7)–(2,-5.3);
[thin] (1,-8.7)–(10.75,-5.3);
[thin] (1,-8.7)–(12.5,-5.3);

[thin] (4,-8.7)–(3.75,-5.3);
[thin] (4,-8.7)–(5.5,-5.3);
[thin] (4,-8.7)–(7.25,-5.3);
[thin] (4,-8.7)–(9,-5.3);

[thin] (7,-8.7)–(2,-5.3);
[thin] (7,-8.7)–(5.5,-5.3);
[thin] (7,-8.7)–(7.25,-5.3);
[thin] (7,-8.7)–(10.75,-5.3);

[thin] (10,-8.7)–(3.75,-5.3);
[thin] (10,-8.7)–(7.25,-5.3);
[thin] (10,-8.7)–(9,-5.3);
[thin] (10,-8.7)–(12.5,-5.3);

[thin] (13,-8.7)–(5.5,-5.3);
[thin] (13,-8.7)–(7.25,-5.3);
[thin] (13,-8.7)–(9,-5.3);
[thin] (13,-8.7)–(10.75,-5.3);

[text width=0.1cm] at (-3.25,-4.5)

[text width=0.1cm] at (7,-13.5)

[text width=0.1cm] at (6.4,-2)

[thin] (7,-13)–(1,-11.3);
[thin] (7,-13)–(13,-11.3);
[thin] (7,-13)–(4,-11.3);
[thin] (7,-13)–(7,-11.3);
[thin] (7,-13)–(10,-11.3);

[thin] (1,-8.7)–(-2.8,-5.3);
[thin] (4,-8.7)–(-2.8,-5.3);

[thin] (7,-2.7)–(-2.8,-3.7);
[thin] (7,-2.7)–(12.5,-3.7);
[thin] (7,-2.7)–(10.75,-3.7);
[thin] (7,-2.7)–(9,-3.7);
[thin] (7,-2.7)–(7.25,-3.7);
[thin] (7,-2.7)–(5.5,-3.7);
[thin] (7,-2.7)–(3.75,-3.7);
[thin] (7,-2.7)–(2,-3.7);—
[thin] (7,-2.7)–(0.25,-3.7);

At the top of the graph of $M^{*}$ we draw the duals of the atoms of $M$, here only $[0]$, and at the bottom of the graph we draw the atoms of $M^{*}$, here $0^*$, again included to make our exposition simpler.

§.§ Atomized models

Equation (<ref>) defines how to derive the partial order from the transitive, noncommutative edge relation $\rightarrow$ and an special kind of elements we call atoms. We say that a model for which there is a description of the partial order in terms of a set of atoms is an atomized model.  In an atomized model all elements are sets of atoms. Using the language of Universal Algebra, when an algebra is atomized it explicitly becomes a direct product of directly idecomposable algebras [3]. This does not mean, however, that we are restricting ourselves to some subset of possible models. The Stone theorem grants that any semilattice model can be described as an atomized model [3].

We know how to derive the partial order from the atoms and edges but we have not given yet a definition for the idempotent operator.  The merge (or idempotent summation) of $a$ and $b$ is the element of the algebra atomized by a set of atoms that is the union of the atoms edged to $a$ and the atoms edged to $b$. The idempotent operator becomes a trivial set union of atoms. Obviously this operation is idempotent, commutative and associative. It is also consistent with our partial order given in equation <ref> that satisfies $a<b$ iff $a \odot b=b$. Consistently, the partial order becomes the set inclusion.

Before we continue with the embedding algorithm we are going to introduce some notation and redefine the problem we are trying to solve in terms of sets of atoms. In Appendix <ref> we define some useful sets. For the moment it is enough to consider the set ${\bf{GL}^{a}}(x)$ which is simply the set of atoms edged to element $x$ that is defined, as always, only when the graph is transitively closed. The G refers to the graph, the L to the lower segment and the superscript a to the atoms. The merge of $a$ and $b$ corresponds with the set of atoms

\begin{equation}
{\bf{GL}^{a}}(a \odot b)={\bf{GL}^{a}}(a) \cup {\bf{GL}^{a}}(b).
\label{eq:positive_encoding}
\end{equation}

For our toy problem, we want a description of the constant $v$ and for the pixels (also constants) as a sets of atoms. Specifically, we want a model for which $v$ is a set included in the positive training images, ${T_{1}^{+}}$ and ${T_{2}^{+}}$ as

\begin{equation}
v<T_{i}^{+} \,\, \Leftrightarrow \,\, {\bf{GL}^{a}}(v) \subset {\bf{GL}^{a}}(T_{i}^{+}),
\label{eq:positive_encoding}
\end{equation}

where the atoms of a term are the union of the atoms of its component constants. We are also looking for a particular atomic model for which the atoms of constant $v$ are not all in the terms corresponding with negative training examples

\begin{equation}
v\not <T_{i}^{-} \,\, \Leftrightarrow \,\,  {\bf{GL}^{a}}(v) \not \subset {\bf{GL}^{a}}(T_{i}^{-}).
\label{eq:negative_encoding}
\end{equation}

The difficulty in finding the model lies in enforcing positive and negative training relations simultaneously, which translates in resolving a large system of equations and inequations over sets. The sets are made of elements we create in the process, the atoms, and there is the added difficulty of finding sets as small and as random (or as free) as possible. In Sections <ref> we introduce the concept of algebraic freedom and discuss its connection with randomness.

We will use an operation, the crossing, to enforce positive relations one by one. By doing so the model evolves through a series of semilattice models, all atomized, until becoming the model we want.  We can build the model step by step thanks to an invariance property related to a construct we name trace. In the next sections we explain the trace and the crossing operation. After this we will show how to further reduce the size of model with a reduction operation and how to do batch training. We will explain these operations for our toy example explicitly, and also give an analysis of the exact and approximate solutions.

§.§ Trace and trace constraints

The trace is central for the embedding procedure as a guiding tool for algebraic transformations. By operating the algebra while keeping the trace of some elements invariant, we can control the global effects caused by our local changes.

The trace $\textbf{Tr} (x)$ maps an element $x \in M$ to a set of atoms in $M^{*}$. To calculate the trace of $x$, we find first its atoms in the graph of $M$, which we write as ${\bf{GL}^{a}}(x)$. Say these are $N$ atoms ${\phi_i}$, with $\phi_{i} \rightarrow x$. Since atoms are minima of $M$, dual of atoms are maxima of $M^{*}$, so for each atom $\phi_{i}$ of $x$ there is a dual-of-atom at the top of the graph of $M^{*}$, $[\phi_i]$. Each of these $[\phi_i]$ also have an associated set of atoms in $M^{*}$, ${\bf{GL}^{a}}([\phi_{i}])$. The trace of $x$ is defined as the intersection of these $N$ sets, ${\bf{Tr}}(x)=\bigcap_{i =1,2,...,N} {\bf{GL}^{a}}([\phi_i])$. Consistently, the trace of an atom $\phi$ equals ${\bf{Tr}}(\phi) \equiv {\bf{GL}^{a}}([\phi])$. In general we can write the trace as

\begin{equation}
\label{deftrace}
{\bf{Tr}}(x) \equiv \cap_{\phi \in {\bf{GL}^{a}}(x)} {\bf{GL}^{a}}([\phi]).
\end{equation}

From this definition it follows that the trace has the linearity property

\begin{equation}
{\bf{Tr}}(a \odot b)={\bf{Tr}}(a) \cap {\bf{Tr}}(b),
\end{equation}

as the atoms in $M$ for $a \odot b$ are the union of the atoms of $a$ and the atoms of $b$ and therefore the trace is the intersection of the traces of $a$ and $b$. From this linearity and the definition of the order relation, $a<b$ iff $a \odot b=b$, it follows that an order relation is related to the traces as

\begin{equation}
a < b \,\, \Rightarrow \,\, {\bf{Tr}}(b) \subset {\bf{Tr}}(a).
\end{equation}

This makes a correspondence between order relations in $M$ and trace interrelations between $M$ and $M^*$ that we call trace constraints. For our toy problem, we are interested in obeying trace constraints for the positive training examples, $v<T_{i}^{+}$, for which we then need to enforce ${{\bf{Tr}}(T_{i}^{+}) \subset \bf{Tr}}(v)$,

\begin{equation}
\textnormal{for} \ v<T_{i}^{+} \ \textnormal{enforce} \ {\bf{Tr}}(T_{i}^{+}) \subset {\bf{Tr}}(v).
\end{equation}

This does not cause $v<T_{i}^{+}$ but it provides a necessary starting point. For negative training examples, $T_{i}^{-}$, we want to obey that $\neg(v < T_{i}^{-})$. This inclusion does not follow from (<ref>), however, it can always be enforced if the embedding strategy is consistent as

\begin{equation}
\textnormal{for} \ \neg(v < T_{i}^{-}) \ \textnormal{enforce} \ {\bf{Tr}}(T_{i}^{-}) \not\subset {\bf{Tr}}(v).
\end{equation}

Once the trace constraint is met, no transformation of $M$ can produce $v < T_{i}^{-}$ unless it alters the traces. This constraint prevents positive relations to appear in $M$ in places where we do not want them.

While the operator $[ \ ]$ does not really map $M$ into its dual semilattice, the traces of the elements of $M$ form an algebra that very much resembles the dual of $M$. This new algebra has trace constraints in the place of order relations and set intersections in the place of set unions. There are still some subtle differences between a proper dual of $M$ and the dual algebra provided by the trace. For example, the trace is defined with the atoms of $M$ instead of the constants of $M$, so it depends on the particular atomization of $M$. While finding a proper dual of $M$ amounts in difficulty to calculate $M$ itself, enforcing the trace constraints is easier because we have the extra freedom of introducing new atoms in $M$. In addition, we do not have restrictions for the size of the traces. We do not care if the traces are large or small.

We want an atomization for $M$ but first we have to calculate an atomization for $M^{*}$. The atomization we are going to build for $M$ does not correspond with the dual of $M^{*}$, neither it corresponds with the dual of the algebra defined by the trace. It corresponds with an algebra freer than the algebra described by the traces. In Section <ref> we explain the role that algebraic freedom plays as a counterbalance to cardinal minimization.

Enforcing the trace constraints might look challenging but it is relatively simple. We are aided by the encoding of training relations $R$ as directed edges in the graph of $M^{*}$ so when the graph is transitively closed the reverted positive relations $[T_{i}^{+}] < [v]$ are always satisfied. We can start, although this step is optional, by first requiring $M^*$ to satisfy the reverted negative relations, positive and negative. That is, if we want to enforce $\neg(v < T_{i}^{-})$ in $M$, we enforce $\neg( [T_{i}^{-}] < [v])$ by adding an atom to $[T_{i}^{-}]$ in $M^{*}$. In our toy example, for every negative example $T_{i}^{-}$ we then add an atom $\xi_{i} \rightarrow [T_{i}^{-}]$, so in our example we introduce three atoms $\zeta_1$, $\zeta_2$ and $\zeta_3$ in the graph of $M^{*}$,

[thick] (0,-11)–(2,-11);
[thick] (1,-11)–(1,-9);
[thick] (2,-11)–(2,-9);
[thick] (0,-11)–(0,-9);
[thick] (0,-9)–(2,-9);
[thick] (0,-10)–(2,-10);

[fill=black] (0,-11) rectangle (1,-9);

[thick] (3,-11)–(5,-11);
[thick] (4,-11)–(4,-9);
[thick] (5,-11)–(5,-9);
[thick] (3,-11)–(3,-9);
[thick] (3,-9)–(5,-9);
[thick] (3,-10)–(5,-10);

[fill=black] (4,-11) rectangle (5,-9);

[thick] (5.5,-11.5)–(5.5,-8.5);

[thick] (6,-11)–(8,-11);
[thick] (7,-11)–(7,-9);
[thick] (8,-11)–(8,-9);
[thick] (6,-11)–(6,-9);
[thick] (6,-9)–(8,-9);
[thick] (6,-10)–(8,-10);

[fill=black] (6,-10) rectangle (7,-9);
[fill=black] (7,-11) rectangle (8,-10);

[thick] (9,-11)–(11,-11);
[thick] (10,-11)–(10,-9);
[thick] (11,-11)–(11,-9);
[thick] (9,-11)–(9,-9);
[thick] (9,-9)–(11,-9);
[thick] (9,-10)–(11,-10);

[fill=black] (10,-10) rectangle (11,-9);

[thick] (12,-11)–(14,-11);
[thick] (13,-11)–(13,-9);
[thick] (14,-11)–(14,-9);
[thick] (12,-11)–(12,-9);
[thick] (12,-9)–(14,-9);
[thick] (12,-10)–(14,-10);

[fill=black] (13,-11) rectangle (14,-10);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-8.7)–(0.25,-5.3);
[thin] (1,-8.7)–(2,-5.3);
[thin] (1,-8.7)–(10.75,-5.3);
[thin] (1,-8.7)–(12.5,-5.3);

[thin] (4,-8.7)–(3.75,-5.3);
[thin] (4,-8.7)–(5.5,-5.3);
[thin] (4,-8.7)–(7.25,-5.3);
[thin] (4,-8.7)–(9,-5.3);

[thin] (7,-8.7)–(2,-5.3);
[thin] (7,-8.7)–(5.5,-5.3);
[thin] (7,-8.7)–(7.25,-5.3);
[thin] (7,-8.7)–(10.75,-5.3);

[thin] (10,-8.7)–(3.75,-5.3);
[thin] (10,-8.7)–(7.25,-5.3);
[thin] (10,-8.7)–(9,-5.3);
[thin] (10,-8.7)–(12.5,-5.3);

[thin] (13,-8.7)–(5.5,-5.3);
[thin] (13,-8.7)–(7.25,-5.3);
[thin] (13,-8.7)–(9,-5.3);
[thin] (13,-8.7)–(10.75,-5.3);

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (1,-14.5)

[text width=0.1cm] at (6.4,-2)

[text width=0.1cm] at (7,-14.5)

[text width=0.1cm] at (10,-14.5)

[text width=0.1cm] at (13,-14.5)

[thin] (1,-13.9)–(1,-11.3);
[thin] (1,-13.9)–(13,-11.3);
[thin] (1,-13.9)–(4,-11.3);
[thin] (1,-13.9)–(7,-11.3);
[thin] (1,-13.9)–(10,-11.3);

[thin] (7,-13.9)–(7,-11.3);
[thin] (10,-13.9)–(10,-11.3);
[thin] (13,-13.9)–(13,-11.3);

[thin] (1,-8.7)–(-2.8,-5.3);
[thin] (4,-8.7)–(-2.8,-5.3);

[thin] (7,-2.7)–(-2.8,-3.7);
[thin] (7,-2.7)–(12.5,-3.7);
[thin] (7,-2.7)–(10.75,-3.7);
[thin] (7,-2.7)–(9,-3.7);
[thin] (7,-2.7)–(7.25,-3.7);
[thin] (7,-2.7)–(5.5,-3.7);
[thin] (7,-2.7)–(3.75,-3.7);
[thin] (7,-2.7)–(2,-3.7);
[thin] (7,-2.7)–(0.25,-3.7);

The new atoms are not in the set ${\bf{GL}^{a}}([v])$ so the reverted negative relations are satisfied. In fact all reverted relations, positive and negative, are satisfied at this point. We have now the chance to detect if the input order relations are inconsistent. First, make sure that for each couple of terms $T_{1}$ and $T_{2}$ mentioned in the input order relations such that the component constants of $T_{1}$ are a subset of those of $T_{2}$ we have added the edge $[T_{2}] \rightarrow [T_{1}]$. At this point, after transitive closure, the reverted order relations are satisfied if and only if the embedding is consistent.

If there are edges pointing in both directions between two elements of $M^{*}$ we can identify them as the same element. Two ore more elements of $M$ may share the same dual.

We have completed the preprocessing step that speeds up the enforcing of trace constraints and validates the consistency of the embedding. We start now enforcing the trace constraints for the negative examples, ${\bf{Tr}}(T_{i}^{-}) \not\subset {\bf{Tr}}(v)$. To compute the trace, we place the graph for $M$ and for $M^{*}$ side to side, to left and right, respectively

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[thick] (3,0)–(5,0);
[thick] (4,0)–(4,2);
[thick] (5,0)–(5,2);
[thick] (3,0)–(3,2);
[thick] (3,2)–(5,2);
[thick] (3,1)–(5,1);

[fill=black] (4,0) rectangle (5,2);

[thick] (5.5,-0.5)–(5.5,2.5);

[thick] (6,0)–(8,0);
[thick] (6,0)–(6,2);
[thick] (8,0)–(8,2);
[thick] (6,1)–(8,1);
[thick] (6,2)–(8,2);
[thick] (7,0)–(7,2);

[fill=black] (6,1) rectangle (7,2);
[fill=black] (7,0) rectangle (8,1);

[thick] (9,0)–(11,0);
[thick] (10,0)–(10,2);
[thick] (11,0)–(11,2);
[thick] (9,0)–(9,2);
[thick] (9,2)–(11,2);
[thick] (9,1)–(11,1);

[fill=black] (10,1) rectangle (11,2);

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-0.3)–(0.25,-3.7);
[thin] (1,-0.3)–(2,-3.7);
[thin] (1,-0.3)–(10.75,-3.7);
[thin] (1,-0.3)–(12.5,-3.7);

[thin] (4,-0.3)–(5.5,-3.7);
[thin] (4,-0.3)–(3.75,-3.7);
[thin] (4,-0.3)–(7.25,-3.7);
[thin] (4,-0.3)–(9,-3.7);

[thin] (7,-0.3)–(2,-3.7);
[thin] (7,-0.3)–(5.5,-3.7);
[thin] (7,-0.3)–(7.25,-3.7);
[thin] (7,-0.3)–(10.75,-3.7);

[thin] (10,-0.3)–(3.75,-3.7);
[thin] (10,-0.3)–(7.25,-3.7);
[thin] (10,-0.3)–(9,-3.7);
[thin] (10,-0.3)–(12.5,-3.7);

[thin] (13,-0.3)–(5.5,-3.7);
[thin] (13,-0.3)–(7.25,-3.7);
[thin] (13,-0.3)–(9,-3.7);
[thin] (13,-0.3)–(10.75,-3.7);

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (6.7,-7.9)

[thin] (7,-7.3)–(-3,-5.3);

[thin] (7,-7.3)–(12.5,-5.3);
[thin] (7,-7.3)–(10.75,-5.3);
[thin] (7,-7.3)–(9,-5.3);
[thin] (7,-7.3)–(7.25,-5.3);
[thin] (7,-7.3)–(5.5,-5.3);
[thin] (7,-7.3)–(3.75,-5.3);
[thin] (7,-7.3)–(2,-5.3);
[thin] (7,-7.3)–(0.25,-5.3);

[thick] (20,-8)–(22,-8);
[thick] (21,-8)–(21,-6);
[thick] (22,-8)–(22,-6);
[thick] (20,-8)–(20,-6);
[thick] (20,-6)–(22,-6);
[thick] (20,-7)–(22,-7);

[fill=black] (20,-8) rectangle (21,-6);

[thick] (23,-8)–(25,-8);
[thick] (24,-8)–(24,-6);
[thick] (25,-8)–(25,-6);
[thick] (23,-8)–(23,-6);
[thick] (23,-6)–(25,-6);
[thick] (23,-7)–(25,-7);

[fill=black] (24,-8) rectangle (25,-6);

[thick] (25.5,-8.5)–(25.5,-5.5);

[thick] (26,-8)–(28,-8);
[thick] (27,-8)–(27,-6);
[thick] (28,-8)–(28,-6);
[thick] (26,-8)–(26,-6);
[thick] (26,-6)–(28,-6);
[thick] (26,-7)–(28,-7);

[fill=black] (26,-7) rectangle (27,-6);
[fill=black] (27,-8) rectangle (28,-7);

[thick] (29,-8)–(31,-8);
[thick] (30,-8)–(30,-6);
[thick] (31,-8)–(31,-6);
[thick] (29,-8)–(29,-6);
[thick] (29,-6)–(31,-6);
[thick] (29,-7)–(31,-7);

[fill=black] (30,-7) rectangle (31,-6);

[thick] (32,-8)–(34,-8);
[thick] (33,-8)–(33,-6);
[thick] (34,-8)–(34,-6);
[thick] (32,-8)–(32,-6);
[thick] (32,-6)–(34,-6);
[thick] (32,-7)–(34,-7);

[fill=black] (33,-8) rectangle (34,-7);

[thick] (19.75,-2)–(20.75,-2);
[thick] (19.75,-1)–(20.75,-1);
[thick] (19.75,-2)–(19.75,-1);
[thick] (20.75,-2)–(20.75,-1);

[fill=black] (19.5,-2.25) rectangle (20,-1.75);

[thick] (21.5,-2)–(22.5,-2);
[thick] (21.5,-1)–(22.5,-1);
[thick] (21.5,-2)–(21.5,-1);
[thick] (22.5,-2)–(22.5,-1);

[fill=black] (21.25,-1.25) rectangle (21.75,-0.75);

[thick] (23.25,-2)–(24.25,-2);
[thick] (23.25,-1)–(24.25,-1);
[thick] (23.25,-2)–(23.25,-1);
[thick] (24.25,-2)–(24.25,-1);

[fill=black] (24,-1.25) rectangle (24.5,-0.75);

[thick] (25,-2)–(26,-2);
[thick] (25,-1)–(26,-1);
[thick] (25,-2)–(25,-1);
[thick] (26,-2)–(26,-1);

[fill=black] (25.75,-2.25) rectangle (26.25,-1.75);

[thick] (26.75,-2)–(27.75,-2);
[thick] (26.75,-1)–(27.75,-1);
[thick] (26.75,-2)–(26.75,-1);
[thick] (27.75,-2)–(27.75,-1);

[fill=white] (26.5,-2.25) rectangle (27,-1.75);

[thick] (28.50,-2)–(29.5,-2);
[thick] (28.50,-1)–(29.5,-1);
[thick] (28.50,-2)–(28.5,-1);
[thick] (29.50,-2)–(29.50,-1);

[fill=white] (28.25,-1.25) rectangle (28.75,-0.75);

[thick] (30.25,-2)–(31.25,-2);
[thick] (30.25,-1)–(31.25,-1);
[thick] (30.25,-2)–(30.25,-1);
[thick] (31.25,-2)–(31.25,-1);

[fill=white] (31,-1.25) rectangle (31.5,-0.75);

[thick] (32,-2)–(33,-2);
[thick] (32,-1)–(33,-1);
[thick] (32,-2)–(32,-1);
[thick] (33,-2)–(33,-1);

[fill=white] (32.75,-2.25) rectangle (33.25,-1.75);

[thin] (21,-5.7)–(20.25,-2.3);
[thin] (21,-5.7)–(22,-2.3);
[thin] (21,-5.7)–(30.75,-2.3);
[thin] (21,-5.7)–(32.5,-2.3);

[thin] (24,-5.7)–(23.75,-2.3);
[thin] (24,-5.7)–(25.5,-2.3);
[thin] (24,-5.7)–(27.25,-2.3);
[thin] (24,-5.7)–(29,-2.3);

[thin] (27,-5.7)–(22,-2.3);
[thin] (27,-5.7)–(25.5,-2.3);
[thin] (27,-5.7)–(27.25,-2.3);
[thin] (27,-5.7)–(30.75,-2.3);

[thin] (30,-5.7)–(23.75,-2.3);
[thin] (30,-5.7)–(27.25,-2.3);
[thin] (30,-5.7)–(29,-2.3);
[thin] (30,-5.7)–(32.5,-2.3);

[thin] (33,-5.7)–(25.5,-2.3);
[thin] (33,-5.7)–(27.25,-2.3);
[thin] (33,-5.7)–(29,-2.3);
[thin] (33,-5.7)–(30.75,-2.3);

[text width=0.1cm] at (16.7,-1.5)

[text width=0.1cm] at (21,-11.5)

[text width=0.1cm] at (26.6,2)

[text width=0.1cm] at (27,-11.5)

[text width=0.1cm] at (30,-11.5)

[text width=0.1cm] at (33,-11.5)

[thin] (21,-10.9)–(21,-8.3);
[thin] (21,-10.9)–(33,-8.3);
[thin] (21,-10.9)–(24,-8.3);
[thin] (21,-10.9)–(27,-8.3);
[thin] (21,-10.9)–(30,-8.3);

[thin] (21,-5.7)–(17.2,-2.3);
[thin] (24,-5.7)–(17.2,-2.3);

[thin] (27,-10.9)–(27,-8.3);
[thin] (30,-10.9)–(30,-8.3);
[thin] (33,-10.9)–(33,-8.3);

[thin] (27,1.1)–(17.2,-0.7);
[thin] (27,1.1)–(32.5,-0.7);
[thin] (27,1.1)–(30.75,-0.7);
[thin] (27,1.1)–(29,-0.7);
[thin] (27,1.1)–(27.25,-0.7);
[thin] (27,1.1)–(25.5,-0.7);
[thin] (27,1.1)–(23.75,-0.7);
[thin] (27,1.1)–(22,-0.7);
[thin] (27,1.1)–(20.25,-0.7);

We are now going to apply Algorithms <ref> and <ref> in Appendix <ref> to enforce the trace constraints. We start with the negative trace constraints, Algorithm <ref>. The trace for the negative training examples is $\textbf{Tr} (T_{i}^{-})={\bf{GL}^{a}}([0])=\{0^{*},\zeta_1, \zeta_2, \zeta_3\}$, and for constant $v$ is also $\textbf{Tr} (v)={\bf{GL}^{a}}([0])=\{0^{*},\zeta_1, \zeta_2, \zeta_3\}$. Now it is not obeyed that ${\bf{Tr}}(T_{i}^{-}) \not\subset {\bf{Tr}}(v)$ so we need to enforce it. For this we need to choose a constant $c \in M$ equal to $v$ or such that $[c]$ receives edges from $[v]$ and not from $[T_{i}^{-}]$. We then need to add an atom $\phi \rightarrow c$. The condition is fulfilled directly by $v$ so we add $\phi \rightarrow v$, and the corresponding dual-of-atom $[v] \rightarrow [\phi]$ in $M^{*}$.

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[thick] (3,0)–(5,0);
[thick] (4,0)–(4,2);
[thick] (5,0)–(5,2);
[thick] (3,0)–(3,2);
[thick] (3,2)–(5,2);
[thick] (3,1)–(5,1);

[fill=black] (4,0) rectangle (5,2);

[thick] (5.5,-0.5)–(5.5,2.5);

[thick] (6,0)–(8,0);
[thick] (6,0)–(6,2);
[thick] (8,0)–(8,2);
[thick] (6,1)–(8,1);
[thick] (6,2)–(8,2);
[thick] (7,0)–(7,2);

[fill=black] (6,1) rectangle (7,2);
[fill=black] (7,0) rectangle (8,1);

[thick] (9,0)–(11,0);
[thick] (10,0)–(10,2);
[thick] (11,0)–(11,2);
[thick] (9,0)–(9,2);
[thick] (9,2)–(11,2);
[thick] (9,1)–(11,1);

[fill=black] (10,1) rectangle (11,2);

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-0.3)–(0.25,-3.7);
[thin] (1,-0.3)–(2,-3.7);
[thin] (1,-0.3)–(10.75,-3.7);
[thin] (1,-0.3)–(12.5,-3.7);

[thin] (4,-0.3)–(5.5,-3.7);
[thin] (4,-0.3)–(3.75,-3.7);
[thin] (4,-0.3)–(7.25,-3.7);
[thin] (4,-0.3)–(9,-3.7);

[thin] (7,-0.3)–(2,-3.7);
[thin] (7,-0.3)–(5.5,-3.7);
[thin] (7,-0.3)–(7.25,-3.7);
[thin] (7,-0.3)–(10.75,-3.7);

[thin] (10,-0.3)–(3.75,-3.7);
[thin] (10,-0.3)–(7.25,-3.7);
[thin] (10,-0.3)–(9,-3.7);
[thin] (10,-0.3)–(12.5,-3.7);

[thin] (13,-0.3)–(5.5,-3.7);
[thin] (13,-0.3)–(7.25,-3.7);
[thin] (13,-0.3)–(9,-3.7);
[thin] (13,-0.3)–(10.75,-3.7);

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (6.7,-7.9)

[text width=0.1cm] at (-3,-8)

[thin] (-3,-5.3)–(-3,-7.6);

[thin] (7,-7.3)–(-3,-5.3);

[thin] (7,-7.3)–(12.5,-5.3);
[thin] (7,-7.3)–(10.75,-5.3);
[thin] (7,-7.3)–(9,-5.3);
[thin] (7,-7.3)–(7.25,-5.3);
[thin] (7,-7.3)–(5.5,-5.3);
[thin] (7,-7.3)–(3.75,-5.3);
[thin] (7,-7.3)–(2,-5.3);
[thin] (7,-7.3)–(0.25,-5.3);

[thick] (20,-8)–(22,-8);
[thick] (21,-8)–(21,-6);
[thick] (22,-8)–(22,-6);
[thick] (20,-8)–(20,-6);
[thick] (20,-6)–(22,-6);
[thick] (20,-7)–(22,-7);

[fill=black] (20,-8) rectangle (21,-6);

[thick] (23,-8)–(25,-8);
[thick] (24,-8)–(24,-6);
[thick] (25,-8)–(25,-6);
[thick] (23,-8)–(23,-6);
[thick] (23,-6)–(25,-6);
[thick] (23,-7)–(25,-7);

[fill=black] (24,-8) rectangle (25,-6);

[thick] (25.5,-8.5)–(25.5,-5.5);

[thick] (26,-8)–(28,-8);
[thick] (27,-8)–(27,-6);
[thick] (28,-8)–(28,-6);
[thick] (26,-8)–(26,-6);
[thick] (26,-6)–(28,-6);
[thick] (26,-7)–(28,-7);

[fill=black] (26,-7) rectangle (27,-6);
[fill=black] (27,-8) rectangle (28,-7);

[thick] (29,-8)–(31,-8);
[thick] (30,-8)–(30,-6);
[thick] (31,-8)–(31,-6);
[thick] (29,-8)–(29,-6);
[thick] (29,-6)–(31,-6);
[thick] (29,-7)–(31,-7);

[fill=black] (30,-7) rectangle (31,-6);

[thick] (32,-8)–(34,-8);
[thick] (33,-8)–(33,-6);
[thick] (34,-8)–(34,-6);
[thick] (32,-8)–(32,-6);
[thick] (32,-6)–(34,-6);
[thick] (32,-7)–(34,-7);

[fill=black] (33,-8) rectangle (34,-7);

[thick] (19.75,-2)–(20.75,-2);
[thick] (19.75,-1)–(20.75,-1);
[thick] (19.75,-2)–(19.75,-1);
[thick] (20.75,-2)–(20.75,-1);

[fill=black] (19.5,-2.25) rectangle (20,-1.75);

[thick] (21.5,-2)–(22.5,-2);
[thick] (21.5,-1)–(22.5,-1);
[thick] (21.5,-2)–(21.5,-1);
[thick] (22.5,-2)–(22.5,-1);

[fill=black] (21.25,-1.25) rectangle (21.75,-0.75);

[thick] (23.25,-2)–(24.25,-2);
[thick] (23.25,-1)–(24.25,-1);
[thick] (23.25,-2)–(23.25,-1);
[thick] (24.25,-2)–(24.25,-1);

[fill=black] (24,-1.25) rectangle (24.5,-0.75);

[thick] (25,-2)–(26,-2);
[thick] (25,-1)–(26,-1);
[thick] (25,-2)–(25,-1);
[thick] (26,-2)–(26,-1);

[fill=black] (25.75,-2.25) rectangle (26.25,-1.75);

[thick] (26.75,-2)–(27.75,-2);
[thick] (26.75,-1)–(27.75,-1);
[thick] (26.75,-2)–(26.75,-1);
[thick] (27.75,-2)–(27.75,-1);

[fill=white] (26.5,-2.25) rectangle (27,-1.75);

[thick] (28.50,-2)–(29.5,-2);
[thick] (28.50,-1)–(29.5,-1);
[thick] (28.50,-2)–(28.5,-1);
[thick] (29.50,-2)–(29.50,-1);

[fill=white] (28.25,-1.25) rectangle (28.75,-0.75);

[thick] (30.25,-2)–(31.25,-2);
[thick] (30.25,-1)–(31.25,-1);
[thick] (30.25,-2)–(30.25,-1);
[thick] (31.25,-2)–(31.25,-1);

[fill=white] (31,-1.25) rectangle (31.5,-0.75);

[thick] (32,-2)–(33,-2);
[thick] (32,-1)–(33,-1);
[thick] (32,-2)–(32,-1);
[thick] (33,-2)–(33,-1);

[fill=white] (32.75,-2.25) rectangle (33.25,-1.75);

[thin] (21,-5.7)–(20.25,-2.3);
[thin] (21,-5.7)–(22,-2.3);
[thin] (21,-5.7)–(30.75,-2.3);
[thin] (21,-5.7)–(32.5,-2.3);

[thin] (24,-5.7)–(23.75,-2.3);
[thin] (24,-5.7)–(25.5,-2.3);
[thin] (24,-5.7)–(27.25,-2.3);
[thin] (24,-5.7)–(29,-2.3);

[thin] (27,-5.7)–(22,-2.3);
[thin] (27,-5.7)–(25.5,-2.3);
[thin] (27,-5.7)–(27.25,-2.3);
[thin] (27,-5.7)–(30.75,-2.3);

[thin] (30,-5.7)–(23.75,-2.3);
[thin] (30,-5.7)–(27.25,-2.3);
[thin] (30,-5.7)–(29,-2.3);
[thin] (30,-5.7)–(32.5,-2.3);

[thin] (33,-5.7)–(25.5,-2.3);
[thin] (33,-5.7)–(27.25,-2.3);
[thin] (33,-5.7)–(29,-2.3);
[thin] (33,-5.7)–(30.75,-2.3);

[text width=0.1cm] at (16.7,2)

[text width=0.1cm] at (16.7,-1.5)

[text width=0.1cm] at (21,-11.5)

[text width=0.1cm] at (26.6,2)

[text width=0.1cm] at (27,-11.5)

[text width=0.1cm] at (30,-11.5)

[text width=0.1cm] at (33,-11.5)

[thin] (17.2,1.3)–(17.2,-0.7);

[thin] (21,-10.9)–(21,-8.3);
[thin] (21,-10.9)–(33,-8.3);
[thin] (21,-10.9)–(24,-8.3);
[thin] (21,-10.9)–(27,-8.3);
[thin] (21,-10.9)–(30,-8.3);

[thin] (21,-5.7)–(17.2,-2.3);
[thin] (24,-5.7)–(17.2,-2.3);

[thin] (27,-10.9)–(27,-8.3);
[thin] (30,-10.9)–(30,-8.3);
[thin] (33,-10.9)–(33,-8.3);

[thin] (27,1.1)–(17.2,-0.7);
[thin] (27,1.1)–(32.5,-0.7);
[thin] (27,1.1)–(30.75,-0.7);
[thin] (27,1.1)–(29,-0.7);
[thin] (27,1.1)–(27.25,-0.7);
[thin] (27,1.1)–(25.5,-0.7);
[thin] (27,1.1)–(23.75,-0.7);
[thin] (27,1.1)–(22,-0.7);
[thin] (27,1.1)–(20.25,-0.7);

We now re-check the traces, $\textbf{Tr}(T_{i}^{-})=\textbf{Tr}(0)=\{0^{*},\zeta_1, \zeta_2, \zeta_3\}$ and
$\textbf{Tr}(v)=\textbf{Tr}(0) \cap \textbf{Tr} (\phi)=\{0^{*}\}$, thus obeying
$\textbf{Tr}(T_{i}^{-}) \not\subset \textbf{Tr}(v)$, as required.

Now, for positive trace constraints, we apply Algorithm <ref>. For the positive relations $v<T_{i}^{+}$, we need to enforce $\textbf{Tr}(T_{i}^{+}) \subset \textbf{Tr}(v)$. First we check the values of the traces,
$\textbf{Tr}(T_{i}^{+})=\textbf{Tr}(0)=\{0^{*},\zeta_1, \zeta_2, \zeta_3\}$, and $\textbf{Tr}(v)=\textbf{Tr}(0)\cap \textbf{Tr}(\phi)=\textbf{Tr}(\phi)=\{0^{*}\}$. This means that $\textbf{Tr}(T_{i}^{+}) \not \subset \textbf{Tr}(v)$, so we need to enforce the trace constraint. We add atoms $\epsilon_i$ to the constants $c_i$ until $\textbf{Tr}(T_{i}^{+})=\textbf{Tr}(0)\cap_i \textbf{Tr}(\epsilon_i)$ equals $\textbf{Tr}(v)$. For the first term $T_1^{+}$ we just need to edge one atom to the first constant, $\epsilon_1 \rightarrow c_1$, so $\textbf{Tr}(T_{1}^{+})=\textbf{Tr}(0) \cap \textbf{Tr}(\epsilon_1)=\{0^{*}, \zeta_1,\zeta_2,\zeta_3\} \cap \{0^{*}\}=\{0^{*}\}$. For the second training example, $T_2^{+}$, we need to add one atom for each of its constants, $\epsilon_2 \rightarrow c_3$ and $\epsilon_3 \rightarrow c_4$. Doing this, we have
$\textbf{Tr}(T_{2}^{+})=\textbf{Tr}(0) \cap \textbf{Tr}(\epsilon_2) \cap \textbf{Tr}(\epsilon_3)=\{0^{*},\zeta_1,\zeta_2,\zeta_3\} \cap \{0^{*},\zeta_2\} \cap \{0^{*},\zeta_1,\zeta_3\}=\{0^{*}\}$, as required.

After imposing the trace constraints the graphs look like this

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[thick] (3,0)–(5,0);
[thick] (4,0)–(4,2);
[thick] (5,0)–(5,2);
[thick] (3,0)–(3,2);
[thick] (3,2)–(5,2);
[thick] (3,1)–(5,1);

[fill=black] (4,0) rectangle (5,2);

[thick] (5.5,-0.5)–(5.5,2.5);

[thick] (6,0)–(8,0);
[thick] (6,0)–(6,2);
[thick] (8,0)–(8,2);
[thick] (6,1)–(8,1);
[thick] (6,2)–(8,2);
[thick] (7,0)–(7,2);

[fill=black] (6,1) rectangle (7,2);
[fill=black] (7,0) rectangle (8,1);

[thick] (9,0)–(11,0);
[thick] (10,0)–(10,2);
[thick] (11,0)–(11,2);
[thick] (9,0)–(9,2);
[thick] (9,2)–(11,2);
[thick] (9,1)–(11,1);

[fill=black] (10,1) rectangle (11,2);

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-0.3)–(0.25,-3.7);
[thin] (1,-0.3)–(2,-3.7);
[thin] (1,-0.3)–(10.75,-3.7);
[thin] (1,-0.3)–(12.5,-3.7);

[thin] (4,-0.3)–(5.5,-3.7);
[thin] (4,-0.3)–(3.75,-3.7);
[thin] (4,-0.3)–(7.25,-3.7);
[thin] (4,-0.3)–(9,-3.7);

[thin] (7,-0.3)–(2,-3.7);
[thin] (7,-0.3)–(5.5,-3.7);
[thin] (7,-0.3)–(7.25,-3.7);
[thin] (7,-0.3)–(10.75,-3.7);

[thin] (10,-0.3)–(3.75,-3.7);
[thin] (10,-0.3)–(7.25,-3.7);
[thin] (10,-0.3)–(9,-3.7);
[thin] (10,-0.3)–(12.5,-3.7);

[thin] (13,-0.3)–(5.5,-3.7);
[thin] (13,-0.3)–(7.25,-3.7);
[thin] (13,-0.3)–(9,-3.7);
[thin] (13,-0.3)–(10.75,-3.7);

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (7,-7.9)

[text width=0.1cm] at (-3,-8)

[text width=0.1cm] at (0.25,-8)

[text width=0.1cm] at (3.75,-8)

[text width=0.1cm] at (5.5,-8)

[thin] (-3,-5.3)–(-3,-7.6);

[thin] (0.25,-5.3)–(0.25,-7.6);

[thin] (3.75,-5.3)–(3.75,-7.6);

[thin] (5.5,-5.3)–(5.5,-7.6);

[thin] (7,-7.3)–(-3,-5.3);

[thin] (7,-7.3)–(12.5,-5.3);
[thin] (7,-7.3)–(10.75,-5.3);
[thin] (7,-7.3)–(9,-5.3);
[thin] (7,-7.3)–(7.25,-5.3);
[thin] (7,-7.3)–(5.5,-5.3);
[thin] (7,-7.3)–(3.75,-5.3);
[thin] (7,-7.3)–(2,-5.3);
[thin] (7,-7.3)–(0.25,-5.3);

[thick] (20,-8)–(22,-8);
[thick] (21,-8)–(21,-6);
[thick] (22,-8)–(22,-6);
[thick] (20,-8)–(20,-6);
[thick] (20,-6)–(22,-6);
[thick] (20,-7)–(22,-7);

[fill=black] (20,-8) rectangle (21,-6);

[thick] (23,-8)–(25,-8);
[thick] (24,-8)–(24,-6);
[thick] (25,-8)–(25,-6);
[thick] (23,-8)–(23,-6);
[thick] (23,-6)–(25,-6);
[thick] (23,-7)–(25,-7);

[fill=black] (24,-8) rectangle (25,-6);

[thick] (25.5,-8.5)–(25.5,-5.5);

[thick] (26,-8)–(28,-8);
[thick] (27,-8)–(27,-6);
[thick] (28,-8)–(28,-6);
[thick] (26,-8)–(26,-6);
[thick] (26,-6)–(28,-6);
[thick] (26,-7)–(28,-7);

[fill=black] (26,-7) rectangle (27,-6);
[fill=black] (27,-8) rectangle (28,-7);

[thick] (29,-8)–(31,-8);
[thick] (30,-8)–(30,-6);
[thick] (31,-8)–(31,-6);
[thick] (29,-8)–(29,-6);
[thick] (29,-6)–(31,-6);
[thick] (29,-7)–(31,-7);

[fill=black] (30,-7) rectangle (31,-6);

[thick] (32,-8)–(34,-8);
[thick] (33,-8)–(33,-6);
[thick] (34,-8)–(34,-6);
[thick] (32,-8)–(32,-6);
[thick] (32,-6)–(34,-6);
[thick] (32,-7)–(34,-7);

[fill=black] (33,-8) rectangle (34,-7);

[thick] (19.75,-2)–(20.75,-2);
[thick] (19.75,-1)–(20.75,-1);
[thick] (19.75,-2)–(19.75,-1);
[thick] (20.75,-2)–(20.75,-1);

[fill=black] (19.5,-2.25) rectangle (20,-1.75);

[thick] (21.5,-2)–(22.5,-2);
[thick] (21.5,-1)–(22.5,-1);
[thick] (21.5,-2)–(21.5,-1);
[thick] (22.5,-2)–(22.5,-1);

[fill=black] (21.25,-1.25) rectangle (21.75,-0.75);

[thick] (23.25,-2)–(24.25,-2);
[thick] (23.25,-1)–(24.25,-1);
[thick] (23.25,-2)–(23.25,-1);
[thick] (24.25,-2)–(24.25,-1);

[fill=black] (24,-1.25) rectangle (24.5,-0.75);

[thick] (25,-2)–(26,-2);
[thick] (25,-1)–(26,-1);
[thick] (25,-2)–(25,-1);
[thick] (26,-2)–(26,-1);

[fill=black] (25.75,-2.25) rectangle (26.25,-1.75);

[thick] (26.75,-2)–(27.75,-2);
[thick] (26.75,-1)–(27.75,-1);
[thick] (26.75,-2)–(26.75,-1);
[thick] (27.75,-2)–(27.75,-1);

[fill=white] (26.5,-2.25) rectangle (27,-1.75);

[thick] (28.50,-2)–(29.5,-2);
[thick] (28.50,-1)–(29.5,-1);
[thick] (28.50,-2)–(28.5,-1);
[thick] (29.50,-2)–(29.50,-1);

[fill=white] (28.25,-1.25) rectangle (28.75,-0.75);

[thick] (30.25,-2)–(31.25,-2);
[thick] (30.25,-1)–(31.25,-1);
[thick] (30.25,-2)–(30.25,-1);
[thick] (31.25,-2)–(31.25,-1);

[fill=white] (31,-1.25) rectangle (31.5,-0.75);

[thick] (32,-2)–(33,-2);
[thick] (32,-1)–(33,-1);
[thick] (32,-2)–(32,-1);
[thick] (33,-2)–(33,-1);

[fill=white] (32.75,-2.25) rectangle (33.25,-1.75);

[thin] (21,-5.7)–(20.25,-2.3);
[thin] (21,-5.7)–(22,-2.3);
[thin] (21,-5.7)–(30.75,-2.3);
[thin] (21,-5.7)–(32.5,-2.3);

[thin] (24,-5.7)–(23.75,-2.3);
[thin] (24,-5.7)–(25.5,-2.3);
[thin] (24,-5.7)–(27.25,-2.3);
[thin] (24,-5.7)–(29,-2.3);

[thin] (27,-5.7)–(22,-2.3);
[thin] (27,-5.7)–(25.5,-2.3);
[thin] (27,-5.7)–(27.25,-2.3);
[thin] (27,-5.7)–(30.75,-2.3);

[thin] (30,-5.7)–(23.75,-2.3);
[thin] (30,-5.7)–(27.25,-2.3);
[thin] (30,-5.7)–(29,-2.3);
[thin] (30,-5.7)–(32.5,-2.3);

[thin] (33,-5.7)–(25.5,-2.3);
[thin] (33,-5.7)–(27.25,-2.3);
[thin] (33,-5.7)–(29,-2.3);
[thin] (33,-5.7)–(30.75,-2.3);

[text width=0.1cm] at (16.7,2)

[text width=0.1cm] at (19.60,2)

[text width=0.1cm] at (23.1,2)

[text width=0.1cm] at (24.85,2)

[text width=0.1cm] at (16.7,-1.5)

[text width=0.1cm] at (21,-11.5)

[text width=0.1cm] at (26.6,2)

[text width=0.1cm] at (27,-11.5)

[text width=0.1cm] at (30,-11.5)

[text width=0.1cm] at (33,-11.5)

[thin] (17.2,1.3)–(17.2,-0.7);

[thin] (20.25,1.3)–(20.25,-0.7);
[thin] (23.75,1.3)–(23.75,-0.7);
[thin] (25.5,1.3)–(25.5,-0.7);

[thin] (21,-10.9)–(21,-8.3);
[thin] (21,-10.9)–(33,-8.3);
[thin] (21,-10.9)–(24,-8.3);
[thin] (21,-10.9)–(27,-8.3);
[thin] (21,-10.9)–(30,-8.3);

[thin] (21,-5.7)–(17.2,-2.3);
[thin] (24,-5.7)–(17.2,-2.3);

[thin] (27,-10.9)–(27,-8.3);
[thin] (30,-10.9)–(30,-8.3);
[thin] (33,-10.9)–(33,-8.3);

[thin] (27,1.1)–(17.2,-0.7);
[thin] (27,1.1)–(32.5,-0.7);
[thin] (27,1.1)–(30.75,-0.7);
[thin] (27,1.1)–(29,-0.7);
[thin] (27,1.1)–(27.25,-0.7);
[thin] (27,1.1)–(25.5,-0.7);
[thin] (27,1.1)–(23.75,-0.7);
[thin] (27,1.1)–(22,-0.7);
[thin] (27,1.1)–(20.25,-0.7);

We have used our toy example to show how to enforce the trace constraints of Algorithms <ref> and <ref>, detailed in Appendix <ref>. The general trace enforcing algorithm consists of repeatedly enforcing negative trace constraints and positive trace constraints until all constraints are satisfied, which usually occurs within a few iterations. The trace enforcing process always ends unless the embedding is inconsistent (see Theorem <ref>).  The number of times these algorithms loop within the do-while statements can be easily bounded by the cardinality of the sets involved and is no worse than linear with the size of the model.

§.§ Full and Sparse Crossing operations

After enforcing the trace constraints, all negative relations $v \not < T_{i}^{-}$ are already satisfied in $M$. This will always be the case. To build an atomized model that also satisfies the positive relations $v < T_{i}^{+}$, we use the Sparse Crossing operation. This trace-invariant operation replaces the atoms of $v$ for others that are also in $T_i^+$ without interfering with previously enforced positive or negative relations and without changing the traces of any element of $M$.

The Sparse Crossing can be seen as an sparse version of the Full Crossing that is also a trace-invariant operation. Both operations are similar and can be represented with a two dimensional matrix as follows. Consider two elements $a$ and $b$ with atoms

\begin{align}
{\bf{GL}}^a (a) = \{ \alpha ,\beta, \chi \} \,\,\,\,\,\,\,\,\,\,\textnormal{and}\,\,\,\,\,\,\,\,\,\, {\bf{GL}}^a (b) = \{ \chi ,\delta ,\varepsilon \},
\end{align}

and suppose we want to enforce $a<b$. Extend the graph appending new atoms and edges as

\[
\begin{array}{*{20}c}
{\phi ,\varphi ,\gamma \to \alpha } \\
{\pi ,\omega ,\theta \to \beta } \\
\end{array}\,\,\,\,\,\,\,\,\,\,\begin{array}{*{20}c}
{\chi ',\phi ,\pi \to \chi } \\
{\delta ',\varphi ,\omega \to \delta } \\
{\varepsilon ',\gamma ,\theta \to \varepsilon } \\
\end{array}
\]

Close the graph by transitive closure and delete $\alpha ,\beta ,\,\chi ,\,\delta$ and $\varepsilon$ from the graph. Then it holds that ${\bf{GL}}^a (a) \subset {\bf{GL}}^a (b)$ and therefore, $\,a<b$. This is the Full Crossing of $a$ into $b$ and can be represented with the table

\[
\begin{array}{*{20}c}
{} & \chi & \delta & \varepsilon \\
\hline
\,\,\,\,\,\,\,\,\vline & \chi ' & \delta ' & \varepsilon ' \\
\alpha \,\,\,\,\vline & \phi & \varphi & \gamma \\
\beta \,\,\,\, \vline & \pi & \omega & \theta \\
\end{array}
\]

We say that we have "crossed" atoms $\alpha$ and $\beta$ into $b$. Note that we do not need to "cross" atom $\chi$ of $a$ as it is already in $b$.

Since the crossing is an expensive operation that multiplies the number of atoms, we instead do a Sparse Crossing. The idea is that, as long as we check that all involved atoms remain trace-invariant, the Sparse Crossing operation still enforces $a<b$ and preserves all positive relations. In addition, it also preserves negative relations as long as they are "protected" by its corresponding negative trace constraint. Later we give details of how to compute it, but is is intuitive to think of it as a Full Crossing but leaving empty spaces in the table, as in this example

\[
\begin{array}{*{20}c}
{} & \varepsilon_1 & \varepsilon_2 & \varepsilon_3 \\
\hline
\,\,\,\,\,\,\,\,\,\,\vline & \varepsilon_{1}' & \,\,\,\, & \varepsilon_{3}' \\
\phi _1 \,\,\,\,\vline & & \varphi_{12} & \\
\phi _2 \,\,\,\,\vline & & \varphi_{22} & \varphi_{23} \\
\end{array}
\]

The Full Crossing and Sparse Crossing operations transform one graph into another graph and, after transitive closure, the crossing operations also map one algebra into another. This mapping function commutes with both operations $\odot$ and $[\,\,\,]$ so it is an homomorphism. This means that if $q=r \odot s$ is true before crossing it is also true after. Since the partial order $<$ is defined using the idempotent operator $\odot$, crossing operations preserve all inclusions between elements.

Full and Sparse Crossing operations keep unaltered all positive order relations, i.e. if $p<q$ is true before the crossing of $a$ into $b$, it is also true after. This applies to all positive relations, not only the positive training relations of $R^{+}$ (we use $R^{+}$ for the positive relations of $R$). Crossing, however, does not preserve negative order relations: a negative relation before crossing can turn positive after crossing. In fact, crossing is never an injective homomorphism because $a<b$, that is false before crossing, becomes true after the crossing.

It turns out that the enforcement of negative trace constraints and the positive trace constraint $ {\bf{Tr}}(b) \subset {\bf{Tr}}(a)$ is what is need to ensure that the crossing of $a$ into $b$ preserves the negative order relations $R^{-}$.  In addition, the atoms introduced during the trace constraint enforcement stage are precisely the ones we need to carry out the Full Crossing (or Sparse Crossing) operation and keep all atoms trace-invariant. This follows from Theorem <ref> that states that the Full Crossing of $a$ into $b$ leaves the traces of all atoms unchanged if and only if the positive trace constraint for $a < b$, i.e. $ {\bf{Tr}}(b) \subset {\bf{Tr}}(a)$ is satisfied.

For a recipe on how to compute the Sparse Crossing, see the Algorithm <ref> in Appendix <ref>. In the following, we apply it to our toy example to the two positive input relations.

The Sparse Crossing operation of $v$ into $T_i^+$ works by creating new atoms and linking them to atoms in $v$ and atoms in $T_i^+$ in a way that the traces of all atoms are kept unaltered. The linearity of the trace ensures that if the trace of the atoms remain unchanged so do the traces of all elements.

After we edge new atoms, say $\phi_1$, $\phi_2$ and $\phi_3$, to an existing atom $\phi$ of $v$, the trace of $\phi$ should be recalculated using $\textbf{Tr}(\phi)=\textbf{Tr}(\phi_1) \cap \textbf{Tr}(\phi_2) \cap \textbf{Tr}(\phi_3)$. Since the new atoms we introduce during the Crossing operations are edged not only to $\phi$ but also to atoms of $T_i^+$, the trace of $\phi$ could change and we do not want that to happen. Before we get rid of atom $\phi$ and replace it with the new ones, we have to make sure that the trace $\textbf{Tr}(\phi)$ has not changed.

We want the Sparse Crossing to be as sparse as possible to produce a model as small as possible. We replace $\phi$ with as few new atoms as possible limited only by the need to keep $\textbf{Tr}(\phi)$ unchanged. This need may force us to introduce more than one new atom in the row of atom $\phi$ in the Sparse Crossing matrix. It is always possible to preserve $\textbf{Tr}(\phi)$ provided that we have enforced the positive trace constraint for $a < b$, i.e. $ {\bf{Tr}}(b) \subset {\bf{Tr}}(a)$.

Keeping the trace of the atoms of $T_i^+$ unaltered is also necessary but it is easier than preserving the trace of $\phi$. Suppose an atom $\alpha < T_1^+$ and assume we add an edge $\phi_1 \rightarrow \alpha$. The trace of $\alpha$ may change but, if it does, now we have the extra freedom of appending another new atom edged just to $\alpha$, which always has the effect to leave the trace of $\alpha$ invariant. This freedom does not exist for atoms of $v$, like $\phi$. Keep in mind that the goal of the crossing is replacing the atoms of $v$ with new atoms that are in both $v$ and $T_i^+$. If we add an extra atom $\phi'$ edged only to $\phi$, then $\phi'$ is not in $T_i^+$.

Consider the set of atoms $\Phi_1$ in $v$ and not in the first positive example, $T_{1}^{+}$, and choose one. At the point where we are in our toy example, there is only a single atom, $\phi \in \Phi_1$. Now we select one of the atoms in $T_{1}^{+}$, in this case only $\epsilon_1$. We create a new atom $\phi_{1}$, and we add an edge to $\phi$ and another to $\epsilon_1$, $\phi_{1} \rightarrow \phi$ and $\phi_{1} \rightarrow \epsilon_1$, obtaining the new graph

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[thick] (3,0)–(5,0);
[thick] (4,0)–(4,2);
[thick] (5,0)–(5,2);
[thick] (3,0)–(3,2);
[thick] (3,2)–(5,2);
[thick] (3,1)–(5,1);

[fill=black] (4,0) rectangle (5,2);

[thick] (5.5,-0.5)–(5.5,2.5);

[thick] (6,0)–(8,0);
[thick] (6,0)–(6,2);
[thick] (8,0)–(8,2);
[thick] (6,1)–(8,1);
[thick] (6,2)–(8,2);
[thick] (7,0)–(7,2);

[fill=black] (6,1) rectangle (7,2);
[fill=black] (7,0) rectangle (8,1);

[thick] (9,0)–(11,0);
[thick] (10,0)–(10,2);
[thick] (11,0)–(11,2);
[thick] (9,0)–(9,2);
[thick] (9,2)–(11,2);
[thick] (9,1)–(11,1);

[fill=black] (10,1) rectangle (11,2);

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-0.3)–(0.25,-3.7);
[thin] (1,-0.3)–(2,-3.7);
[thin] (1,-0.3)–(10.75,-3.7);
[thin] (1,-0.3)–(12.5,-3.7);

[thin] (4,-0.3)–(5.5,-3.7);
[thin] (4,-0.3)–(3.75,-3.7);
[thin] (4,-0.3)–(7.25,-3.7);
[thin] (4,-0.3)–(9,-3.7);

[thin] (7,-0.3)–(2,-3.7);
[thin] (7,-0.3)–(5.5,-3.7);
[thin] (7,-0.3)–(7.25,-3.7);
[thin] (7,-0.3)–(10.75,-3.7);

[thin] (10,-0.3)–(3.75,-3.7);
[thin] (10,-0.3)–(7.25,-3.7);
[thin] (10,-0.3)–(9,-3.7);
[thin] (10,-0.3)–(12.5,-3.7);

[thin] (13,-0.3)–(5.5,-3.7);
[thin] (13,-0.3)–(7.25,-3.7);
[thin] (13,-0.3)–(9,-3.7);
[thin] (13,-0.3)–(10.75,-3.7);

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (7,-7.9)

[text width=0.1cm] at (-3,-8)

[text width=0.1cm] at (0.25,-8)

[text width=0.1cm] at (3.75,-8)

[text width=0.1cm] at (5.5,-8)
[text width=0.1cm] at (-1.875,-10)

[thin] (-3,-5.3)–(-3,-7.6);

[thin] (-1.5,-9.3)–(-3,-8.7);
[thin] (-1.5,-9.3)–(0.25,-8.7);

[thin] (0.25,-5.3)–(0.25,-7.6);

[thin] (3.75,-5.3)–(3.75,-7.6);

[thin] (5.5,-5.3)–(5.5,-7.6);

[thin] (7,-7.3)–(-3,-5.3);

[thin] (7,-7.3)–(12.5,-5.3);
[thin] (7,-7.3)–(10.75,-5.3);
[thin] (7,-7.3)–(9,-5.3);
[thin] (7,-7.3)–(7.25,-5.3);
[thin] (7,-7.3)–(5.5,-5.3);
[thin] (7,-7.3)–(3.75,-5.3);
[thin] (7,-7.3)–(2,-5.3);
[thin] (7,-7.3)–(0.25,-5.3);

[thick] (20,-8)–(22,-8);
[thick] (21,-8)–(21,-6);
[thick] (22,-8)–(22,-6);
[thick] (20,-8)–(20,-6);
[thick] (20,-6)–(22,-6);
[thick] (20,-7)–(22,-7);

[fill=black] (20,-8) rectangle (21,-6);

[thick] (23,-8)–(25,-8);
[thick] (24,-8)–(24,-6);
[thick] (25,-8)–(25,-6);
[thick] (23,-8)–(23,-6);
[thick] (23,-6)–(25,-6);
[thick] (23,-7)–(25,-7);

[fill=black] (24,-8) rectangle (25,-6);

[thick] (25.5,-8.5)–(25.5,-5.5);

[thick] (26,-8)–(28,-8);
[thick] (27,-8)–(27,-6);
[thick] (28,-8)–(28,-6);
[thick] (26,-8)–(26,-6);
[thick] (26,-6)–(28,-6);
[thick] (26,-7)–(28,-7);

[fill=black] (26,-7) rectangle (27,-6);
[fill=black] (27,-8) rectangle (28,-7);

[thick] (29,-8)–(31,-8);
[thick] (30,-8)–(30,-6);
[thick] (31,-8)–(31,-6);
[thick] (29,-8)–(29,-6);
[thick] (29,-6)–(31,-6);
[thick] (29,-7)–(31,-7);

[fill=black] (30,-7) rectangle (31,-6);

[thick] (32,-8)–(34,-8);
[thick] (33,-8)–(33,-6);
[thick] (34,-8)–(34,-6);
[thick] (32,-8)–(32,-6);
[thick] (32,-6)–(34,-6);
[thick] (32,-7)–(34,-7);

[fill=black] (33,-8) rectangle (34,-7);

[thick] (19.75,-2)–(20.75,-2);
[thick] (19.75,-1)–(20.75,-1);
[thick] (19.75,-2)–(19.75,-1);
[thick] (20.75,-2)–(20.75,-1);

[fill=black] (19.5,-2.25) rectangle (20,-1.75);

[thick] (21.5,-2)–(22.5,-2);
[thick] (21.5,-1)–(22.5,-1);
[thick] (21.5,-2)–(21.5,-1);
[thick] (22.5,-2)–(22.5,-1);

[fill=black] (21.25,-1.25) rectangle (21.75,-0.75);

[thick] (23.25,-2)–(24.25,-2);
[thick] (23.25,-1)–(24.25,-1);
[thick] (23.25,-2)–(23.25,-1);
[thick] (24.25,-2)–(24.25,-1);

[fill=black] (24,-1.25) rectangle (24.5,-0.75);

[thick] (25,-2)–(26,-2);
[thick] (25,-1)–(26,-1);
[thick] (25,-2)–(25,-1);
[thick] (26,-2)–(26,-1);

[fill=black] (25.75,-2.25) rectangle (26.25,-1.75);

[thick] (26.75,-2)–(27.75,-2);
[thick] (26.75,-1)–(27.75,-1);
[thick] (26.75,-2)–(26.75,-1);
[thick] (27.75,-2)–(27.75,-1);

[fill=white] (26.5,-2.25) rectangle (27,-1.75);

[thick] (28.50,-2)–(29.5,-2);
[thick] (28.50,-1)–(29.5,-1);
[thick] (28.50,-2)–(28.5,-1);
[thick] (29.50,-2)–(29.50,-1);

[fill=white] (28.25,-1.25) rectangle (28.75,-0.75);

[thick] (30.25,-2)–(31.25,-2);
[thick] (30.25,-1)–(31.25,-1);
[thick] (30.25,-2)–(30.25,-1);
[thick] (31.25,-2)–(31.25,-1);

[fill=white] (31,-1.25) rectangle (31.5,-0.75);

[thick] (32,-2)–(33,-2);
[thick] (32,-1)–(33,-1);
[thick] (32,-2)–(32,-1);
[thick] (33,-2)–(33,-1);

[fill=white] (32.75,-2.25) rectangle (33.25,-1.75);

[thin] (21,-5.7)–(20.25,-2.3);
[thin] (21,-5.7)–(22,-2.3);
[thin] (21,-5.7)–(30.75,-2.3);
[thin] (21,-5.7)–(32.5,-2.3);

[thin] (24,-5.7)–(23.75,-2.3);
[thin] (24,-5.7)–(25.5,-2.3);
[thin] (24,-5.7)–(27.25,-2.3);
[thin] (24,-5.7)–(29,-2.3);

[thin] (27,-5.7)–(22,-2.3);
[thin] (27,-5.7)–(25.5,-2.3);
[thin] (27,-5.7)–(27.25,-2.3);
[thin] (27,-5.7)–(30.75,-2.3);

[thin] (30,-5.7)–(23.75,-2.3);
[thin] (30,-5.7)–(27.25,-2.3);
[thin] (30,-5.7)–(29,-2.3);
[thin] (30,-5.7)–(32.5,-2.3);

[thin] (33,-5.7)–(25.5,-2.3);
[thin] (33,-5.7)–(27.25,-2.3);
[thin] (33,-5.7)–(29,-2.3);
[thin] (33,-5.7)–(30.75,-2.3);

[text width=0.1cm] at (16.7,2)
[text width=0.1cm] at (17.8,4.1)
[text width=0.1cm] at (19.60,2)
[text width=0.1cm] at (23.1,2)
[text width=0.1cm] at (24.85,2)
[text width=0.1cm] at (16.7,-1.5)

[text width=0.1cm] at (21,-11.5)

[text width=0.1cm] at (26.6,2)

[text width=0.1cm] at (27,-11.5)

[text width=0.1cm] at (30,-11.5)
[text width=0.1cm] at (33,-11.5)

[thin] (17.2,1.3)–(17.2,-0.7);

[thin] (18.5,3.3)–(17.2,2.7);
[thin] (18.5,3.3)–(20,2.7);

[thin] (20.25,1.3)–(20.25,-0.7);
[thin] (23.75,1.3)–(23.75,-0.7);
[thin] (25.5,1.3)–(25.5,-0.7);

[thin] (21,-10.9)–(21,-8.3);
[thin] (21,-10.9)–(33,-8.3);
[thin] (21,-10.9)–(24,-8.3);
[thin] (21,-10.9)–(27,-8.3);
[thin] (21,-10.9)–(30,-8.3);

[thin] (21,-5.7)–(17.2,-2.3);
[thin] (24,-5.7)–(17.2,-2.3);

[thin] (27,-10.9)–(27,-8.3);
[thin] (30,-10.9)–(30,-8.3);
[thin] (33,-10.9)–(33,-8.3);

[thin] (27,1.1)–(17.2,-0.7);
[thin] (27,1.1)–(32.5,-0.7);
[thin] (27,1.1)–(30.75,-0.7);
[thin] (27,1.1)–(29,-0.7);
[thin] (27,1.1)–(27.25,-0.7);
[thin] (27,1.1)–(25.5,-0.7);
[thin] (27,1.1)–(23.75,-0.7);
[thin] (27,1.1)–(22,-0.7);
[thin] (27,1.1)–(20.25,-0.7);

We have to check that the traces of all the atoms remain unchanged. We can start with atom $\phi$. Initially, we have that $\textbf{Tr}(\phi)_{i}= \{0^{*}\}$, and after the crossing $\textbf{Tr}(\phi)_{f}=\textbf{Tr}(\phi_{1})= \{0^{*}\}$, so it has not changed. For atom $\epsilon_1$, we have initially $\textbf{Tr}(\epsilon_1)_{i}=\{0^{*}\}$ and after the crossing $\textbf{Tr}(\epsilon_1)_{f}=\textbf{Tr}(\phi_{1})= \{0^{*}\}$, so it has not changed either. Now that we have checked for trace invariance of the crossing, we can eliminate the original atoms $\phi$ and $\epsilon_1$, giving

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[thick] (3,0)–(5,0);
[thick] (4,0)–(4,2);
[thick] (5,0)–(5,2);
[thick] (3,0)–(3,2);
[thick] (3,2)–(5,2);
[thick] (3,1)–(5,1);

[fill=black] (4,0) rectangle (5,2);

[thick] (5.5,-0.5)–(5.5,2.5);

[thick] (6,0)–(8,0);
[thick] (6,0)–(6,2);
[thick] (8,0)–(8,2);
[thick] (6,1)–(8,1);
[thick] (6,2)–(8,2);
[thick] (7,0)–(7,2);

[fill=black] (6,1) rectangle (7,2);
[fill=black] (7,0) rectangle (8,1);

[thick] (9,0)–(11,0);
[thick] (10,0)–(10,2);
[thick] (11,0)–(11,2);
[thick] (9,0)–(9,2);
[thick] (9,2)–(11,2);
[thick] (9,1)–(11,1);

[fill=black] (10,1) rectangle (11,2);

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-0.3)–(0.25,-3.7);
[thin] (1,-0.3)–(2,-3.7);
[thin] (1,-0.3)–(10.75,-3.7);
[thin] (1,-0.3)–(12.5,-3.7);

[thin] (4,-0.3)–(5.5,-3.7);
[thin] (4,-0.3)–(3.75,-3.7);
[thin] (4,-0.3)–(7.25,-3.7);
[thin] (4,-0.3)–(9,-3.7);

[thin] (7,-0.3)–(2,-3.7);
[thin] (7,-0.3)–(5.5,-3.7);
[thin] (7,-0.3)–(7.25,-3.7);
[thin] (7,-0.3)–(10.75,-3.7);

[thin] (10,-0.3)–(3.75,-3.7);
[thin] (10,-0.3)–(7.25,-3.7);
[thin] (10,-0.3)–(9,-3.7);
[thin] (10,-0.3)–(12.5,-3.7);

[thin] (13,-0.3)–(5.5,-3.7);
[thin] (13,-0.3)–(7.25,-3.7);
[thin] (13,-0.3)–(9,-3.7);
[thin] (13,-0.3)–(10.75,-3.7);

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (7,-7.9)

[text width=0.1cm] at (3.75,-8)

[text width=0.1cm] at (5.5,-8)
[text width=0.1cm] at (-1.8,-8)

[thin] (-1.5,-7.4)–(-3,-5.3);
[thin] (-1.5,-7.4)–(0.25,-5.3);

[thin] (3.75,-5.3)–(3.75,-7.6);

[thin] (5.5,-5.3)–(5.5,-7.6);

[thin] (7,-7.3)–(-3,-5.3);

[thin] (7,-7.3)–(12.5,-5.3);
[thin] (7,-7.3)–(10.75,-5.3);
[thin] (7,-7.3)–(9,-5.3);
[thin] (7,-7.3)–(7.25,-5.3);
[thin] (7,-7.3)–(5.5,-5.3);
[thin] (7,-7.3)–(3.75,-5.3);
[thin] (7,-7.3)–(2,-5.3);
[thin] (7,-7.3)–(0.25,-5.3);

[thick] (20,-8)–(22,-8);
[thick] (21,-8)–(21,-6);
[thick] (22,-8)–(22,-6);
[thick] (20,-8)–(20,-6);
[thick] (20,-6)–(22,-6);
[thick] (20,-7)–(22,-7);

[fill=black] (20,-8) rectangle (21,-6);

[thick] (23,-8)–(25,-8);
[thick] (24,-8)–(24,-6);
[thick] (25,-8)–(25,-6);
[thick] (23,-8)–(23,-6);
[thick] (23,-6)–(25,-6);
[thick] (23,-7)–(25,-7);

[fill=black] (24,-8) rectangle (25,-6);

[thick] (25.5,-8.5)–(25.5,-5.5);

[thick] (26,-8)–(28,-8);
[thick] (27,-8)–(27,-6);
[thick] (28,-8)–(28,-6);
[thick] (26,-8)–(26,-6);
[thick] (26,-6)–(28,-6);
[thick] (26,-7)–(28,-7);

[fill=black] (26,-7) rectangle (27,-6);
[fill=black] (27,-8) rectangle (28,-7);

[thick] (29,-8)–(31,-8);
[thick] (30,-8)–(30,-6);
[thick] (31,-8)–(31,-6);
[thick] (29,-8)–(29,-6);
[thick] (29,-6)–(31,-6);
[thick] (29,-7)–(31,-7);

[fill=black] (30,-7) rectangle (31,-6);

[thick] (32,-8)–(34,-8);
[thick] (33,-8)–(33,-6);
[thick] (34,-8)–(34,-6);
[thick] (32,-8)–(32,-6);
[thick] (32,-6)–(34,-6);
[thick] (32,-7)–(34,-7);

[fill=black] (33,-8) rectangle (34,-7);

[thick] (19.75,-2)–(20.75,-2);
[thick] (19.75,-1)–(20.75,-1);
[thick] (19.75,-2)–(19.75,-1);
[thick] (20.75,-2)–(20.75,-1);

[fill=black] (19.5,-2.25) rectangle (20,-1.75);

[thick] (21.5,-2)–(22.5,-2);
[thick] (21.5,-1)–(22.5,-1);
[thick] (21.5,-2)–(21.5,-1);
[thick] (22.5,-2)–(22.5,-1);

[fill=black] (21.25,-1.25) rectangle (21.75,-0.75);

[thick] (23.25,-2)–(24.25,-2);
[thick] (23.25,-1)–(24.25,-1);
[thick] (23.25,-2)–(23.25,-1);
[thick] (24.25,-2)–(24.25,-1);

[fill=black] (24,-1.25) rectangle (24.5,-0.75);

[thick] (25,-2)–(26,-2);
[thick] (25,-1)–(26,-1);
[thick] (25,-2)–(25,-1);
[thick] (26,-2)–(26,-1);

[fill=black] (25.75,-2.25) rectangle (26.25,-1.75);

[thick] (26.75,-2)–(27.75,-2);
[thick] (26.75,-1)–(27.75,-1);
[thick] (26.75,-2)–(26.75,-1);
[thick] (27.75,-2)–(27.75,-1);

[fill=white] (26.5,-2.25) rectangle (27,-1.75);

[thick] (28.50,-2)–(29.5,-2);
[thick] (28.50,-1)–(29.5,-1);
[thick] (28.50,-2)–(28.5,-1);
[thick] (29.50,-2)–(29.50,-1);

[fill=white] (28.25,-1.25) rectangle (28.75,-0.75);

[thick] (30.25,-2)–(31.25,-2);
[thick] (30.25,-1)–(31.25,-1);
[thick] (30.25,-2)–(30.25,-1);
[thick] (31.25,-2)–(31.25,-1);

[fill=white] (31,-1.25) rectangle (31.5,-0.75);

[thick] (32,-2)–(33,-2);
[thick] (32,-1)–(33,-1);
[thick] (32,-2)–(32,-1);
[thick] (33,-2)–(33,-1);

[fill=white] (32.75,-2.25) rectangle (33.25,-1.75);

[thin] (21,-5.7)–(20.25,-2.3);
[thin] (21,-5.7)–(22,-2.3);
[thin] (21,-5.7)–(30.75,-2.3);
[thin] (21,-5.7)–(32.5,-2.3);

[thin] (24,-5.7)–(23.75,-2.3);
[thin] (24,-5.7)–(25.5,-2.3);
[thin] (24,-5.7)–(27.25,-2.3);
[thin] (24,-5.7)–(29,-2.3);

[thin] (27,-5.7)–(22,-2.3);
[thin] (27,-5.7)–(25.5,-2.3);
[thin] (27,-5.7)–(27.25,-2.3);
[thin] (27,-5.7)–(30.75,-2.3);

[thin] (30,-5.7)–(23.75,-2.3);
[thin] (30,-5.7)–(27.25,-2.3);
[thin] (30,-5.7)–(29,-2.3);
[thin] (30,-5.7)–(32.5,-2.3);

[thin] (33,-5.7)–(25.5,-2.3);
[thin] (33,-5.7)–(27.25,-2.3);
[thin] (33,-5.7)–(29,-2.3);
[thin] (33,-5.7)–(30.75,-2.3);

[text width=0.1cm] at (17.8,2)

[text width=0.1cm] at (23.1,2)
[text width=0.1cm] at (24.85,2)
[text width=0.1cm] at (16.7,-1.5)

[text width=0.1cm] at (21,-11.5)

[text width=0.1cm] at (26.6,2)

[text width=0.1cm] at (27,-11.5)

[text width=0.1cm] at (30,-11.5)
[text width=0.1cm] at (33,-11.5)

[thin] (18.5,1.3)–(17.2,-0.7);
[thin] (18.5,1.3)–(20.25,-0.7);

[thin] (23.75,1.3)–(23.75,-0.7);
[thin] (25.5,1.3)–(25.5,-0.7);

[thin] (21,-10.9)–(21,-8.3);
[thin] (21,-10.9)–(33,-8.3);
[thin] (21,-10.9)–(24,-8.3);
[thin] (21,-10.9)–(27,-8.3);
[thin] (21,-10.9)–(30,-8.3);

[thin] (21,-5.7)–(17.2,-2.3);
[thin] (24,-5.7)–(17.2,-2.3);

[thin] (27,-10.9)–(27,-8.3);
[thin] (30,-10.9)–(30,-8.3);
[thin] (33,-10.9)–(33,-8.3);

[thin] (27,1.1)–(17.2,-0.7);
[thin] (27,1.1)–(32.5,-0.7);
[thin] (27,1.1)–(30.75,-0.7);
[thin] (27,1.1)–(29,-0.7);
[thin] (27,1.1)–(27.25,-0.7);
[thin] (27,1.1)–(25.5,-0.7);
[thin] (27,1.1)–(23.75,-0.7);
[thin] (27,1.1)–(22,-0.7);
[thin] (27,1.1)–(20.25,-0.7);

We now perform the crossing between $v$ and the second positive example, $T_2^{+}$. We cross the only atom in $\Phi_2$ (the atoms of $v$ that are not atoms of $T_2^{+}$), $\phi_{1}$, with one of the two atoms in $T_2^{+}$, say $\epsilon_2$. We create a new atom $\phi_{2}$ and edges $\phi_{2} \rightarrow \phi_{1}$ and $\phi_{2} \rightarrow \epsilon_2$. Before the crossing, the trace of atom $\phi_{1}$ is $\textbf{Tr}(\phi_{1})_{i}=\{0^{*}\}$, but after the crossing is $\textbf{Tr}(\phi_{1})_{f}=\{0^{*},\zeta_2 \}$. Since the trace has changed, we proceed to select another atom in $T_2^{+}$, that is, $\epsilon_3$. We then create a new atom $\phi_{3}$ and edges $\phi_{3} \rightarrow \phi_{1}$ and $\phi_{3} \rightarrow \epsilon_3$. After appending $\phi_{3}$ with this new edges to the graph the trace of $\phi_{1}$ becomes $\textbf{Tr}(\phi_{1})_{f}=\textbf{Tr}(\phi_{2}) \cap \textbf{Tr}(\phi_{3})=\{0^{*}\}$, so we now have the trace invariance we were looking for. The trace of atom $\epsilon_{2}$ also remains unchanged as $\textbf{Tr}(\epsilon_{2})_{i}=\{0^{*},\zeta_{1}\}$ equals $\textbf{Tr}(\epsilon_{2})_{f}=\textbf{Tr}(\phi_{2})=\{0^{*},\zeta_{1}\}$. For the trace of $\epsilon_{3}$ we have $\textbf{Tr}(\epsilon_{3})_{i}=\textbf{Tr}(\epsilon_{3})_{f}=\{0^{*},\zeta_{1},\zeta_{3}\}$ so it also remains unaltered.
Eliminating the initial atoms $\phi_{1}, \epsilon_2$ and $\epsilon_3$ we have the graph

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[thick] (3,0)–(5,0);
[thick] (4,0)–(4,2);
[thick] (5,0)–(5,2);
[thick] (3,0)–(3,2);
[thick] (3,2)–(5,2);
[thick] (3,1)–(5,1);

[fill=black] (4,0) rectangle (5,2);

[thick] (5.5,-0.5)–(5.5,2.5);

[thick] (6,0)–(8,0);
[thick] (6,0)–(6,2);
[thick] (8,0)–(8,2);
[thick] (6,1)–(8,1);
[thick] (6,2)–(8,2);
[thick] (7,0)–(7,2);

[fill=black] (6,1) rectangle (7,2);
[fill=black] (7,0) rectangle (8,1);

[thick] (9,0)–(11,0);
[thick] (10,0)–(10,2);
[thick] (11,0)–(11,2);
[thick] (9,0)–(9,2);
[thick] (9,2)–(11,2);
[thick] (9,1)–(11,1);

[fill=black] (10,1) rectangle (11,2);

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-0.3)–(0.25,-3.7);
[thin] (1,-0.3)–(2,-3.7);
[thin] (1,-0.3)–(10.75,-3.7);
[thin] (1,-0.3)–(12.5,-3.7);

[thin] (4,-0.3)–(5.5,-3.7);
[thin] (4,-0.3)–(3.75,-3.7);
[thin] (4,-0.3)–(7.25,-3.7);
[thin] (4,-0.3)–(9,-3.7);

[thin] (7,-0.3)–(2,-3.7);
[thin] (7,-0.3)–(5.5,-3.7);
[thin] (7,-0.3)–(7.25,-3.7);
[thin] (7,-0.3)–(10.75,-3.7);

[thin] (10,-0.3)–(3.75,-3.7);
[thin] (10,-0.3)–(7.25,-3.7);
[thin] (10,-0.3)–(9,-3.7);
[thin] (10,-0.3)–(12.5,-3.7);

[thin] (13,-0.3)–(5.5,-3.7);
[thin] (13,-0.3)–(7.25,-3.7);
[thin] (13,-0.3)–(9,-3.7);
[thin] (13,-0.3)–(10.75,-3.7);

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (7,-7.9)

[text width=0.1cm] at (0.25,-7.9)

[text width=0.1cm] at (3.75,-7.9)

[thin] (0.25,-7.3)–(-3,-5.3);
[thin] (0.25,-7.3)–(0.25,-5.3);
[thin] (0.25,-7.3)–(3.75,-5.3);

[thin] (3.75,-7.3)–(-3,-5.3);
[thin] (3.75,-7.3)–(0.25,-5.3);
[thin] (3.75,-7.3)–(5.5,-5.3);

[thin] (7,-7.3)–(-3,-5.3);

[thin] (7,-7.3)–(12.5,-5.3);
[thin] (7,-7.3)–(10.75,-5.3);
[thin] (7,-7.3)–(9,-5.3);
[thin] (7,-7.3)–(7.25,-5.3);
[thin] (7,-7.3)–(5.5,-5.3);
[thin] (7,-7.3)–(3.75,-5.3);
[thin] (7,-7.3)–(2,-5.3);
[thin] (7,-7.3)–(0.25,-5.3);

[thick] (20,-8)–(22,-8);
[thick] (21,-8)–(21,-6);
[thick] (22,-8)–(22,-6);
[thick] (20,-8)–(20,-6);
[thick] (20,-6)–(22,-6);
[thick] (20,-7)–(22,-7);

[fill=black] (20,-8) rectangle (21,-6);

[thick] (23,-8)–(25,-8);
[thick] (24,-8)–(24,-6);
[thick] (25,-8)–(25,-6);
[thick] (23,-8)–(23,-6);
[thick] (23,-6)–(25,-6);
[thick] (23,-7)–(25,-7);

[fill=black] (24,-8) rectangle (25,-6);

[thick] (25.5,-7.3)–(25.5,-5.5);

[thick] (26,-8)–(28,-8);
[thick] (27,-8)–(27,-6);
[thick] (28,-8)–(28,-6);
[thick] (26,-8)–(26,-6);
[thick] (26,-6)–(28,-6);
[thick] (26,-7)–(28,-7);

[fill=black] (26,-7) rectangle (27,-6);
[fill=black] (27,-8) rectangle (28,-7);

[thick] (29,-8)–(31,-8);
[thick] (30,-8)–(30,-6);
[thick] (31,-8)–(31,-6);
[thick] (29,-8)–(29,-6);
[thick] (29,-6)–(31,-6);
[thick] (29,-7)–(31,-7);

[fill=black] (30,-7) rectangle (31,-6);

[thick] (32,-8)–(34,-8);
[thick] (33,-8)–(33,-6);
[thick] (34,-8)–(34,-6);
[thick] (32,-8)–(32,-6);
[thick] (32,-6)–(34,-6);
[thick] (32,-7)–(34,-7);

[fill=black] (33,-8) rectangle (34,-7);

[thick] (19.75,-2)–(20.75,-2);
[thick] (19.75,-1)–(20.75,-1);
[thick] (19.75,-2)–(19.75,-1);
[thick] (20.75,-2)–(20.75,-1);

[fill=black] (19.5,-2.25) rectangle (20,-1.75);

[thick] (21.5,-2)–(22.5,-2);
[thick] (21.5,-1)–(22.5,-1);
[thick] (21.5,-2)–(21.5,-1);
[thick] (22.5,-2)–(22.5,-1);

[fill=black] (21.25,-1.25) rectangle (21.75,-0.75);

[thick] (23.25,-2)–(24.25,-2);
[thick] (23.25,-1)–(24.25,-1);
[thick] (23.25,-2)–(23.25,-1);
[thick] (24.25,-2)–(24.25,-1);

[fill=black] (24,-1.25) rectangle (24.5,-0.75);

[thick] (25,-2)–(26,-2);
[thick] (25,-1)–(26,-1);
[thick] (25,-2)–(25,-1);
[thick] (26,-2)–(26,-1);

[fill=black] (25.75,-2.25) rectangle (26.25,-1.75);

[thick] (26.75,-2)–(27.75,-2);
[thick] (26.75,-1)–(27.75,-1);
[thick] (26.75,-2)–(26.75,-1);
[thick] (27.75,-2)–(27.75,-1);

[fill=white] (26.5,-2.25) rectangle (27,-1.75);

[thick] (28.50,-2)–(29.5,-2);
[thick] (28.50,-1)–(29.5,-1);
[thick] (28.50,-2)–(28.5,-1);
[thick] (29.50,-2)–(29.50,-1);

[fill=white] (28.25,-1.25) rectangle (28.75,-0.75);

[thick] (30.25,-2)–(31.25,-2);
[thick] (30.25,-1)–(31.25,-1);
[thick] (30.25,-2)–(30.25,-1);
[thick] (31.25,-2)–(31.25,-1);

[fill=white] (31,-1.25) rectangle (31.5,-0.75);

[thick] (32,-2)–(33,-2);
[thick] (32,-1)–(33,-1);
[thick] (32,-2)–(32,-1);
[thick] (33,-2)–(33,-1);

[fill=white] (32.75,-2.25) rectangle (33.25,-1.75);

[thin] (21,-5.7)–(20.25,-2.3);
[thin] (21,-5.7)–(22,-2.3);
[thin] (21,-5.7)–(30.75,-2.3);
[thin] (21,-5.7)–(32.5,-2.3);

[thin] (24,-5.7)–(23.75,-2.3);
[thin] (24,-5.7)–(25.5,-2.3);
[thin] (24,-5.7)–(27.25,-2.3);
[thin] (24,-5.7)–(29,-2.3);

[thin] (27,-5.7)–(22,-2.3);
[thin] (27,-5.7)–(25.5,-2.3);
[thin] (27,-5.7)–(27.25,-2.3);
[thin] (27,-5.7)–(30.75,-2.3);

[thin] (30,-5.7)–(23.75,-2.3);
[thin] (30,-5.7)–(27.25,-2.3);
[thin] (30,-5.7)–(29,-2.3);
[thin] (30,-5.7)–(32.5,-2.3);

[thin] (33,-5.7)–(25.5,-2.3);
[thin] (33,-5.7)–(27.25,-2.3);
[thin] (33,-5.7)–(29,-2.3);
[thin] (33,-5.7)–(30.75,-2.3);

[text width=0.1cm] at (23.1,2)
[text width=0.1cm] at (19.6,2)
[text width=0.1cm] at (16.7,-1.5)

[text width=0.1cm] at (21,-11.5)

[text width=0.1cm] at (26.6,2)

[text width=0.1cm] at (27,-11.5)

[text width=0.1cm] at (30,-11.5)
[text width=0.1cm] at (33,-11.5)

[thin] (20.25,1.1)–(17.2,-0.7);
[thin] (20.25,1.1)–(20.25,-0.7);
[thin] (20.25,1.1)–(23.75,-0.7);

[thin] (23.75,1.1)–(17.2,-0.7);
[thin] (23.75,1.1)–(20.25,-0.7);
[thin] (23.75,1.1)–(25.5,-0.7);

[thin] (21,-10.9)–(21,-8.3);
[thin] (21,-10.9)–(33,-8.3);
[thin] (21,-10.9)–(24,-8.3);
[thin] (21,-10.9)–(27,-8.3);
[thin] (21,-10.9)–(30,-8.3);

[thin] (21,-5.7)–(17.2,-2.3);
[thin] (24,-5.7)–(17.2,-2.3);

[thin] (27,-10.9)–(27,-8.3);
[thin] (30,-10.9)–(30,-8.3);
[thin] (33,-10.9)–(33,-8.3);

[thin] (27,1.1)–(17.2,-0.7);
[thin] (27,1.1)–(32.5,-0.7);
[thin] (27,1.1)–(30.75,-0.7);
[thin] (27,1.1)–(29,-0.7);
[thin] (27,1.1)–(27.25,-0.7);
[thin] (27,1.1)–(25.5,-0.7);
[thin] (27,1.1)–(23.75,-0.7);
[thin] (27,1.1)–(22,-0.7);
[thin] (27,1.1)–(20.25,-0.7);

If we had more atoms in $v$, we would repeat the same procedure for these atoms. In our present case, we have finished.

The Sparse Crossing operation has worked; the positive training examples all obey $v<T_{i}^{+}$, and the negative ones $ v \not< T_{j}^{-}$. The atoms of $v$ are ${\bf{GL}^{a}}(v)=\{0,\phi_{2},\phi_{3}\}$ and the atoms for the positive training examples are also ${\bf{GL}^{a}}(T_{1,2}^{+})=\{0,\phi_{2},\phi_{3}\}$, while for the negative examples we have ${\bf{GL}^{a}}(T_{1,3}^{-})=\{0,\phi_{3}\}$ and ${\bf{GL}^{a}}(T_{2}^{-})=\{0,\phi_{2}\}$.

§.§ Reduction operation

Models found by Sparse Crossing are much smaller than models found by Full Crossing.  We are still interested in further reducing their size. A suitable size reduction algorithm should be trace-invariant. Trace invariance preserves trace constraints and preserving trace constraints ensures that we will be able to carry out pending Sparse Crossing operations. This means that a trace-invariant reduction scheme can be called at any time during learning, as often as required.

While carrying out Sparse Crossing operations we were careful to keep the trace of all the atoms unaltered, for the reduction operation we will focus on constants instead. An operation that keeps the trace of all constants unaltered also keeps the trace of the terms unaltered and the trace constraints preserved. Since atoms are not mentioned in trace constraints we do not really need them to be trace-invariant; it is enough with keeping the constants trace-invariant.  Furthermore, we can remove atoms from a model as long as we keep the traces of all the constants unchanged.

Our reduction scheme consists of finding a subset $Q$ of the atoms that produces the same traces for all constants. We can then discard the atoms that are not in $Q$. We start with $Q$ empty. Then we review the constants one by one in random order. For each constant $c$ we select a subset of its atoms such that the trace of $c$ calculated using only the atoms in this subset corresponds with the actual trace of $c$. The selected atoms are added to $Q$ before we move onto the next constant. When selecting atoms for the next constant $c$ we start with the intersection between its atoms and $Q$, i.e ${{\bf{GL}}^a}(c) \cap Q$, and continue adding atoms to $Q$ until the trace calculated taking into account the atoms of ${{\bf{GL}}^a}(c) \cap Q$ equates ${\bf{Tr}}(c)$. Once all constants are reviewed any atom that is not in $Q$ can be safely removed from the algebra. Algorithm <ref> in Appendix <ref> is an improved version of this method.

At the point where we are with our toy problem we have already obtained an atomized model that distinguishes well positive from negative examples. We are going to apply the reduction algorithm to see if we can get rid of some of its atoms. We are going to review the constants starting by the third one. In our example, the trace of the third constant only depends on a single atom $\textbf{Tr}(c_{3})=\textbf{Tr}(0) \cap \textbf{Tr}(\phi_{2})=\textbf{Tr}(\phi_{2})$, so we must keep $\phi_{2}$ for trace invariance of this constant. An analogous situation takes place for the fourth constant, for which we have that its trace only depends on $\phi_{3}$, $\textbf{Tr}(c_{4})=\textbf{Tr}(\phi_{3})$, so it cannot be eliminated, either. The model we have obtained cannot be reduced.

To illustrate a simple size reduction in action, let us add to the graphs an extra atom $\beta$ edged to the first constant, $\beta \rightarrow c_{1}$. This new atom does not change any traces and gives the graphs

[thick] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);

[thick] (3,0)–(5,0);
[thick] (4,0)–(4,2);
[thick] (5,0)–(5,2);
[thick] (3,0)–(3,2);
[thick] (3,2)–(5,2);
[thick] (3,1)–(5,1);

[fill=black] (4,0) rectangle (5,2);

[thick] (5.5,-0.5)–(5.5,2.5);

[thick] (6,0)–(8,0);
[thick] (6,0)–(6,2);
[thick] (8,0)–(8,2);
[thick] (6,1)–(8,1);
[thick] (6,2)–(8,2);
[thick] (7,0)–(7,2);

[fill=black] (6,1) rectangle (7,2);
[fill=black] (7,0) rectangle (8,1);

[thick] (9,0)–(11,0);
[thick] (10,0)–(10,2);
[thick] (11,0)–(11,2);
[thick] (9,0)–(9,2);
[thick] (9,2)–(11,2);
[thick] (9,1)–(11,1);

[fill=black] (10,1) rectangle (11,2);

[thick] (12,0)–(14,0);
[thick] (13,0)–(13,2);
[thick] (14,0)–(14,2);
[thick] (12,0)–(12,2);
[thick] (12,2)–(14,2);
[thick] (12,1)–(14,1);

[fill=black] (13,0) rectangle (14,1);

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thick] (6.75,-5)–(7.75,-5);
[thick] (6.75,-4)–(7.75,-4);
[thick] (6.75,-5)–(6.75,-4);
[thick] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thick] (8.50,-5)–(9.5,-5);
[thick] (8.50,-4)–(9.5,-4);
[thick] (8.50,-5)–(8.5,-4);
[thick] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thick] (10.25,-5)–(11.25,-5);
[thick] (10.25,-4)–(11.25,-4);
[thick] (10.25,-5)–(10.25,-4);
[thick] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thick] (12,-5)–(13,-5);
[thick] (12,-4)–(13,-4);
[thick] (12,-5)–(12,-4);
[thick] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-0.3)–(0.25,-3.7);
[thin] (1,-0.3)–(2,-3.7);
[thin] (1,-0.3)–(10.75,-3.7);
[thin] (1,-0.3)–(12.5,-3.7);

[thin] (4,-0.3)–(5.5,-3.7);
[thin] (4,-0.3)–(3.75,-3.7);
[thin] (4,-0.3)–(7.25,-3.7);
[thin] (4,-0.3)–(9,-3.7);

[thin] (7,-0.3)–(2,-3.7);
[thin] (7,-0.3)–(5.5,-3.7);
[thin] (7,-0.3)–(7.25,-3.7);
[thin] (7,-0.3)–(10.75,-3.7);

[thin] (10,-0.3)–(3.75,-3.7);
[thin] (10,-0.3)–(7.25,-3.7);
[thin] (10,-0.3)–(9,-3.7);
[thin] (10,-0.3)–(12.5,-3.7);

[thin] (13,-0.3)–(5.5,-3.7);
[thin] (13,-0.3)–(7.25,-3.7);
[thin] (13,-0.3)–(9,-3.7);
[thin] (13,-0.3)–(10.75,-3.7);

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (7,-7.9)

[text width=0.1cm] at (0.25,-7.9)

[text width=0.1cm] at (3.75,-7.9)

[text width=0.1cm] at (-3,-7.9)

[thin] (-3,-7.3)–(0.25,-5.3);

[thin] (0.25,-7.3)–(-3,-5.3);
[thin] (0.25,-7.3)–(0.25,-5.3);
[thin] (0.25,-7.3)–(3.75,-5.3);

[thin] (3.75,-7.3)–(-3,-5.3);
[thin] (3.75,-7.3)–(0.25,-5.3);
[thin] (3.75,-7.3)–(5.5,-5.3);

[thin] (7,-7.3)–(-3,-5.3);

[thin] (7,-7.3)–(12.5,-5.3);
[thin] (7,-7.3)–(10.75,-5.3);
[thin] (7,-7.3)–(9,-5.3);
[thin] (7,-7.3)–(7.25,-5.3);
[thin] (7,-7.3)–(5.5,-5.3);
[thin] (7,-7.3)–(3.75,-5.3);
[thin] (7,-7.3)–(2,-5.3);
[thin] (7,-7.3)–(0.25,-5.3);

[thick] (20,-8)–(22,-8);
[thick] (21,-8)–(21,-6);
[thick] (22,-8)–(22,-6);
[thick] (20,-8)–(20,-6);
[thick] (20,-6)–(22,-6);
[thick] (20,-7)–(22,-7);

[fill=black] (20,-8) rectangle (21,-6);

[thick] (23,-8)–(25,-8);
[thick] (24,-8)–(24,-6);
[thick] (25,-8)–(25,-6);
[thick] (23,-8)–(23,-6);
[thick] (23,-6)–(25,-6);
[thick] (23,-7)–(25,-7);

[fill=black] (24,-8) rectangle (25,-6);

[thick] (25.5,-7.3)–(25.5,-5.5);

[thick] (26,-8)–(28,-8);
[thick] (27,-8)–(27,-6);
[thick] (28,-8)–(28,-6);
[thick] (26,-8)–(26,-6);
[thick] (26,-6)–(28,-6);
[thick] (26,-7)–(28,-7);

[fill=black] (26,-7) rectangle (27,-6);
[fill=black] (27,-8) rectangle (28,-7);

[thick] (29,-8)–(31,-8);
[thick] (30,-8)–(30,-6);
[thick] (31,-8)–(31,-6);
[thick] (29,-8)–(29,-6);
[thick] (29,-6)–(31,-6);
[thick] (29,-7)–(31,-7);

[fill=black] (30,-7) rectangle (31,-6);

[thick] (32,-8)–(34,-8);
[thick] (33,-8)–(33,-6);
[thick] (34,-8)–(34,-6);
[thick] (32,-8)–(32,-6);
[thick] (32,-6)–(34,-6);
[thick] (32,-7)–(34,-7);

[fill=black] (33,-8) rectangle (34,-7);

[thick] (19.75,-2)–(20.75,-2);
[thick] (19.75,-1)–(20.75,-1);
[thick] (19.75,-2)–(19.75,-1);
[thick] (20.75,-2)–(20.75,-1);

[fill=black] (19.5,-2.25) rectangle (20,-1.75);

[thick] (21.5,-2)–(22.5,-2);
[thick] (21.5,-1)–(22.5,-1);
[thick] (21.5,-2)–(21.5,-1);
[thick] (22.5,-2)–(22.5,-1);

[fill=black] (21.25,-1.25) rectangle (21.75,-0.75);

[thick] (23.25,-2)–(24.25,-2);
[thick] (23.25,-1)–(24.25,-1);
[thick] (23.25,-2)–(23.25,-1);
[thick] (24.25,-2)–(24.25,-1);

[fill=black] (24,-1.25) rectangle (24.5,-0.75);

[thick] (25,-2)–(26,-2);
[thick] (25,-1)–(26,-1);
[thick] (25,-2)–(25,-1);
[thick] (26,-2)–(26,-1);

[fill=black] (25.75,-2.25) rectangle (26.25,-1.75);

[thick] (26.75,-2)–(27.75,-2);
[thick] (26.75,-1)–(27.75,-1);
[thick] (26.75,-2)–(26.75,-1);
[thick] (27.75,-2)–(27.75,-1);

[fill=white] (26.5,-2.25) rectangle (27,-1.75);

[thick] (28.50,-2)–(29.5,-2);
[thick] (28.50,-1)–(29.5,-1);
[thick] (28.50,-2)–(28.5,-1);
[thick] (29.50,-2)–(29.50,-1);

[fill=white] (28.25,-1.25) rectangle (28.75,-0.75);

[thick] (30.25,-2)–(31.25,-2);
[thick] (30.25,-1)–(31.25,-1);
[thick] (30.25,-2)–(30.25,-1);
[thick] (31.25,-2)–(31.25,-1);

[fill=white] (31,-1.25) rectangle (31.5,-0.75);

[thick] (32,-2)–(33,-2);
[thick] (32,-1)–(33,-1);
[thick] (32,-2)–(32,-1);
[thick] (33,-2)–(33,-1);

[fill=white] (32.75,-2.25) rectangle (33.25,-1.75);

[thin] (21,-5.7)–(20.25,-2.3);
[thin] (21,-5.7)–(22,-2.3);
[thin] (21,-5.7)–(30.75,-2.3);
[thin] (21,-5.7)–(32.5,-2.3);

[thin] (24,-5.7)–(23.75,-2.3);
[thin] (24,-5.7)–(25.5,-2.3);
[thin] (24,-5.7)–(27.25,-2.3);
[thin] (24,-5.7)–(29,-2.3);

[thin] (27,-5.7)–(22,-2.3);
[thin] (27,-5.7)–(25.5,-2.3);
[thin] (27,-5.7)–(27.25,-2.3);
[thin] (27,-5.7)–(30.75,-2.3);

[thin] (30,-5.7)–(23.75,-2.3);
[thin] (30,-5.7)–(27.25,-2.3);
[thin] (30,-5.7)–(29,-2.3);
[thin] (30,-5.7)–(32.5,-2.3);

[thin] (33,-5.7)–(25.5,-2.3);
[thin] (33,-5.7)–(27.25,-2.3);
[thin] (33,-5.7)–(29,-2.3);
[thin] (33,-5.7)–(30.75,-2.3);

[text width=0.1cm] at (16.7,2)

[text width=0.1cm] at (23.1,2)

[text width=0.1cm] at (19.6,2)

[text width=0.1cm] at (16.7,-1.5)

[text width=0.1cm] at (21,-11.5)

[text width=0.1cm] at (26.6,2)

[text width=0.1cm] at (27,-11.5)

[text width=0.1cm] at (30,-11.5)

[text width=0.1cm] at (33,-11.5)

[thin] (17.2,1.3)–(20.25,-0.7);

[thin] (20.25,1.1)–(17.2,-0.7);
[thin] (20.25,1.1)–(20.25,-0.7);
[thin] (20.25,1.1)–(23.75,-0.7);

[thin] (23.75,1.1)–(17.2,-0.7);
[thin] (23.75,1.1)–(20.25,-0.7);
[thin] (23.75,1.1)–(25.5,-0.7);

[thin] (21,-10.9)–(21,-8.3);
[thin] (21,-10.9)–(33,-8.3);
[thin] (21,-10.9)–(24,-8.3);
[thin] (21,-10.9)–(27,-8.3);
[thin] (21,-10.9)–(30,-8.3);

[thin] (21,-5.7)–(17.2,-2.3);
[thin] (24,-5.7)–(17.2,-2.3);

[thin] (27,-10.9)–(27,-8.3);
[thin] (30,-10.9)–(30,-8.3);
[thin] (33,-10.9)–(33,-8.3);

[thin] (27,1.1)–(17.2,-0.7);
[thin] (27,1.1)–(32.5,-0.7);
[thin] (27,1.1)–(30.75,-0.7);
[thin] (27,1.1)–(29,-0.7);
[thin] (27,1.1)–(27.25,-0.7);
[thin] (27,1.1)–(25.5,-0.7);
[thin] (27,1.1)–(23.75,-0.7);
[thin] (27,1.1)–(22,-0.7);
[thin] (27,1.1)–(20.25,-0.7);

Revising the first constant, we then have that its trace depends on the trace of the three atoms and atom $0$ as $\textbf{Tr}(c_{1})=\textbf{Tr}(0) \cap \textbf{Tr}(\phi_{2}) \cap \textbf{Tr}(\phi_{3}) \cap \textbf{Tr}(\beta)$, with $\textbf{Tr}(0)=\{0^{*},\zeta_{1},\zeta_{2},\zeta_{3}\}$,
$\textbf{Tr}(\phi_{3})=\{0^{*},\zeta_{1},\zeta_{3}\}$ and $\textbf{Tr}(\beta)=\{0^{*}\}$. The constant $c_1$ would remain trace-invariant if we eliminated atoms $\phi_{2}$ and $\phi_{3}$ or only $\beta$. But, as for the invariance of constants $c_3$ and $c_4$ we need atoms $\phi_{2}$ and $\phi_{3}$, it is $\beta$ the atom we can eliminate. The stochastic Algorithm <ref> in Appendix <ref> typically would delete atom $\beta$ in a single call or within a few calls.

There are other reduction schemes. For example, a size reduction scheme based on keeping just enough atoms to discriminate the set $R^{-}$ ensures an atomization with a size under that of set $R^{-}$. The problem with this reduction scheme is that it fails to produce good generalizing models as it seems to reduce algebraic freedom (see Section <ref>) more than one would wish, especially at the initial phases of learning when the error is large and the algebra should grow rather than shrink. In addition, since this scheme can violate negative trace constraints, it can only be used once the full embedding is completed. If used at some intermediate stage of the embedding, subsequent Sparse Crossing operations may produce models that do not satisfy $R^{-}$.  This is a problem because the model can become very large before we can reduce its size. However, this scheme can be successfully applied to the dual, $M^{*}$, right before trace constraints are enforced, ensuring that the number of atoms in $M^{*}$ is never larger than the size of the set $R^{-}$. This reduction scheme corresponds to Algorithm <ref> in Appendix <ref>.

The trace-preserving reduction scheme presented in this section works well in combination with Sparse Crossing and finds small, generalizing models efficiently. For this reduction scheme there is no guarantee that the size of $M$ is going to end up under the size of $M^{*}$ or under the size of $R^{-}$. In fact, it is often the case that the atomization of $M$ is a few times larger than the atomization of $M^{*}$. Even when is smaller then $M$, $M^{*}$ does not generalize because it is not sufficiently free.

§.§ Batch training

We have seen how to learn an atomized model from a set $R$ of positive and negative examples. In practice, we would check the accuracy of the learned model in test data. If the accuracy is below some desired level, we would continue training with a new set of examples. Rather than a single set $R$ we have a series of batches $R_{0}, R_{1},...,R_{n}$ where the subscript corresponds with the training epoch.

Assume we are in epoch $1$. In order to keep the graph $G(S)$ manageable we want to remove from it the nodes corresponding to elements mentioned in $R_{0}$, as well as deleting the set $R_{0}$ itself to leave space for the new set of relations $R_{1}$. However, if we delete $R_{0}$ we run into the following problem; Often when we resume learning by embedding $R_{1}$ some relations of $R_{0}$ no longer hold. We need a method to minimize the likelihood for this to occur.

In the following we discuss how to do batch learning. Once learning epoch $0$ is completed we have $R_{0}$ encoded into atoms. What we do is replacing $R_{0}$ by a set of relations that $\emph{define}$ its atoms in the following way; For each atom $\phi$, we create one term $T_{\phi}$ equal to the idempotent summation of all the constants that do not contain atom $\phi$. For each constant $c$ so $(\phi < c)$, we create a new relation $\neg(c < T_{\phi})$. We call this set of terms and relations the  pinning structure of the algebra because they help to preserve knowledge when $R_{0}$ is deleted and additional learning takes place. We call terms $T_{\phi}$ pinning terms and the set of relations, pinning relations and refer to them with $R_{p}$.

Following this procedure in our toy example, we would create two pinning terms. For atom $\phi_{2}$, with $\phi_{2} < c_{1}$ and $\phi_{2} < c_{3}$, we create $T_{\phi_{2}}=c_{2} \odot c_{4} \odot c_{5} \odot c_{6} \odot c_{7} \odot c_{8}$. For atom $\phi_{3}$, with $\phi_{3} < c_{1}$ and $\phi_{2} < c_{4}$, we create $T_{\phi_{3}}=c_{2} \odot c_{3} \odot c_{5} \odot c_{6} \odot c_{7} \odot c_{8}$.

We then require the negative relations $\neg(c_{1}<T_{\phi_{2}})$, $\neg(c_{3}<T_{\phi_{3}})$, $\neg(v<T_{\phi_{2}})$, $\neg(c_{1}<T_{\phi_{3}})$, $\neg(c_{4}<T_{\phi_{3}})$ and $\neg(v<T_{\phi_{3}})$, and obtain

[thin] (0,0)–(2,0);
[thick] (1,0)–(1,2);
[thick] (2,0)–(2,2);
[thick] (0,0)–(0,2);
[thick] (0,2)–(2,2);
[thick] (0,1)–(2,1);

[fill=black] (0,0) rectangle (1,2);
[fill=black] (1,1) rectangle (2,2);

[thick] (2.5,-0.5)–(2.5,2.5);

[thin] (3,0)–(5,0);
[thin] (4,0)–(4,2);
[thin] (5,0)–(5,2);
[thin] (3,0)–(3,2);
[thin] (3,2)–(5,2);
[thin] (3,1)–(5,1);

[fill=black] (3,1) rectangle (5,2);

[thin] (2.5,-0.5)–(2.5,2.5);

[thin] (-0.25,-5)–(0.75,-5);
[thin] (-0.25,-4)–(0.75,-4);
[thin] (-0.25,-5)–(-0.25,-4);
[thin] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);

[thin] (1.5,-5)–(2.5,-5);
[thin] (1.5,-4)–(2.5,-4);
[thin] (1.5,-5)–(1.5,-4);
[thin] (2.5,-5)–(2.5,-4);

[fill=black] (1.25,-4.25) rectangle (1.75,-3.75);

[thin] (3.25,-5)–(4.25,-5);
[thin] (3.25,-4)–(4.25,-4);
[thin] (3.25,-5)–(3.25,-4);
[thin] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);

[thin] (5,-5)–(6,-5);
[thin] (5,-4)–(6,-4);
[thin] (5,-5)–(5,-4);
[thin] (6,-5)–(6,-4);

[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

[thin] (6.75,-5)–(7.75,-5);
[thin] (6.75,-4)–(7.75,-4);
[thin] (6.75,-5)–(6.75,-4);
[thin] (7.75,-5)–(7.75,-4);

[fill=white] (6.5,-5.25) rectangle (7,-4.75);

[thin] (8.50,-5)–(9.5,-5);
[thin] (8.50,-4)–(9.5,-4);
[thin] (8.50,-5)–(8.5,-4);
[thin] (9.50,-5)–(9.50,-4);

[fill=white] (8.25,-4.25) rectangle (8.75,-3.75);

[thin] (10.25,-5)–(11.25,-5);
[thin] (10.25,-4)–(11.25,-4);
[thin] (10.25,-5)–(10.25,-4);
[thin] (11.25,-5)–(11.25,-4);

[fill=white] (11,-4.25) rectangle (11.5,-3.75);

[thin] (12,-5)–(13,-5);
[thin] (12,-4)–(13,-4);
[thin] (12,-5)–(12,-4);
[thin] (13,-5)–(13,-4);

[fill=white] (12.75,-5.25) rectangle (13.25,-4.75);

[thin] (1,-0.3)–(0.25,-3.7);
[thin] (1,-0.3)–(2,-3.7);

[thin] (1,-0.3)–(12.5,-3.7);
[thin] (1,-0.3)–(3.75,-3.7);

[thin] (4,-0.3)–(2,-3.7);
[thin] (4,-0.3)–(3.75,-3.7);
[thin] (4,-0.3)–(7.25,-3.7);
[thin] (4,-0.3)–(12.5,-3.7);

[thin] (7,-0.3)–(2,-3.7);
[thin] (7,-0.3)–(5.5,-3.7);
[thin] (7,-0.3)–(7.25,-3.7);
[thin] (7,-0.3)–(9,-3.7);
[thin] (7,-0.3)–(10.75,-3.7);
[thin] (7,-0.3)–(12.5,-3.7);

[thin] (10,3.3)–(4,2.5);

[thin] (10,3.3)–(9,-3.7);
[thin] (10,3.3)–(10.75,-3.7);

[text width=0.1cm] at (6.5,1)

[text width=0.1cm] at (9.5,4)

[text width=0.1cm] at (-3,-4.5)

[text width=0.1cm] at (7,-7.9)

[text width=0.1cm] at (0.25,-7.9)

[text width=0.1cm] at (3.75,-7.9)

[thin] (0.25,-7.3)–(-3,-5.3);
[thin] (0.25,-7.3)–(0.25,-5.3);
[thin] (0.25,-7.3)–(3.75,-5.3);

[thin] (3.75,-7.3)–(-3,-5.3);
[thin] (3.75,-7.3)–(0.25,-5.3);
[thin] (3.75,-7.3)–(5.5,-5.3);

[thin] (7,-7.3)–(-3,-5.3);

[thin] (7,-7.3)–(12.5,-5.3);
[thin] (7,-7.3)–(10.75,-5.3);
[thin] (7,-7.3)–(9,-5.3);
[thin] (7,-7.3)–(7.25,-5.3);
[thin] (7,-7.3)–(5.5,-5.3);
[thin] (7,-7.3)–(3.75,-5.3);
[thin] (7,-7.3)–(2,-5.3);
[thin] (7,-7.3)–(0.25,-5.3);

[thin] (20,-8)–(22,-8);
[thin] (21,-8)–(21,-6);
[thin] (22,-8)–(22,-6);
[thin] (20,-8)–(20,-6);
[thin] (20,-6)–(22,-6);
[thin] (20,-7)–(22,-7);

[fill=black] (20,-8) rectangle (21,-6);
[fill=black] (21,-7) rectangle (22,-6);

[thin] (22.5,-7.3)–(22.5,-5.5);

[thin] (23,-8)–(25,-8);
[thin] (24,-8)–(24,-6);
[thin] (25,-8)–(25,-6);
[thin] (23,-8)–(23,-6);
[thin] (23,-6)–(25,-6);
[thin] (23,-7)–(25,-7);

[fill=black] (23,-6) rectangle (25,-7);

[thin] (19.75,-2)–(20.75,-2);
[thin] (19.75,-1)–(20.75,-1);
[thin] (19.75,-2)–(19.75,-1);
[thin] (20.75,-2)–(20.75,-1);

[fill=black] (19.5,-2.25) rectangle (20,-1.75);

[thin] (21.5,-2)–(22.5,-2);
[thin] (21.5,-1)–(22.5,-1);
[thin] (21.5,-2)–(21.5,-1);
[thin] (22.5,-2)–(22.5,-1);

[fill=black] (21.25,-1.25) rectangle (21.75,-0.75);

[thin] (23.25,-2)–(24.25,-2);
[thin] (23.25,-1)–(24.25,-1);
[thin] (23.25,-2)–(23.25,-1);
[thin] (24.25,-2)–(24.25,-1);

[fill=black] (24,-1.25) rectangle (24.5,-0.75);

[thin] (25,-2)–(26,-2);
[thin] (25,-1)–(26,-1);
[thin] (25,-2)–(25,-1);
[thin] (26,-2)–(26,-1);

[fill=black] (25.75,-2.25) rectangle (26.25,-1.75);

[thin] (26.75,-2)–(27.75,-2);
[thin] (26.75,-1)–(27.75,-1);
[thin] (26.75,-2)–(26.75,-1);
[thin] (27.75,-2)–(27.75,-1);

[fill=white] (26.5,-2.25) rectangle (27,-1.75);

[thin] (28.50,-2)–(29.5,-2);
[thin] (28.50,-1)–(29.5,-1);
[thin] (28.50,-2)–(28.5,-1);
[thin] (29.50,-2)–(29.50,-1);

[fill=white] (28.25,-1.25) rectangle (28.75,-0.75);

[thin] (30.25,-2)–(31.25,-2);
[thin] (30.25,-1)–(31.25,-1);
[thin] (30.25,-2)–(30.25,-1);
[thin] (31.25,-2)–(31.25,-1);

[fill=white] (31,-1.25) rectangle (31.5,-0.75);

[thin] (32,-2)–(33,-2);
[thin] (32,-1)–(33,-1);
[thin] (32,-2)–(32,-1);
[thin] (33,-2)–(33,-1);

[fill=white] (32.75,-2.25) rectangle (33.25,-1.75);

[thin] (21,-5.7)–(20.25,-2.3);
[thin] (21,-5.7)–(22,-2.3);
[thin] (21,-5.7)–(23.75,-2.3);
[thin] (21,-5.7)–(32.5,-2.3);

[thin] (24,-5.7)–(23.75,-2.3);
[thin] (24,-5.7)–(22,-2.3);
[thin] (24,-5.7)–(32.5,-2.3);
[thin] (24,-5.7)–(27.25,-2.3);

[thin] (27,-5.7)–(22,-2.3);
[thin] (27,-5.7)–(25.5,-2.3);
[thin] (27,-5.7)–(27.25,-2.3);
[thin] (27,-5.7)–(29,-2.3);
[thin] (27,-5.7)–(30.75,-2.3);
[thin] (27,-5.7)–(32.5,-2.3);

[thin] (29.75,-10)–(24,-8.3);

[thin] (29.75,-10)–(29,-2.3);
[thin] (29.75,-10)–(30.75,-2.3);

[text width=0.1cm] at (26.5,-7)

[text width=0.1cm] at (29.5,-11)

[text width=0.1cm] at (19.6,2)

[text width=0.1cm] at (23.1,2)

[text width=0.1cm] at (16.7,-1.5)

[text width=0.1cm] at (21,-13)

[text width=0.1cm] at (26.6,2)

[text width=0.1cm] at (27,-13)

[text width=0.1cm] at (29.7,-13)

[thin] (20.25,1.1)–(17.2,-0.7);
[thin] (20.25,1.1)–(20.25,-0.7);
[thin] (20.25,1.1)–(23.75,-0.7);

[thin] (23.75,1.1)–(17.2,-0.7);
[thin] (23.75,1.1)–(20.25,-0.7);
[thin] (23.75,1.1)–(25.5,-0.7);

[thin] (21,-12.3)–(21,-8.3);

[thin] (21,-12.3)–(24,-8.3);
[thin] (21,-12.3)–(27,-8.3);
[thin] (21,-12.3)–(29.75,-10);

[thin] (21,-5.7)–(17.2,-2.3);

[thin] (27,-12.3)–(27,-8.3);
[thin] (29.75,-12.3)–(29.75,-11.5);

[thin] (27,1.1)–(17.2,-0.7);
[thin] (27,1.1)–(32.5,-0.7);
[thin] (27,1.1)–(30.75,-0.7);
[thin] (27,1.1)–(29,-0.7);
[thin] (27,1.1)–(27.25,-0.7);
[thin] (27,1.1)–(25.5,-0.7);
[thin] (27,1.1)–(23.75,-0.7);
[thin] (27,1.1)–(22,-0.7);
[thin] (27,1.1)–(20.25,-0.7);

New pinning terms and relations are formed at the end of each learning epoch. We do not need to replace pinning relations of epochs $0,1,...,n-1$ with the pinning relations derived from the atoms of epoch $n$, instead we can let them accumulate, epoch after epoch. Pinning relations do not grow until becoming unmanageable. One of the reasons why this occurs is that pinning terms and relations do not only get created, they also get discarded. Discarding pinning relations is needed because the set $R_n \cup R_p$ may be inconsistent. We use $R_p$ to refer to all the accumulated pinning relations.

Inconsistencies are detected as explained in Section <ref>. When we try to enforce the set $R_n \cup R_p$ in $M^{*}$ often we find that some negative relations cannot be enforced. We enforce the relations in $M^{*}$ by adding atoms in the dual to discriminate all the (reversed) negative relations, i.e. the relations in the set $R_{n}^{-} \cup R_p$. Once we calculate the transitive closure of the graph of $M^{*}$ we may find that some negative relations do not hold. It doesn't matter how many times we try or how we choose to introduce the discriminating atoms in $M^{*}$ the resulting relations that do not hold are always the same and are always negative. If a relation that belongs to $R_{n}^{-}$ does not hold, then the set $R_{n}$ is inconsistent. In this case, something is wrong with our training set. If the relation that fails belongs to $R_p$ we just discard it deleting its pinning term and associated pinning relations. We can regard $R_{p}$ as a set of hypotheses; some hypotheses are eventually found inconsistent with new data.

Once inconsistent pinning relations have been discarded and we have a consistent set $R_n \cup R_p$ we have a couple of possible strategies. One is enforcing $R_n \cup R_p$ in epoch $n$. The other strategy, the one used in all the experiments of this paper, consists of creating a new set of atoms for $M^{*}$ enforcing only the relations of $R_n$ but with the pinning terms of $R_p$ present in the graph of $M^{*}$. Then we enforce trace constraints for $R_n$ and also for $R_p$ but only for the relations of $R_p$ that happen to hold in $M^{*}$. In different epochs different relations hold and different pinning terms are used. We found this strategy more efficient and computationally lighter than the first.

Pinning relations are all negative and there are good reasons for this. One reason has to do with maximizing algebraic freedom and it is discussed in section Sections <ref> and Theorem <ref>, the second reason is that inconsistent negative relations can be individually detected while inconsistent positive relations cannot be detected so easily. In Theorem <ref> of Appendix <ref> we prove that any positive relation that is entailed by a set of positive and negative relations is also entailed by the positive relations of the set alone. Negative relations do not have positive relations as logical consequences; their consequences are all negative, so by restricting ourselves to negative pinning relations we can detect and isolate inconsistences introduced by the pinning relations as they arise.

Introducing pinning relations to deal with batch learning has other important advantage. Pinning relations found after embedding a batch of order relations $R_{n+1}$ tend to be quite similar to those obtained for the previous batch $R_{n}$, more so the more the algebra has already learned. This means that the number of pinning terms and relations tend to converge to a fixed number with training or grow very slowly. This approach is then clearly superior to one combining all training sets together.

Pinning terms and relations accumulate the knowledge of the training and can be shared with other algebras.

§ ANALYSIS OF SOLUTIONS

§.§ Finding a class definition for the toy problem

So far we have obtained, with 2 positive and 3 negative examples, a model with two atoms. With a few more training examples, two more atoms are obtained. In terms of the constants they are edged to, we can plot these four atoms as

[thick] (-0.25,-5)–(0.75,-5);
[thick] (-0.25,-4)–(0.75,-4);
[thick] (-0.25,-5)–(-0.25,-4);
[thick] (0.75,-5)–(0.75,-4);

[fill=black] (-0.50,-5.25) rectangle (0,-4.75);
[fill=black] (0.50,-5.25) rectangle (1,-4.75);

[thick] (1.5,-5)–(2.5,-5);
[thick] (1.5,-4)–(2.5,-4);
[thick] (1.5,-5)–(1.5,-4);
[thick] (2.5,-5)–(2.5,-4);

[fill=black] (2.25,-4.25) rectangle (2.75,-3.75);
[fill=black] (1.25,-5.25) rectangle (1.75,-4.75);

[thick] (3.25,-5)–(4.25,-5);
[thick] (3.25,-4)–(4.25,-4);
[thick] (3.25,-5)–(3.25,-4);
[thick] (4.25,-5)–(4.25,-4);

[fill=black] (4,-4.25) rectangle (4.5,-3.75);
[fill=black] (3,-4.25) rectangle (3.5,-3.75);

[thick] (5,-5)–(6,-5);
[thick] (5,-4)–(6,-4);
[thick] (5,-5)–(5,-4);
[thick] (6,-5)–(6,-4);

[fill=black] (4.75,-4.25) rectangle (5.25,-3.75);
[fill=black] (5.75,-5.25) rectangle (6.25,-4.75);

where the first two atoms are atoms $\phi_{3}$ and $\phi_{2}$, that we derived in previous sections. Using more examples, trace-invariant reduction and Sparse Crossing the reader can find the entire solution by hand.

The $16$ possible $2 \times 2$ images can be correctly classified into those with a black vertical bar that contain the four atoms and those without a bar that have one or more atoms missing. A $2 \times 2$ image $I$ has the property $v$ of the positive class when its term contains all four atoms. Those images that do not contain a vertical bar have terms that only contain three atoms or less. Describing the four atoms in terms of the constants, that for clarity we have renamed as $c_{ij\textbf{b}}$ for black pixels in row $i$ and column $j$:

\begin{equation}
\begin{aligned}
(v < I) & \Leftrightarrow (c_{11\textbf{b}} < I \vee c_{12\textbf{b}} < I) \wedge (c_{11\textbf{b}} < I \vee c_{22\textbf{b}} < I)  \\
&\wedge \, \, \, (c_{21\textbf{b}} < I \vee c_{12\textbf{b}} < I) \wedge (c_{21\textbf{b}} < I \vee c_{22\textbf{b}} < I),
\label{eq:solution_bar}
\end{aligned}
\end{equation}

we get a first order expression that defines $v$.

Using the distributive law, we can rewrite the solution in Equation (<ref>) as

\begin{equation}
(v < I) \Leftrightarrow (c_{11 \textbf{b}} <I \wedge c_{21 \textbf{b}} <I) \vee (c_{12\textbf{b}} < I \wedge c_{22 \textbf{b}} < I),
\end{equation}

or more compactly as

\begin{align}
\label{eq:imagewithline_small}
(v < I) \Leftrightarrow \vee_{j=1}^{2} \ \wedge_{i=1}^{2} (c_{ij \textbf{b}} < I).
\end{align}

This last expression in Equation (<ref>) says that positive examples have or column 1 or column 2 (or both) with row 1 and row 2 in black, which is the simplest definition of an image including a vertical bar. We have been able to learn and derive from examples a closed expression defining the class of images that contain a vertical bar.

Deriving formal class definitions form examples is an exciting subject but in this paper we are mainly interested in approximate solutions that are sufficient for Machine Learning. To understand the approximate solutions, however, we are going to walk backwards from exact, closed expressions to the atoms. Specifically, we will show that for the vertical bar problem in a grid of size $M \times N$ there is an astronomically large number of suitable approximate solutions with a desired error rate, and that our stochastic learning algorithm only needs to find one.

§.§ Analysis of exact solutions

So far we have analyzed the vertical bar problem only for $ 2 \times 2$ images. In the following we derive the exact solution for the more general case
of $M \times N$ images. We are not going to learn the solution from examples, instead we are going to derive the form of the atoms from the known concept of a vertical bar. This exact solution will be used in the next section to show that, for algebraic learning to find an approximate solution, it needs to find some valid subset of atoms from the exact solution and there are an astronomically large number of valid subsets.

An $M \times N$ image contains a black vertical bar if there is at least one of the $N$ columns in the image for which all $M$ pixels are black. Formally, image $I$ has a vertical line if either column $1$ has all rows in black, or column $2$ or any of the $N$ columns,

\begin{equation}
(v < I) \Leftrightarrow \vee_{j=1}^{N} \wedge_{i=1}^{M} (c_{ij \textbf{b}} < I),
\label{eq:imagewithline0}
\end{equation}

where the dusjunction $\vee$ runs over the columns of the image $I$ and the conjunction $\wedge$ over the rows and $c_{ij \textbf{b}}$ stands for the pixel in row $i$ and column $j$ being in black.

In order to compare Equation (<ref>) with the general form of a solution learned using algebras we are going to start by expressing the partial order $a < b$ affecting any two elements $a$ and $b$ of an atomized algebra in terms of its constants rather than its atoms. We know how to determine if $a < b$ using atoms: $a < b$ if and only if the atoms of $a$ are also atoms of $b$. Just to clarify, we say an atom $\phi$ is in $a$ or is of $a$ or contained in $a$ if it is in the lower segment ${\bf{L}}(a)$ or, equivalently in the graph, if it is edged to $a$, i.e. if $\phi \in {\bf{GL}}(a)$ or, also equivalently, if $\phi < a$.

Element $a$ of an atomized algebra is lower than $b$ (or in $b$) if and only if all the atoms of $a$ are also in $b$,

\begin{equation}
\label{eq:atomic1}
(a<b) \Leftrightarrow \wedge_{\phi \,<\, a} (\phi < b),
\end{equation}

with the conjunction running over all atoms of $a$. An atom $\phi$ is contained in $b$ if any of the constants that contain that atom, $c_{\phi k}$, is in element $b$,

\begin{equation}
\label{eq:atomic2}
(\phi<b) \Leftrightarrow \vee_{k} (c_{\phi k} < b),
\end{equation}

where index $k$ runs along all constants $c_{\phi k}$ that contain atom $\phi$.

Substituting Equation (<ref>) into Equation (<ref>), we can write

\begin{equation}
\label{eq:lineinimage_algebra}
(a<b) \Leftrightarrow \wedge_{\phi \,<\, a}  \vee_{k} (c_{\phi k} < b),
\end{equation}

where we have expressed $a<b$ with the constants of the algebra.

Going back to our problem of vertical bars, we can apply to $v < I$ what we have learned and write

\begin{equation}
\label{eq:imagewithline_algebra}
(v<I) \Leftrightarrow \wedge_{\phi \,<\, v}  \vee_{k} (c_{\phi k} < I).
\end{equation}

where $I$ is a term describing an image, and then compare it with our first expression, Equation (<ref>). This formula has a conjuction followed by a disjunction so we are going to transform Equation (<ref>) to conjunctive normal form (CNF) to match the form of Equation (<ref>).

We first do the transformation for images of size $3 \times 2$ to keep it intuitive. For this size of images, the expression for a vertical bar to be in one of these images in Equation (<ref>) is of the form

\begin{equation}
\begin{aligned}
(v < I) & \Leftrightarrow \vee_{j=1}^{2} \ \wedge_{i=1}^{3} (c_{ij \textbf{b}} < I) \\
&=(c_{11 \textbf{b}<I}\wedge c_{21 \textbf{b}<I}\wedge c_{31 \textbf{b}}<I) \vee c_{12\textbf{b}<I}\wedge c_{22 \textbf{b}<I}\wedge c_{32\textbf{b}}<I).
\end{aligned}
\end{equation}

Using that conjuction and disjuction are distributive:

\begin{equation}
\begin{aligned}
(v < I) &\Leftrightarrow \vee_{j=1}^{2}  \wedge_{i=1}^{3} (c_{ij \textbf{b}} < I) \\
&=(c_{11\textbf{b}} \vee c_{12\textbf{b}}) \wedge (c_{11\textbf{b}} \vee c_{22\textbf{b}}) \wedge (c_{11\textbf{b}} \vee c_{32\textbf{b}}) \\
& \vee \,
(c_{21\textbf{b}} \vee c_{12\textbf{b}}) \wedge (c_{21\textbf{b}} \vee c_{22\textbf{b}}) \wedge (c_{21\textbf{b}} \vee c_{32\textbf{b}}) \\
& \vee \,