# Boolean-Arithmetic Equations: Acquisition and Uses

R Gindullin, Nicolas Beldiceanu, Jovial Cheukam Ngouonou, Rémi Douence, Claude-Guy Quimper

► To cite this version:

R Gindullin, Nicolas Beldiceanu, Jovial Cheukam Ngouonou, Rémi Douence, Claude-Guy Quimper. Boolean-Arithmetic Equations: Acquisition and Uses. CPAIOR 2023: 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, May 2023, Nice, France. pp.378-394, 10.1007/978-3-031-33271-5_25. hal-04460561

HAL Id: hal-04460561

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

Submitted on 15 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Boolean-Arithmetic Equations:
Acquisition and Uses

R. Gindullin*¹,², N. Beldiceanu¹,², J. Cheukam Ngouonou¹,²,⁴,
R. Douence¹,²,³, C.-G. Quimper⁴

IMT Atlantique¹, LS2N², INRIA³, Université Laval⁴

**Abstract.** Motivated by identifying equations to automate the discovery of conjectures about sharp bounds on combinatorial objects, we introduce a CP model to acquire Boolean-arithmetic equations (BAE) from a table providing sharp bounds for various combinations of parameters. Boolean-arithmetic expressions consist of simple arithmetic conditions (SAC) connected by a single commutative operator such as ‘∧’, ‘√’, ‘⊕’ or ‘+’. Each SAC can use up to three variables, two coefficients, and an arithmetic function such as ‘+’, ‘−’, ‘×’, ‘floor’, ‘mod’ or ‘min’. We enhance our CP model in the following way to limit the search space: (i) We break the symmetries linked to multiple instances of similar SACs in the same expression. (ii) We prevent the creation of SAC that could be simplified away. We identify several use cases of our CP model for acquiring BAE and show its applicability for learning sharp bounds for eight types of combinatorial objects as digraphs, forests, and partitions.

**Keywords:** Boolean-arithmetic equation · equation discovery · bounds.

# 1 Introduction

In the context of finding conjectures about combinatorial objects, the relevance of Boolean and BAE has been noted but not fully developed. Larson and Cleemput describe in [21] the use of pure Boolean expressions to represent necessary or sufficient conditions for a graph property, while [8] depicts the application of BAE to express sharp bounds of graph characteristics. While the first work uses a systematic generate and test approach, the second does not describe how such BAE were produced. Our work is motivated by the following observations: (i) we want to go beyond a generate and test approach [21], and investigate how CP can be used to identify a wide range of concise BAE in the context of conjecture acquisition; (ii) while the experimental part of [8] indicates the relevance to use BAE to get sharp bounds for digraphs characteristics, it was still unclear whether this applies to other combinatorial objects. The contribution of the paper is threefold.

1. First, it exhibits a variety of Boolean-arithmetic expressions $f(X_1, X_2, \dots, X_n)$ which occur in practice when looking for sharp bounds.

<footnote>* R. Gindulling is supported by the EU-funded ASSISTANT project no. 101000165.</footnote>
2. Second, it provides CP models for acquiring Boolean arithmetic expressions. The main point of these models is to restrict the search space by breaking symmetries between similar simple arithmetic conditions (SACs) and avoiding generating simplifiable SACs.

3. Finally, it shows that Boolean-arithmetic expressions are not only relevant for expressing bounds for digraphs as mentioned in [8], but also for trees, forests, partitions, and some global constraints.

In Sect. 2, we describe four settings for the practical use of Boolean expressions that we observed in the context of sharp bound acquisition. In Sect. 3, we define the Boolean-arithmetic formulae that we consider throughout this paper. In Sect. 4, we provide a core CP model for learning a BAE that explains an output column of a table from a set of input columns. We show in Sect. 5 various extensions of the core model to restrict the search space of Boolean-arithmetic expressions. We evaluate the core model and its extensions in Sect. 6, discuss related work in Sect. 7, and conclude in Sect. 8.

## 2 The Relevance of Boolean-Arithmetic Equations

To show the expressive power of BAE, let us consider typical situations where they are relevant for acquiring sharp bounds, i.e. an inequality for which the equality holds for at least one example.

1. Using a BAE is a natural option when the codomain of $f(X_1, X_2, \dots, X_n)$ is equal to $\{0, 1\}$ or more generally consists of only two distinct consecutive values $v$ and $v+1$. For instance, let $v, a, os$ and $s$ be the number of vertices, of arcs, of smallest strongly connected components and the size of the smallest strongly connected component of a digraph. As found by the CP model of [8] when $a$ is maximal, we have the relation $os = \lfloor \frac{v}{\max(-s+v, s)} \rfloor$, which is subsumed by the relation $os = 1 + [v = 2 \cdot s]$, where the Boolean expression $[v = 2 \cdot s]$ is used as an integer, i.e. either 0 for false or 1 for true.

2. Even when the number of distinct values $m$ of the codomain of $f(X_1, X_2, \dots, X_n)$ is greater than two values, but still very small, we can use Boolean arithmetic expressions to capture concise formulae. This is done by summing up $m-1$ Boolean-arithmetic conditions as illustrated now: e.g., let $v, a, c_1$ and $c$ be the number of vertices, of arcs, of connected components having more than one vertex and the size of the smallest connected component of a digraph. As found by the CP model in [8], when $a$ is maximal, we have the relation $c_1 = \lfloor \frac{(v+\max(-c+v, c))}{2 \cdot \max(\max(-c+v, c), 2) - \max(-c+v, c) + 1} \rfloor$, which is subsumed by the BAE $c_1 = 2 - ([c=1] + [(v-c) \le 1])$.

3. Quite often, using BAE allows one simplifying formulae with min and max as illustrated now. Let $v, c, c_{23}$ and $\bar{s}$ be the number of vertices, connected components, connected components with two or three vertices where the size of each strongly connected component is equal to 1, and the size of the largest strongly connected component of a digraph: e.g for the graph $\bullet \to \bullet \to \bullet \bullet \to \bullet \bullet \to \bullet$ we have $v = 7, c = 3, c_{23} = 2, \bar{s} = 2$. As discovered by the
CP model of [8], when $c$ is minimal, we have $c_{23} = (v, \bar{s} \le 3? \min(v-1, 1): 0),^1$ which can be replaced by the Boolean relation $c_{23} = [\bar{s} = 1 \land v \in [2, 3]]$.

4. It may occur that a formula can provide an approximate bound with an error of at most 1 on a parameter in $\mathbb{Z}$. Then, a way for getting a sharp bound is to find a Boolean formula which precisely describes the bound discrepancy. For instance, a non-sharp lower bound (with a deviation of at most 1) on the number of connected components $c$ of a digraph $\mathcal{G}$ wrt the number of vertices $v$ of $\mathcal{G}$, the size of the largest connected component $\bar{c}$ of $\mathcal{G}$, and the size of the smallest strongly connected component $\underline{s}$ of $\mathcal{G}$ is given by $\lceil \frac{v}{\bar{c}} \rceil$; but a sharp lower is given by $\lceil \frac{v}{c} \rceil + [(\underline{s} < \text{fmod}(v, \bar{c})) \land (2 \cdot \underline{s} > \bar{c})]$, where $\text{fmod}(x, y)$ is defined by the conditional expression $(x \text{ mod } y = 0 ? y : x \text{ mod } y)$.

The following points are specific to our equation discovery context [29]:

- As our samples are noise-free, we need to acquire formulae that *correctly represent all the samples* we have.

- As our samples correspond to instances of combinatorial objects reaching a sharp bound, this is why we search for equations rather than for inequalities.

- Simple conditions are not translated into a large set of features, which is the case for most decision tree approaches [3,4,19].

- We keep the original columns of the tables, as using one-hot encoding considerably increases the number of columns and affects the interpretability [28].

## 3 Describing Boolean-Arithmetic Expressions

The type of Boolean-Arithmetic expressions we consider is dictated by two opposite objectives. (i) On the one hand, we want to focus on concise expressions involving a limited number of variables and constants. This is motivated by the need to generate interpretable formulae and by the necessity to avoid a combinatorial explosion when searching for such formulae [12]. Consequently, we limit the number of variables and constants, as well as the number of subterms of Boolean-Arithmetic expressions. (ii) On the other hand, we aim at covering a variety of Boolean expressions which occurs in practice. This is done by allowing one to use a variety of arithmetic operators and Boolean functions.

To meet the above objectives, we use the following two-level description:

- First, we consider a Boolean-arithmetic condition (BAC) mentioning *no more than two variables and two constants*, the comparison operators $\le$, $=$, $\ge$, $\in$, $\notin$ and a *variety of arithmetic operators* such as $+$, $-$, $\times$, $\lfloor-\rfloor$, $\lceil-\rceil$, mod, min, max. We currently have 53 elementary arithmetic conditions.

- Second, we build a Boolean-arithmetic term by feeding several arithmetic conditions, or their negation, to a *commutative and associative aggregation operator* such as $+$, $\lor$, $\land$, $\oplus$, eq, card1, voting, where:

* $\oplus$ stands for XOR;

* eq is equal to 1 iff all its conditions are evaluated to the same value;

<footnote n="1">¹ The expression $(cond?x:y)$ denotes $x$ if condition $cond$ holds, $y$ otherwise.</footnote>
* card1 is equal to 1 iff only one of its conditions is evaluated to 1;

* voting is equal to 1 iff the majority of its conditions are evaluated to 1.

The use of a commutative and associative aggregation operator simplifies the interpretability of a formula and reduces the combinatorics, as the order of the BACs within a Boolean-arithmetic term is irrelevant. It allows for a compact representation of some Boolean expressions, that would otherwise be large when expressed in conjunctive or disjunctive normal form without introducing new variables. For instance, the n-ary XOR, i.e. $\oplus_{i=1}^{n} \ell_i$, is represented by a CNF consisting of $2^{n-1}$ clauses, where each clause mentions all literals $\ell_1, \ell_2, \dots, \ell_n$. It also permits the use of the '+' operator in a natural way.

# 4 A Core Model for Acquiring BAE

This section introduces a CP-based core model for acquiring BAE. First, the model relies on soft constraints to represent learned Boolean expressions that mention a restricted number of arithmetic conditions taken from a large set of candidate conditions. Second, the model incorporates symmetry-breaking constraints resulting from the relaxation of arithmetic conditions. Sect. 5 will extend these symmetry-breaking constraints.

## 4.1 Problem Description

Given a two-dimensional table tab[1..r, 1..c] of integer values, consisting of r distinct rows and c distinct columns, where column c is functionally determined by columns 1, 2, ..., c-1, the problem is to come up with a constraint model to acquire an equality constraint of the form

$$ \forall j \in [1, r] : \text{tab}[j, c] = f(\text{tab}[j, 1], \text{tab}[j, 2], \dots, \text{tab}[j, c-1]) \quad (1) $$

i.e. a constraint that is valid for all rows of the table, where f is a Boolean- arithmetic expression mentioning c-1 parameters.

As we want to restrict the complexity of the acquired formulae, the expression f is limited to $n_{AC} \in \{1, 2, 3\}$ conditions chosen from $m = 53$ potential distinct BACs introduced in Sect. 3 (where a few conditions may be duplicated using different constants), and a single commutative and associative aggregation operator g selected from the set $\{\vee, \wedge, \oplus, +, \text{eq}, \text{card1}, \text{voting}\}$. As the acquisition system successively tries the different aggregation operators, we assume from now on that g is fixed. As we search for Boolean-arithmetic expressions by increasing number of BACs, we also assume that $n_{AC}$ is fixed.

Each potential candidate BAC $C_d$ of f (with $d \in [1, m]$) mentioning $\ell_d$ columns of the tab table (with $\ell_d \in [1, 3]$) and $\ell'_d$ coefficients (with $\ell'_d \in [0, 2]$) is represented by the term $C_d \binom{a_{d,1}, \dots, a_{d,\ell_d}}{c_{d,1}, \dots, c_{d,\ell'_d}}$, where:

- the variables $a_{d,1}, \dots, a_{d,\ell_d}$ denote the indices of the distinct columns of the table tab[1..r, 1..c] mentioned by condition $C_d$,
- the variables $c_{d,1}, \dots, c_{d,\ell_d'}$ represents the coefficients used in the arithmetic expression of condition $C_d$.

The problem is to come up with a CP-based model which, given (i) a commutative and associative Boolean operator $g \in \{\vee, \wedge, \oplus, +, \text{eq}, \text{card1}, \text{voting}\}$, and (ii) a fixed number of conditions $n_{AC}$, extracts the subset of relevant conditions for the expression $f$ of Constraint (1), and finds for each used conditions all its parameters, i.e. which columns and which coefficient values it uses.

**Example 1.** On page 8, the left-hand side of Table 2 provides a table tab[1..9, 1..4] from which we acquire the following BAE $x_4 = [(x_1 - x_2) = 2] \lor [x_3 \le 4]$. The acquisition process is now explained in Sect. 4.2.

## 4.2 A CP Core Model

**Notation 1** Given a table tab[1..r, 1..c], the j-th row of tab[1..r, 1..c] is called a negative entry if tab[j, c] = 0, and a positive entry otherwise.

**Selecting the BACs used in f** To each potential BAC $C_d$ (with $d \in [1, m]$) of a Boolean-arithmetic expression $f$, we associate a variable $b_d$ such that:

- $b_d = -1$ means that neither condition $C_d$, nor condition $\neg C_d$ are used in $f$,

- $b_d = 0$ indicates that the condition $\neg C_d$ is used in $f$, i.e. $C_d$ is negated,

- $b_d = 1$ signifies that the condition $C_d$ occurs in $f$.

As $f$ should mention $n_{AC}$ BACs, we set up the following AMONG constraint to specify that $m - n_{AC}$ conditions must be unused:

$$ \text{AMONG} (m - n_{AC}, \langle b_1, b_2, \dots, b_m \rangle, -1) \qquad (2) $$

**Selecting the attributes used in each BAC** For each potential condition $C_d$ ($a_{d,1}, \dots, a_{d,\ell_d}$, $c_{d,1}, \dots, c_{d,\ell_d'}$) (with $d \in [1, m]$) we set all its variables $a_{d,1}, a_{d,2}, \dots, a_{d,\ell_d}$ to 0 when the condition $C_d$ is not used, i.e. when $b_d = -1$. We introduce the variables $a'_{d,1}, a'_{d,2}, \dots, a'_{d,\ell_d}$ corresponding to $a_{d,1} + 1, a_{d,2} + 1, \dots, a_{d,\ell_d} + 1$: we use the offset +1 as these variables will also be used in ELEMENT constraints whose index starts at 1.

For each potential condition $C_d$, its variables $a'_{d,1}, a'_{d,2}, \dots, a'_{d,\ell_d}$ should either be all distinct and greater than or equal to 2, or be all equal to 1. This is expressed by the next GLOBAL\_CARDINALITY (GCC) constraint.

$$ \text{GCC} \left( \begin{array}{c} \langle a'_{d,1}, a'_{d,2}, \dots, a'_{d,\ell_d} \rangle, \\ \langle 1 : \{0, \ell_d\}, 2 : \{0, 1\}, \dots, c : \{0, 1\} \rangle \end{array} \right) \qquad (3) $$

When the condition $C_d$ is unused, i.e. $b_d = -1$, we set all its variables $a'_{d,1}, a'_{d,2}, \dots, a'_{d,\ell_d}$ to 1 to break symmetry, i.e. to avoid enumerating over these variables:

$$ \forall d \in [1, m], \forall k \in [1, \ell_d] : b_d = -1 \Leftrightarrow a'_{d,k} = 1 \qquad (4) $$
To force the use of all attributes from 1 to $c-1$ of the table tab[1..r, 1..c] across all selected conditions, i.e. those conditions $C_d$, (with $d \in [1, m]$) such that $b_d \neq -1$, we set up the following GCC constraint:

$$ \text{GCC} \left( \left\langle \begin{array}{c} a'_{1,1}, a'_{1,2}, \dots, a'_{1,\ell_1} \\ a'_{2,1}, a'_{2,2}, \dots, a'_{2,\ell_2} \\ \vdots \vdots \vdots \vdots \\ a'_{m,1}, a'_{m,2}, \dots, a'_{m,\ell_m} \end{array} \right\rangle, \left\langle \begin{array}{c} 2 : o_2 \\ 3 : o_3 \\ \vdots \\ c : o_c \end{array} \right\rangle \right) \quad \text{with } o_i \in [1, m], \forall i \in [2, c] \quad (5) $$

**Restricting the coefficients of each BAC** When the BAC $C_d \begin{pmatrix} a_{d,1}, \dots, a_{d,\ell_d} \\ c_{d,1}, \dots, c_{d,\ell'_d} \end{pmatrix}$ is used, i.e. $b_d \neq -1$, the coefficient variables $c_{d,1}, \dots, c_{d,\ell'_d}$ denote the coefficients used in the arithmetic expression related to $C_d$. As we look for simple formulae, the initial domain of such variables is initialised to a small interval, e.g. $[-9, +9]$.

Note that we are not interested in acquiring conditions that can be substituted by true or false as they could be simplified away. For some types of conditions this would require additional constraints on the condition's coefficients, e.g. for $C_d(a_{d,1}, c_{d,1}, c_{d,2}) \equiv [(a_{d,1} \bmod c_{d,1}) = c_{d,2}]$ we post the additional constraints $b_d \neq -1 \Rightarrow c_{d,1} \ge 2$ and $b_d \neq -1 \Rightarrow c_{d,2} \in [0, c_{d,1} - 1]$:

- If $c_{d,1} = 1$ then the condition $C_d(a_{d,1}, c_{d,1}, c_{d,2})$ is either always true, when $c_{d,2} = 0$, or always false when $c_{d,2} \neq 0$.

- Otherwise, if $c_{d,1} \ge 2$ and $c_{d,2} \notin [0, c_{d,1} - 1]$ then the condition $C_d(a_{d,1}, c_{d,1}, c_{d,2})$ is always false as $(a_{d,1} \bmod c_{d,1}) \in [0, c_{d,1} - 1]$.

When the condition $C_d$ is unused, we have $b_d = -1 \Rightarrow (c_{d,1} = \dots = c_{d,\ell'_d} = 0)$ to avoid multiple solutions stemming from the coefficients of an unused condition.

How to further restrict the initial domain of the coefficient variables wrt the entries of the table tab[1..r, 1..c] will be explained in Section 5.3.

**Setting row constraints** To evaluate each condition $C_d$ wrt the j-th row of the table tab[1..r, 1..c], we create the variables $v_{d,j,k}$ for the values of its k-th attributes and a variable $b_{d,j}$ for the value of $C_d$. This is described in the next two items:

- For each condition $C_d$ (with $d \in [1, m]$), for each row $j$ (with $j \in [1, r]$), and for each argument $k$ (with $k \in [1, \ell_d]$) of condition $C_d$, we create a variable $v_{d,j,k}$ that gives, either the value of the k-th argument of condition $C_d$ wrt the j-th row of the table tab[1..r, 1..c], or 0 if the condition $C_d$ is unused:

* $\forall d \in [1, m], \forall j \in [1, r], \forall k \in [1, \ell_d]$ : 
    ELEMENT $\begin{pmatrix} a'_{d,k}, \langle 0, \text{tab}[j, 1], \text{tab}[j, 2], \dots, \text{tab}[j, c-1] \rangle, v_{d,j,k} \end{pmatrix}$.

- We also create a 0-1 variable $b_{d,j}$ which will be set to true iff condition $C_d$ holds for the j-th row of the table tab[1..r, 1..c]:

* $\forall d \in [1, m], \forall j \in [1, r] : b_{d,j} \Leftrightarrow C_d(v_{d,j,1}, v_{d,j,2}, \dots, v_{d,j,\ell_d})$.
Now, based on the aggregator *g*, we state a few row constraints for each used condition $C_d$ (with $d \in [1, m]$) and wrt each row of the table tab[1..r, 1..c]. These row constraints are related to the type of aggregator *g* we are using. In this context, we distinguish the following types of aggregators I, II, and III:

I. Aggregators for which (i) positive and negative table entries have distinct row constraints and (ii) a single table entry may determine the Boolean arithmetic expression value. For instance, if *g* is the ‘^’ aggregator then on a positive entry, a condition $C_d$ which is false (with $d \in [1, m]$) falsifies the Boolean arithmetic expression *f*. Aggregators ‘$\vee$’ and ‘^’ belong to this class.

II. Aggregators for which (i) positive and negative table entries have distinct row constraints, and (ii) a single table entry cannot determine the Boolean arithmetic expression value. Aggregator ‘eq’ belongs to this class.

III. Aggregators for which (i) positive and negative table entries have the same row constraint, and (ii) a single table entry cannot determine the Boolean arithmetic expression value. Aggregators ‘+’, ‘$\oplus$’, ‘card1’, and ‘voting’ belong to this class.

Table 1 provides for each class in {I, II, III} of aggregator *g* the corresponding row constraints that determine the value of the Boolean arithmetic expression *f*. As mentioned earlier, for the first two classes, these row constraints depend on whether we have a positive or negative table entry; for the third class, the same constraint applies for both a positive and a negative table entry. We now explain the constraints stated in Table 1 for the first aggregator of each class.

[Case aggregator *g* is ‘$\vee$’]

- For each positive row *j* (with *j* ∈ [1, *r*]), we post the constraint $\vee_{d=1}^m [b_d = b_{d,j}]$ to ensure that *at least one condition is true* so that the disjunction of conditions holds.

- For each condition $C_d$ (with $d \in [1, m]$) and each negative row $j$ (with $j \in [1, r]$), we post the constraint $\text{TABLE}(\langle\langle(b_d, b_{d,j})\rangle\rangle, \langle\langle-1, 0\rangle\rangle, \langle\langle-1, 1\rangle\rangle, \langle\langle 0, 1\rangle\rangle, \langle\langle 1, 0\rangle\rangle)$. When the condition $C_d$ is not used, i.e. $b_d = -1$, there is no restriction on $b_{d,j}$, i.e. $b_{d,j} \in \{0, 1\}$; otherwise, each condition must be falsified, i.e. $b_{d,j} = 1 - b_d$, so that the corresponding disjunction of conditions is not true.

[Case aggregator *g* is ‘eq’]

- For each positive row $j$ (with $j \in [1, r]$), we post the constraint:

$$[\sum_{d=1}^{m} [b_d = b_{d,j}] = n_{AC}] \lor [\sum_{d=1}^{m} [b_d = \neg b_{d,j}] = n_{AC}]$$

enforcing *either that all conditions hold or that all conditions are false*.

- For each negative row $j$ (with $j \in [1, r]$) we post the constraint:

$$[\sum_{d=1}^{m} [b_d = b_{d,j}] < n_{AC}] \land [\sum_{d=1}^{m} [b_d = \neg b_{d,j}] < n_{AC}]$$

imposing that *at least one condition is false and at least one is true*.

[Case aggregator *g* is ‘+’] For each row *j* (with *j* ∈ [1, *r*]), we post the constraint tab[*j*, *c*] = $\sum_{d=1}^{m} [b_d = b_{d,j}]$ to ensure that the appropriate number of conditions are satisfied.
- As row 6 is a negative entry, we post the constraint TABLE `((b_d, b_{d,6}), T)`, with $T = ((-1, 0), (-1, 1), (0, 1), (1, 0))$, for each condition $C_d$ ($d \in \{1, 2, 3\}$). All three constraints hold for the sixth row.

# 5 Enhancing the Core Model

## 5.1 Linking the Number of Conditions, their Arity, and the Number of Attributes

We introduce the following constraints to explicitly restrict the potential combinations of unary, binary and ternary conditions to consider.

**Notation 2** *Within the expression f formed by $n_{AC}$ conditions, let $n_{AC,k}$ denote the number of conditions mentioning $k$ attributes.*

Since we restrict the Boolean-arithmetic expression $f$ to at most three conditions, we state the constraints $n_{AC} = \sum_{k=1}^{3} n_{AC,k}$ and $\sum_{k=1}^{3} k \cdot n_{AC,k} = \sum_{i=2}^{c} o_i$, where $o_i$ is the number of occurrences of value $i$ in the variables $a'_{d,1}, a'_{d,2}, \dots, a'_{d,\ell_d}$, as stated by the GCC constraint (3) of the core model. We now state the lower and upper bounds on the number of distinct attributes $c-1$ appearing in the expression $f$ wrt $n_{AC,k}$ (with $k \in [1, 3]$):

* $c-1 \ge \max_{k=1}^{3} (k \cdot \min(1, n_{AC,k}))$, 
* $c-1 \le \sum_{k=1}^{3} (k \cdot n_{AC,k})$.

## 5.2 Symmetry Breaking

As a formula may involve commutative arithmetic operators whose arguments can be interchanged, and mention several occurrences of the same condition which can be swapped, we show how to restrict the search space for formulae.

**Commutative arithmetic operators** For each BAC $C_d$ ($\begin{pmatrix} a_{d,1}, a_{d,2}, \\ c_{d,1}, \dots, c_{d,\ell'_d} \end{pmatrix}$) (with $d \in [1, m]$) mentioning two attributes $a_{d,1}$ and $a_{d,2}$, as well as a commutative arithmetic operator such as $+$, $\min$, or $\max$, we order its arguments only when the condition is used, by posting a constraint of the form $b_d \ne -1 \Rightarrow a'_{d,1} < a'_{d,2}$ on its variables $a'_{d,1}$ and $a'_{d,2}$.

**Conditions mentioning the same comparison and arithmetic operators** In case a same condition would occur several times in the expression $f$, positively or negatively, or with different attributes, we post symmetry-breaking constraints to prevent generating equivalent subexpressions. We order the list of potential BACs $C_1, C_2, \dots, C_m$ so that conditions that use the same comparison operator $\le$, $=$, $\ge$, $\in$, as well as the same arithmetic operator $+$, $-$, $\times$, $\lfloor-\rfloor$, $\lceil-\rceil$, mod, min, max are located consecutively. For each pair of consecutive conditions $C_d$ ($\begin{pmatrix} a_{d,1}, \dots, a_{d,\ell_d}, \\ c_{d,1}, \dots, c_{d,\ell'_d} \end{pmatrix}$), $C_{d+1}$ ($\begin{pmatrix} a_{d+1,1}, \dots, a_{d+1,\ell_{d+1}}, \\ c_{d+1,1}, \dots, c_{d+1,\ell'_{d+1}} \end{pmatrix}$) (with $d \in [1, m-1]$)
using the same comparison and arithmetic operators, we enforce the following symmetry-breaking constraint.

The idea is to impose a strict lexicographic ordering constraint (SLOC) between the variables of such consecutive conditions $C_d$ and $C_{d+1}$. However, we need to consider the cases where these conditions are unused ($b_d = -1$, $b_{d+1} = -1$), negated ($b_d = 0$, $b_{d+1} = 0$) or positively used ($b_d = 1$, $b_{d+1} = 1$). We use the following idea to adapt the SLOC to our context: a SLOC can be described as a finite automaton whose input alphabet consists of letters that pairwise compare the k-th components of two vectors [6]. We compare the vectors $\vec{U} = (b_d, a'_{d,1}, a'_{d,2}, \dots, a'_{d,\ell_d}) = (u_1, u_2, \dots, u_{\ell_d+1})$ and $\vec{V} = (b_{d+1}, a'_{d+1,1}, a'_{d+1,2}, \dots, a'_{d+1,\ell_{d+1}}) = (v_1, v_2, \dots, v_{\ell_{d+1}})$. Recall from Sect. 4.2 that (i) depending on whether condition $C_d$ is unused, negated or used positively, $b_d$ will be set to $-1$, 0 or 1 respectively, and that (ii) the variables $a'_{d,1}, a'_{d,2}, \dots, a'_{d,\ell_d}$ are all in the range $[2, c]$ as we applied the offset +1. By pairwise comparing the k-th components of vectors $\vec{U}$ and $\vec{V}$ (with $k \in [1, \ell_d + 1]$) we create the following vector $\vec{W} = (w_1, w_2, \dots, w_{\ell_{d+1}})$, where each component is defined by one of the nine letters 0, 1, \dots, 8 described in Table 3.

We then force the components of vector $\vec{W}$ to be accepted by the finite automaton given in Fig. 1. The three accepting states labelled by **n**, **o**, and **t** respectively correspond to the fact that (i) none of the conditions $C_d$, $C_{d+1}$ is used, (ii) only the first condition $C_d$ is used, and (iii) the two conditions $C_d$, $C_{d+1}$ are both used. The outgoing transitions from state $\epsilon$ to states $\mathbf{t} \neq$

<table><caption>**Table 3.** Definition of the input letters of the finite automaton depicted in Part (A) of Fig. 1 used for breaking symmetry between two consecutive conditions</caption><thead><tr><th>Input letter</th><th>Corresponding condition</th><th>Comment</th></tr></thead><tbody><tr><td>w<sub>k</sub> = 0</td><td>u<sub>k</sub> = -1 &amp; v<sub>k</sub> = -1</td><td>Both conditions are unused.</td></tr><tr><td>w<sub>k</sub> = 1</td><td>(u<sub>k</sub> = 0 &amp; v<sub>k</sub> = -1)</td><td>Only one condition is used.</td></tr><tr><td>w<sub>k</sub> = 2</td><td>u<sub>k</sub> = 1 &amp; v<sub>k</sub> = 0</td><td>The 1st condition is used positively, and the negation of the 2nd condition is used.</td></tr><tr><td>w<sub>k</sub> = 3</td><td>u<sub>k</sub> = 0 &amp; v<sub>k</sub> = 0</td><td>The negation of the 1st condition is used, and the negation of the 2nd condition is used.</td></tr><tr><td>w<sub>k</sub> = 4</td><td>u<sub>k</sub> = 1 &amp; v<sub>k</sub> = 1</td><td>k = 1: both conditions are used positively, k > 1: attributes of both conditions are unused.</td></tr><tr><td>w<sub>k</sub> = 5</td><td>u<sub>k</sub> > 1 &amp; v<sub>k</sub> = 1</td><td>u<sub>k</sub> is an attribute of the 1st condition, and v<sub>k</sub> an unused attribute of the 2nd condition, as the 2nd condition is unused.</td></tr><tr><td>w<sub>k</sub> = 6</td><td>u<sub>k</sub> > 1 &amp; v<sub>k</sub> > 1 &amp; u<sub>k</sub> = v<sub>k</sub></td><td>u<sub>k</sub> and v<sub>k</sub> are attributes of the two used conditions, such that u<sub>k</sub> = v<sub>k</sub>.</td></tr><tr><td>w<sub>k</sub> = 7</td><td>u<sub>k</sub> > 1 &amp; v<sub>k</sub> > 1 &amp; u<sub>k</sub> > v<sub>k</sub></td><td>u<sub>k</sub> and v<sub>k</sub> are attributes of the two used conditions, such that u<sub>k</sub> > v<sub>k</sub>.</td></tr><tr><td>w<sub>k</sub> = 8</td><td>u<sub>k</sub> > 1 &amp; v<sub>k</sub> > 1 &amp; u<sub>k</sub> < v<sub>k</sub></td><td>u<sub>k</sub> and v<sub>k</sub> are attributes of the two used conditions, such that u<sub>k</sub> < v<sub>k</sub>.</td></tr></tbody></table>
and $\vec{t}$ enforce that, when using a condition and its negated form, the negated form is located in the second position. The two outgoing transitions of state $\vec{t}$ ensure that the arguments of the first used condition are lexicographically strictly greater than the arguments of the second condition, while the two outgoing transitions of state $\vec{t} \neq$ force the two conditions to not use the same arguments.

## 5.3 Pre-computing the Combinations of Possible Values of the Coefficients of a Condition

Most BACs $C_d \begin{pmatrix} a_{d,1}, \dots, a_{d,\ell_d'} \\ c_{d,1}, \dots, c_{d,\ell_d'} \end{pmatrix}$ can be presented as a comparison of the form $C'_d(P) \diamond c_{d,\ell_d'}$ (with $\diamond \in \{\leq, =, \geq\}$), where $C'_d(P)$ is an arithmetic expression parameterised by $P = \begin{pmatrix} a'_{d,1}, \dots, a'_{d,\ell_d'} \\ c_{d,1}, \dots, c_{d,\ell_d'-1} \end{pmatrix}$. Such BACs in a Boolean formula $f$ must not be equivalent to true or false, as otherwise they could be simplified away from $f$. We also want to avoid generating a condition involving an inequality when an equality would suffice. For this purpose we proceed as follows.

- For each possible combination of values $p$ of parameter $P$ wrt the potential values of $a'_{d,1}, \dots, a'_{d,\ell_d'}$, $c_{d,1}, \dots, c_{d,\ell_d'-1}$, we compute the feasible values of $C'_d(p)$ wrt all the table entries of tab[1..$r$, 1..$c$]. We denote by $V_{d,p}$ such sets.

- Then, depending on the comparison operator $\diamond$ used in condition $C_d$, we derive for each combination of values $p$ of parameter $P$, the set of values of coefficient $c_{d,\ell_d'}$ which does not make condition $C_d$ always true or always false. We denote such sets as $V_{d,p}^{\diamond}$. They are obtained from the sets $V_{d,p}$ in the following way.

• $[\diamond$ is `=']$: when the coefficient $c_{d,\ell_d'}$ is assigned a value outside $V_{d,p}$ the condition $C_d$ would always be false; if the cardinality of $V_{d,p}$ is 1 then

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** (A) Automaton for breaking symmetries between two consecutive conditions $C_d, C_{d+1}$ sharing the same comparison and arithmetic operators, where accepting states are denoted by a double circle; (B) Examples of vectors $\vec{U}, \vec{V}, \vec{W}$ and corresponding used conditions with their arguments (each condition mentions one single attribute).</figcaption></figure>
<table><caption>**Table 4.** Example table for pre-computing the possible values of the coefficients for conditions $C_1$ and $C_2$</caption><thead><tr><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>c</sub></th><th>[x<sub>1</sub> - x<sub>2</sub>]</th><th>[x<sub>2</sub> - x<sub>1</sub>]</th><th>[x<sub>1</sub> mod 3]</th><th>[x<sub>2</sub> mod 3]</th></tr></thead><tbody><tr><td>1</td><td>2</td><td>0</td><td>-1</td><td>1</td><td>1</td><td>2</td></tr><tr><td>2</td><td>1</td><td>0</td><td>1</td><td>-1</td><td>2</td><td>1</td></tr><tr><td>1</td><td>2</td><td>1</td><td>-1</td><td>1</td><td>1</td><td>2</td></tr><tr><td>1</td><td>3</td><td>1</td><td>-2</td><td>2</td><td>1</td><td>0</td></tr><tr><td>1</td><td>4</td><td>1</td><td>-3</td><td>3</td><td>1</td><td>1</td></tr></tbody></table>

$V_{d,p}^{\diamondsuit} = \emptyset$ (i.e. if there is only one value the condition would always be true), otherwise $V_{d,p}^{\diamondsuit} = V_{d,p}$.

* $[\diamondsuit$ is $\leq'$ or $\geq'$]: let $\alpha$ and $\omega$ respectively be the smallest and the largest value of the set $V_{d,p}$; then $V_{d,p}^{\diamondsuit} = V_{d,p} \setminus \{\alpha, \omega\}$. The intuition for $\diamondsuit = \leq'$ is as follows: if we keep $\alpha$ then $\diamondsuit = \leq'$ is equivalent to $\diamondsuit = ='$; if we keep $\omega$ the condition will always be true. For $\geq'$ the intuition is symmetrical.

– We may further reduce the set $V_{d,p}^{\diamondsuit}$ by considering the aggregator $g$. First, for each possible combination of values $p$ of parameter $P$, we compute the feasible values of $C_d'(p)$ wrt all the positive (resp. negative) table entries of tab[1..$r$, 1..$c$]. We denote by $V_{d,p}^{\text{pos}}$ (resp. $V_{d,p}^{\text{neg}}$) such sets. From these sets, we compute the further restricted set $V_{d,p}^{\diamondsuit,g}$ as follows:

* $[g \text{ is } \wedge\wedge]:$ if $\diamondsuit$ is $==$' then $V_{d,p}^{\diamondsuit,g} = V_{d,p}^{\text{pos}}$ else $V_{d,p}^{\diamondsuit,g} = V_{d,p}^{\text{pos}} \cap V_{d,p}^{\diamondsuit}$,

* $[g \in \{\wedge, \wedge, +\}]:$ $V_{d,p}^{\diamondsuit,g} = V_{d,p}^{\diamondsuit} \setminus V_{d,p}^{\text{neg}}$,

* $[g \notin \{\wedge, \wedge, \vee, \vee, +\}]: V_{d,p}^{\diamondsuit,g} = V_{d,p}^{\diamondsuit}$.

– Finally, we set up the table constraint TABLE $\left( \left\langle \begin{array}{c} a'_{d,1}, \dots, a'_{d,\ell_d} \\ c_{d,1}, \dots, c_{d,\ell'_d} \end{array} \right\rangle, S \right)$ where $S$ corresponds to the union of cartesian products $\cup_{p \in P} (p \times V_{d,p}^{\diamondsuit,g})$.

*Example 3.* To illustrate the process, consider Table 4. There are two input columns 1 and 2 and the output column $c$. Consider the two conditions $C_1 = [a_{1,1} - a_{1,2} = c_{1,1}]$ and $C_2 = [a_{2,1} \text{ mod } c_{2,1} \geq c_{2,2}]$.

* For $C_1$ we have only two options for $p = \{a_{1,1}, a_{1,2}\}$, namely:

1) $p = \{1,2\}$: $\begin{cases} V_{1,p} = \{-3,-2,-1,1\}, & V_{1,p}^{\wedge} = V_{1,p}, \\ V_{1,p}^{\wedge,\wedge} = \{-3,-2,-1\}, & V_{1,p}^{\wedge,\vee} = V_{1,p}^{\wedge} \setminus \{-1,1\} = \{-3,-2\}. \end{cases}$

2) $p = \{2,1\}$: $\begin{cases} V_{1,p} = \{-1,1,2,3\}, & V_{1,p}^{\wedge} = V_{1,p}, \\ V_{1,p}^{\wedge,\wedge} = \{1,2,3\}, & V_{1,p}^{\wedge,\vee} = V_{1,p}^{\wedge} \setminus \{-1,1\} = \{2,3\}. \end{cases}$

* For $C_2$ we need to enumerate on $c_{2,1}$. Wlog, we only consider the case $c_{2,1} = 3$. In this context, the options for $p = \{a_{2,1}, c_{2,1}\}$ are:

1) $p = \{1,3\}$: $V_{2,p} = \{1,2\}, \alpha = 1, \omega = 2, V_{2,p}^{\geq} = V_{2,p} \setminus \{\alpha, \omega\} = \emptyset$, i.e. this set of options for this condition is not considered any further.

2) $p = \{2,3\}$: $\begin{cases} V_{2,p} = \{0,1,2\}, \alpha = 0, \omega = 2, V_{1,p}^{\geq} = V_{2,p} \setminus \{\alpha, \omega\} = \{1\}, \\ V_{2,p}^{\text{pos}} = \{1\}, V_{2,p}^{\text{neg}} = \{1,2\}, \\ V_{2,p}^{\geq, \wedge} = V_{2,p}^{\text{pos}} \cap V_{2,p}^{\geq} = \{1\}, V_{2,p}^{\geq, \vee} = V_{2,p}^{\geq} \setminus V_{2,p}^{\text{neg}} = \emptyset. \end{cases}$
# 6 Evaluation

The CP core model introduced in Sect. 4 and its extension described in Sect. 5 were evaluated in the context of the search of conjectures on sharp bounds on characteristics of several combinatorial objects, which we now describe.

- **digraph (without isolated vertex):** a set of vertices $\mathcal{V}$ and a set of ordered pairs of vertices $\mathcal{A}$ with the restriction that each vertex of $\mathcal{V}$ occurs in at least one pair of $\mathcal{A}$ [5].

- **rooted tree:** a connected acyclic undirected graph where a vertex is designed as the “root” of the tree [18].

- **rooted forest:** a disjoint union of rooted trees [18]; we also consider a variant, **rooted forest2**, where all rooted trees have at least two vertices.

- **partition:** a partition of a set $\mathcal{S}$ is a collection of possibly empty subsets of $\mathcal{S}$ such that every element of $\mathcal{S}$ is in exactly one of the subsets of the collection. The use of a partition was motivated by the fact that a partition can be interpreted as a solution to the conjunction of the NVALUE (i.e. the number of partition subsets, see [26]) and the BALANCE (i.e. the difference between the cardinalities of the largest and smallest subsets of the partition, see [7]) constraints. Motivated by the extension of the BALANCE constraint, i.e. ALL_BALANCE [9], we also consider a version of partition named **partition0** where all subsets of $\mathcal{S}$ are non-empty.

- **stretch:** a solution of a stretch constraint on 0-1 variables, where a subsequence of 1 immediately preceded and followed by a 0 is called a *stretch* [27]; we also consider the variant named **cyclic stretch** where, when the sequence begins and terminates by 1, those two 1 belong to the same stretch.

Table 5 shows for each combinatorial object some characteristics we consider, and some conjectures found using the Boolean model described in this paper. Those conjectures are equalities which express (i) either the value of a characteristic when another characteristic is reaching its sharp bound, (ii) either a sharp bound formulated wrt other characteristics [8]. We evaluate the CP models of Sect. 4 and 5 wrt to the following two aspects:

1. The computing time spent by the core model of Sect. 4 (i.e. C. Model) and by its enhanced version of Sect. 5 (i.e. E. Model) wrt (i) the type of aggregator used in a BAE, and wrt (ii) the kind of combinatorial object. For this aspect, we test 3706 examples of acquired BAE on a MacBookPro with a 2.6 GHz Core i7 and 16Gb of memory using SICStus 4.6.0. Table 6 shows that the E. model acquires a BAE with, on average, 73% less time than the C. Model. Additional tests showed that using just the constraints from Sect. 5.1 increases the speed of the C. Model by ≈ 5%, just the constraints from Sect. 5.2 - by ≈ 63% and just the constraints from Sect. 5.3 - by ≈ 48%.

2. Using the enhanced model together with the model acquiring polynomial of [8] (i.e. the EP. Model), Table 7 gives (i) the number of Boolean formulae found, i.e. 642 (sum of second columns), replacing a formula with a polynomial, and (ii) the number of new Boolean formulae, i.e. 56 (sum of
<table><caption>**Table 5.** Examples of characteristics (char.) of combinatorial objects and corresponding conjectures: (i) *c*, *s*, *oc*, *c* and *s*: number of connected components (cc), strongly connected components (scc), connected components with at least two vertices, size of the smallest cc and size of the largest scc of a digraph; (ii) *c*₀: denote 0 if all the cc have same maximal size, and *c* otherwise, for a digraph; (iii) *v* and *f*: number of vertices and leaves in a rooted tree; (iv) *d*: largest degree of a parent node in a rooted tree or a rooted forest; (v) *p* and *t*: minimum depth and size of the smallest tree in a rooted forest; (vi) *n*, *nval*, and *m*: number of elements, number of subsets, and cardinality of the smallest subset in a partition; (vii) *sr*, *dr*, and *dm*: difference between the number of elements of the largest and smallest stretches, difference between the maximum and minimum distance of consecutive stretches, and minimum distance between consecutive stretches in stretch; (viii) *n*, *ng*, and *osc*: number of elements, total number of stretches, and number of stretches which have more than one element when the number of element of the largest stretch is maximal in cyclic stretch.</caption><thead><tr><th>Combinatorial object</th><th>Number of char.</th><th>Some of the used char.</th><th>Examples of discovered conjectures</th></tr></thead><tbody><tr><td>digraph</td><td>20</td><td>c, c, s, oc</td><td>c = 1 + [¬(s ≤ c ∧ oc ≤ 1)]</td></tr><tr><td>digraph</td><td>20</td><td>c<sub>0</sub>, c, s, s&#773;</td><td>c<sub>0</sub> = [¬voting(c = s, c = 1, min(c, s&#773;) = 1)]</td></tr><tr><td>rooted tree</td><td>6</td><td>d, v, f</td><td>d&#773; = (v = f ∨ v = 1 ? 0 : f)</td></tr><tr><td>rooted forest</td><td>11</td><td>p, d, t</td><td>d&#773; = 2 - ([p = 0] + [(t - p) = 1])</td></tr><tr><td>partition</td><td>14</td><td>n, nval, m&#773;</td><td>nval = 1 + [2 · m&#773; ≤ n]</td></tr><tr><td>stretch</td><td>26</td><td>sr, dr, dm&#773;</td><td>dm&#773; = [(sr, dr) ≥ 1]</td></tr><tr><td>cyclic stretch</td><td>26</td><td>osc, n, ng</td><td>osc = [¬card1(n = 2 · ng, n · ng = 3, n · ng ≤ 3)]</td></tr></tbody></table>

<table><caption>**Table 6.** Computing time for the Core and the Enhanced models wrt aggregators (left side) and combinatorial objects (right side)</caption><thead><tr><th rowspan="2">g</th><th rowspan="2">n<sub>AC</sub></th><th rowspan="2">Number of conjectures</th><th colspan="2">Average time per conjecture</th><th rowspan="2">Combinatorial object</th><th rowspan="2">Number of conjectures</th><th colspan="2">Average time per conjecture</th></tr><tr><th>C. Model</th><th>E. Model</th><th>C. Model</th><th>E. Model</th></tr></thead><tbody><tr><td>∧</td><td>1</td><td>2311</td><td>0.36s</td><td>0.35s</td><td>digraph</td><td>546</td><td>43s</td><td>10s</td></tr><tr><td>∧</td><td>2</td><td>341</td><td>25.5s</td><td>11s</td><td>rooted tree</td><td>56</td><td>1.5s</td><td>1s</td></tr><tr><td>∧</td><td>3</td><td>5</td><td>2591s</td><td>542s</td><td>rooted forest</td><td>229</td><td>3.4s</td><td>1.3s</td></tr><tr><td>∨</td><td>2</td><td>190</td><td>18.9s</td><td>6.1s</td><td>rooted forest<sub>2</sub></td><td>586</td><td>18.2s</td><td>5.9s</td></tr><tr><td>∨</td><td>3</td><td>1</td><td>3062s</td><td>292s</td><td>partition</td><td>24</td><td>2.7s</td><td>1.7s</td></tr><tr><td>eq</td><td>2</td><td>143</td><td>35.7s</td><td>14.7s</td><td>partition<sub>0</sub></td><td>24</td><td>0.8s</td><td>0.5s</td></tr><tr><td>eq</td><td>3</td><td>47</td><td>309s</td><td>50s</td><td>stretch</td><td>1059</td><td>10s</td><td>2.7s</td></tr><tr><td>+</td><td>2</td><td>662</td><td>2s</td><td>1.3s</td><td>cyclic stretch</td><td>1182</td><td>6.4s</td><td>1.8s</td></tr><tr><td>card1</td><td>3</td><td>2</td><td>1003s</td><td>27.5s</td><td></td><td></td><td></td><td></td></tr><tr><td>voting</td><td>3</td><td>4</td><td>345s</td><td>66s</td><td></td><td></td><td></td><td></td></tr></tbody><tfoot><tr><td colspan="4"></td><td></td><td>Total</td><td>3706</td><td>14.4h</td><td>3.9h</td></tr></tfoot></table>

third columns) discovered compared to the model described in [8], which only looked for formulae with polynomials and arithmetic functions involving two polynomials (i.e. the P. Model).

# 7 Related Work

Learning purely Boolean expressions from data is widely reported in the literature. A significant number of papers explore the acquisition of relevant features, often called the “relevant features problem” (RFP). Blum formalises the RFP
in [10], and provides a survey of various algorithms in [11]. The RFP can be applied to features that are Boolean, integer or continuous, each of which requires its own approach [15, chapter 1.2]. Some of the works focusing on purely Boolean RFP are described in [25,23,13]. In [24], Mutlu and Oghaz provide a taxonomy of Boolean and non-Boolean feature extraction techniques applied to graphs. Other works present the acquisition of Boolean expressions as a part of the Boolean rules extraction process for classification problems using SAT [31] or neural networks [22]. Lastly, there are papers [16,14] focusing on the construction and the simplification of Boolean functions. The acquisition of Boolean-arithmetic expressions is often used in the context of classification problems. Random forest [17], decision trees [3,4,19], Bayesian rule lists [30], fuzzy association rules [2] and rough sets [20] approaches are used. Most of the work considers the acquisition of relatively simple Boolean-arithmetic expressions of the type “attribute has a value of”. The SEEN system [19] extracts more complex Boolean-arithmetic expressions that contain the +, × and / arithmetic operators: it calls such domain “logical-arithmetic expression mining”.

Beyond the domain of Boolean formulae, synthesising formulae from data [1] mostly relies on a generate and test approach to produce candidate formulae of increasing complexity for a fixed grammar. In our context, applying techniques that minimise an error function produces complicated formulae that are not verified wrt all input data. In [8] we compared our approach to methods used for symbolic regression such as GPlearn and ffx: GPlearn generally found no formulae, while ffx discovered formulae with a large number of terms.

## 8 Conclusion

The paper presents a CP model for learning BAE that can cope with a variety of expressions involving the most common Boolean aggregators and arithmetic operators. In the context of sharp bound acquisition, this complements the model introduced in [8] for learning equations whose right-hand sides are polynomials. The model is relevant not only in the context of digraphs, but also for other combinatorial objects such as rooted trees or partitions.

<table><caption>**Table 7.** Contribution of the EP. Model that both acquires Boolean formulae (BF) and polynomials compared to searching only formulae with polynomials with the P. Model</caption><thead><tr><th rowspan="2">Combinatorial object</th><th colspan="3">Number of (BF) which are:</th></tr><tr><th>found</th><th>replacing polynomials</th><th>new</th></tr></thead><tbody><tr><td>digraph</td><td>164</td><td>118</td><td>46</td></tr><tr><td>rooted tree</td><td>26</td><td>26</td><td>0</td></tr><tr><td>rooted forest</td><td>91</td><td>86</td><td>5</td></tr><tr><td>rooted forest2</td><td>149</td><td>145</td><td>4</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">Combinatorial object</th><th colspan="3">Number of (BF) which are:</th></tr><tr><th>found</th><th>replacing polynomials</th><th>new</th></tr></thead><tbody><tr><td>partition</td><td>20</td><td>20</td><td>0</td></tr><tr><td>partition0</td><td>10</td><td>10</td><td>0</td></tr><tr><td>stretch</td><td>93</td><td>93</td><td>0</td></tr><tr><td>cyclic stretch</td><td>145</td><td>144</td><td>1</td></tr></tbody></table>
References

1. Alur, R., Singh, R., Fisman, D., Solar-Lezama, A.: Search-based program synthesis. Commun. ACM **61**(12), 84–93 (2018). https://doi.org/10.1145/3208071, https://doi.org/10.1145/3208071

2. Au, W.H., Chan, K.C.: Mining fuzzy association rules in a bank-account database. IEEE Transactions on Fuzzy Systems **11**(2), 238–248 (2003)

3. Aung, M.H., Lisboa, P., Etchells, T.A., Testa, A.C., Calster, B.V., Huffel, S.V., Valentin, L., Timmerman, D.: Comparing analytical decision support models through boolean rule extraction: A case study of ovarian tumour malignancy. In: International Symposium on Neural Networks. pp. 1177–1186. Springer (2007)

4. Barbareschi, M., Barone, S., Mazzocca, N.: Advancing synthesis of decision tree-based multiple classifier systems: an approximate computing case study. Knowledge and Information Systems **63**(6), 1577–1596 (2021)

5. Beldiceanu, N.: Global constraints as graph properties on a structured network of elementary constraints of the same type. In: Dechter, R. (ed.) Principles and Practice of Constraint Programming - CP 2000, 6th International Conference, Singapore, September 18-21, 2000, Proceedings. Lecture Notes in Computer Science, vol. 1894, pp. 52–66. Springer (2000). https://doi.org/10.1007/3-540-45349-0_6, https://doi.org/10.1007/3-540-45349-0_6

6. Beldiceanu, N., Carlsson, M., Petit, T.: Deriving filtering algorithms from constraint checkers. In: Wallace, M. (ed.) Principles and Practice of Constraint Programming - CP 2004, 10th International Conference, CP 2004, Toronto, Canada, September 27 - October 1, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3258, pp. 107–122. Springer (2004). https://doi.org/10.1007/978-3-540-30201-8_11, https://doi.org/10.1007/978-3-540-30201-8_11

7. Beldiceanu, N., Carlsson, M., Rampon, J.X.: Global Constraint Catalog, 2nd Edition (revision a). Tech. Rep. T2012-03, Swedish Institute of Computer Science (2012), available at http://ri.diva-portal.org/smash/get/diva2:1043063/FULLTEXT01.pdf

8. Beldiceanu, N., Cheukam-Ngouonou, J., Douence, R., Gindullin, R., Quimper, C.G.: Acquiring maps of interrelated conjectures on sharp bounds. In: 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2022)

9. Bessière, C., Hebrard, E., Katsirelos, G., Kızıltan, Z., Picard-Cantin, É., Quimper, C.G., Walsh, T.: The balance constraint family. In: O’Sullivan, B. (ed.) Principles and Practice of Constraint Programming. pp. 174–189. Springer International Publishing, Cham (2014)

10. Blum, A.: Relevant examples and relevant features: Thoughts from computational learning theory. In: AAAI Fall Symposium on ‘Relevance. vol. 5, p. 1 (1994)

11. Blum, A.L., Langley, P.: Selection of relevant features and examples in machine learning. Artificial intelligence **97**(1-2), 245–271 (1997)

12. Brence, J., Todorovski, L., Džeroski, S.: Probabilistic grammars for equation discovery. Knowledge-Based Systems **224** (2021), https://doi.org/10.1016/j.knosys.2021.107077

13. Forman, G., Kirshenbaum, E.: Extremely fast text feature extraction for classification and indexing. In: Proceedings of the 17th ACM conference on Information and knowledge management. pp. 1221–1230 (2008)

14. Golia, P., Slivovsky, F., Roy, S., Meel, K.S.: Engineering an efficient boolean functional synthesis engine. In: 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD). pp. 1–9. IEEE (2021)
15. Guyon, I., Elisseeff, A.: An introduction to feature extraction. In: Feature extraction, pp. 1–25. Springer (2006)

16. Jakobovic, D., Picek, S., Martins, M.S., Wagner, M.: Toward more efficient heuristic construction of boolean functions. Applied Soft Computing **107**, 107327 (2021)

17. Jun, S., Lee, S., Chun, H.: Learning dispatching rules using random forest in flexible job shop scheduling problems. International Journal of Production Research **57**(10), 3290–3310 (2019)

18. Knuth, D.: Art of Computer Programming, Volume 4, Generating All Trees, pp. 461–462. Addison-Wesley (2006)

19. Kosman, E., Kolchinsky, I., Schuster, A.: Mining logical arithmetic expressions from proper representations. In: Proceedings of the 2022 SIAM International Conference on Data Mining (SDM). pp. 621–629. SIAM (2022)

20. Lambert-Torres, G.: Application of rough sets in power system control center data mining. In: 2002 IEEE Power Engineering Society Winter Meeting. Conference Proceedings (Cat. No. 02CH37309). vol. 1, pp. 627–631. IEEE (2002)

21. Larson, C.E., Van Cleemput, N.: Automated conjecturing iii. Annals of Mathematics and Artificial Intelligence **81**(3), 315–327 (2017)

22. Mereani, F., Howe, J.M.: Exact and approximate rule extraction from neural networks with boolean features. In: Proceedings of the 11th International Joint Conference on Computational Intelligence. pp. 424–433. SCITEPRESS (2019)

23. Mossel, E., O'Donnell, R., Servedio, R.A.: Learning functions of k relevant variables. Journal of Computer and System Sciences **69**(3), 421–434 (2004)

24. Mutlu, E.C., Oghaz, T.A.: Review on graph feature learning and feature extraction techniques for link prediction. arXiv preprint arXiv:1901.03425 (2019)

25. Nguifo, E.M., Njiwoua, P.: Using lattice-based framework as a tool for feature extraction. In: Feature Extraction, Construction and Selection, pp. 205–218. Springer (1998)

26. Pachet, F., Roy, P.: Automatic generation of music programs. In: Jaffar, J. (ed.) Principles and Practice of Constraint Programming - CP'99, 5th International Conference, Alexandria, Virginia, USA, October 11-14, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1713, pp. 331–345. Springer (1999). https://doi.org/10.1007/978-3-540-48085-3_24, https://doi.org/10.1007/978-3-540-48085-3_24

27. Pesant, G.: A filtering algorithm for the stretch constraint. In: Walsh, T. (ed.) Principles and Practice of Constraint Programming — CP 2001. pp. 183–195. Springer Berlin Heidelberg, Berlin, Heidelberg (2001)

28. Schelldorfer, J., Wuthrich, M.V.: Nesting classical actuarial models into neural networks. Available at SSRN 3320525 (2019)

29. Todorovski, L.: Equation discovery. In: Sammut, C., Webb, G.I. (eds.) Encyclopedia of Machine Learning, pp. 327–330. Springer US, Boston, MA (2010)

30. Yang, H., Rudin, C., Seltzer, M.: Scalable bayesian rule lists. In: International conference on machine learning. pp. 3921–3930. PMLR (2017)

31. Yu, J., Ignatiev, A., Stuckey, P.J., Le Bodic, P.: Computing optimal decision sets with sat. In: International Conference on Principles and Practice of Constraint Programming. pp. 952–970. Springer (2020)