R Gindullin

N Beldiceanu

J Cheukam Ngouonou

R Douence

C.-G Quimper

Boolean-Arithmetic Equations: Acquisition and Uses

Keywords: Boolean-arithmetic equation, equation discovery, bounds

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.

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 [START_REF] Larson | Automated conjecturing iii[END_REF] the use of pure Boolean expressions to represent necessary or sufficient conditions for a graph property, while [START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF] 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 [START_REF] Larson | Automated conjecturing iii[END_REF], 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 [START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF] 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 , . . . , X n ) which occur in practice when looking for sharp bounds.

⋆ R. Gindulling is supported by the EU-funded ASSISTANT project no. 101000165.

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 [START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF], 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. [START_REF] Barbareschi | Advancing synthesis of decision treebased multiple classifier systems: an approximate computing case study[END_REF], 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.

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 , . . . , 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 [START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF] when a is maximal, we have the relation os = ⌊ v max(-s+v,s) ⌋, which is subsumed by the relation os = 1 + [v = 2 • s], where the Boolean expression [v = 2 • 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 , . . . , 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 [START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF], when a is maximal, we have the relation

c 1 = ⌊ (v+max(-c+v,c)) (2•max(max(-c+v,c),2)-max(-c+v,c)+1) ⌋, which is subsumed by the BAE c 1 = 2 -([c = 1] + [(v -c) ≤ 1]).
= [s = 1 ∧ v ∈ [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 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 G wrt the number of vertices v of G, the size of the largest connected component c of G, and the size of the smallest strongly connected component s of G is given by ⌈ v c ⌉; but a sharp lower is given by

⌈ v c ⌉ + [(s < fmod(v, c)) ∧ (2 • s > c)],
where fmod(x, y) is defined by the conditional expression (x mod y = 0 ? y : x mod y).

The following points are specific to our equation discovery context [START_REF] Todorovski | Equation discovery[END_REF]:

-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 [START_REF] Aung | Comparing analytical decision support models through boolean rule extraction: A case study of ovarian tumour malignancy[END_REF][START_REF] Barbareschi | Advancing synthesis of decision treebased multiple classifier systems: an approximate computing case study[END_REF][START_REF] Kosman | Mining logical arithmetic expressions from proper representations[END_REF]. -We keep the original columns of the tables, as using one-hot encoding considerably increases the number of columns and affects the interpretability [START_REF] Schelldorfer | Nesting classical actuarial models into neural networks[END_REF].

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 [START_REF] Brence | Probabilistic grammars for equation discovery[END_REF]. 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 ≤, =, ≥, ∈, / ∈ and a variety of arithmetic operators such as +, -, ×, ⌊ ⌋, ⌈ ⌉, 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 +, ∨, ∧, ⊕, eq, card1, voting, where:

• ⊕ stands for xor;

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

• 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. ⊕ n i=1 ℓ i , is represented by a CNF consisting of 2 n-1 clauses, where each clause mentions all literals ℓ 1 , ℓ 2 , . . . , ℓ n . It also permits the use of the '+' operator in a natural way.

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.

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

∀j ∈ [1, r] : tab[j, c] = f (tab[j, 1], tab[j, 2], . . . , tab[j, c -1]) (1)
i.e. a constraint that is valid for all rows of the table, where f is a Booleanarithmetic expression mentioning c -1 parameters.

As we want to restrict the complexity of the acquired formulae, the expression f is limited to n AC ∈ {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 {∨, ∧, ⊕, +, eq, card1, 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 The problem is to come up with a CP-based model which, given (i ) a commutative and associative Boolean operator g ∈ {∨, ∧, ⊕, +, eq, card1, 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] ∨ [x 3 ≤ 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 ∈ [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 ¬C d are used in f , • b d = 0 indicates that the condition ¬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:

among (m -n AC , ⟨b 1 , b 2 , . . . , b m ⟩, -1) (2)
Selecting the attributes used in each BAC For each potential condition

C d a d,1 , . . . , a d,ℓ d , c d,1 , . . . , c d,ℓ ′ d (with d ∈ [1, m]) we set all its variables a d,1 , a d,2 , . . . , a d,ℓ 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 , . . . , a ′ d,ℓ d corresponding to a d,1 + 1, a d,2 + 1, . . . , a d,ℓ 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 , . . . , a ′ d,ℓ 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.

gcc a ′ d,1 , a ′ d,2 , . . . , a ′ d,ℓ d , ⟨1 : {0, ℓ d }, 2 : {0, 1}, . . . , c : {0, 1}⟩ (3)
When the condition C d is unused, i.e. b d = -1, we set all its variables a ′ d,1 , a ′ d,2 , . . . , a ′ d,ℓ d to 1 to break symmetry, i.e. to avoid enumerating over these variables:

∀d ∈ [1, m], ∀k ∈ [1, ℓ d ] : b d = -1 ⇔ a ′ d,k = 1 (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 ∈ [1, m]) such that b d ̸ = -1, we set up the following gcc constraint:

gcc     a ′ 1,1 , a ′ 1,2 , . . . , a ′ 1,ℓ1 , a ′ 2,1 , a ′ 2,2 , . . . , a ′ 2,ℓ2 , . . . . . . . . . . . . . . . . . . . . a ′ m,1 , a ′ m,2 , . . . , a ′ m,ℓm ,
2 : o 2 , 3 : o 3 , . . . . . c : o c     with o i ∈ [1, m], ∀i ∈ [2, c] (5)
Restricting the coefficients of each BAC When the BAC

C d a d,1 , . . . , a d,ℓ d , c d,1 , . . . , c d,ℓ ′ d is used, i.e. b d ̸ = -1, the coefficient variables c d,1 , . . . , c d,ℓ ′ 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 ) ≡ [(a d,1 mod c d,1 ) = c d,2 ] we post the additional constraints b d ̸ = -1 ⇒ c d,1 ≥ 2 and b d ̸ = -1 ⇒ c d,2 ∈ [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 ̸ = 0. -Otherwise, if c d,1 ≥ 2 and c d,2 / ∈ [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 mod c d,1 ) ∈ [0, c d,1 -1]. When the condition C d is unused, we have b d = -1 ⇒ (c d,1 = • • • = c d,ℓ ′ 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 ∈ [1, m]), for each row j (with j ∈ [1, r]),
• ∀d ∈ [1, m], ∀j ∈ [1, r], ∀k ∈ [1, ℓ d ] : element a ′ d,k , ⟨0, tab[j, 1], tab[j, 2], . . . , tab[j, c -1]⟩ , v d,j,k .
-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]: )⟩, ⟨(-1, 0), (-1, 1), (0, 1), (1, 0)⟩).

• ∀d ∈ [1, m], ∀j ∈ [1, r] : b d,j ⇔ C d (v d,j,1 , v d,
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 ∈ {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 ∈ [1, r]), we post the constraint:

[ m d=1 [b d = b d,j ] = n AC ] ∨ [ m d=1 [b d = ¬b d,j ] = n AC ]
enforcing either that all conditions hold or that all conditions are false.

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

[ m d=1 [b d = b d,j ] < n AC ] ∧ [ m d=1 [b d = ¬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 ∈ table ⟨(bd, bd,j)⟩, (-1, 0), (-1, 1), ( 0, 1), ( 1, 0)

'∧' table ⟨(bd, bd,j)⟩, (-1, 0), (-1, 1), ( 0, 0), ( 1, 1)

∨ m d=1 [b d = ¬b d,j ] II 'eq' m d=1 [b d = b d,j ] = nAC, m d=1 [b d = ¬b d,j ] = nAC m d=1 [b d = b d,j ] < nAC, m d=1 [b d = ¬b d,j ] < nAC III '+' tab[j, c] = m d=1 [b d = b d,j ] '⊕' tab[j, c] = ( m d=1 [b d = b d,j ]) mod 2 'card1' tab[j, c] = [( m d=1 [b d = b d,j ]) = 1] 'voting' tab[j, c] = [2 • ( m d=1 [b d = b d,j ]) > nAC]
j table tab C1 = [(x1 -x2) = 2] C2 = [x3 ≤ 4] C3 = [x k 1 = x k 2 ] row constraint satisfaction x1x2x3x4 b1=1a ′ 1,1 =2 a ′ 1,2 =3 b2=1 a ′ 2,1 =4 b3=-1a ′ 3,1 =1a ′ 3,2 =1
b1,j v1,j,1 v1,j,2 b2,j v2,j,1 b3,j v3,j,1 v3,j,2 positive entries

= [(x 1 -x 2 ) = 2] ∨ [x 3 ≤ 4] from the table tab[1.
.9, 1..4]: it provides the main variables introduced by the core model. First, note that only conditions C 1 and C 2 are selected, as b 3 = -1. For the first positive entry (i.e. j = 1) and the first negative entry (i.e. j = 6), we now show that the corresponding row constraints described in Table 1 are true:

-As row 1 is a positive entry, we post the constraint

[b 1 = b 1,1 ] ∨ [b 2 = b 2,1 ] ∨ [b 3 = b 3,1 ] which is true as b 1 = b 1,1 holds.
-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 ∈ {1, 2, 3}). All three constraints hold for the sixth row.

5 Enhancing the Core Model 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 =

• c -1 ≥ max 3 k=1 (k • min(1, n AC,k )), • c -1 ≤ 3 k=1 (k • n AC,k ).

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 a d,1 , a d,2 , c d,1 , . . . , c d,ℓ ′ d (with d ∈ [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 ̸ = -1 ⇒ 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 , . . . , C m so that conditions that use the same comparison operator ≤, =, ≥, ∈, as well as the same arithmetic operator +, -, ×, ⌊ ⌋, ⌈ ⌉, mod, min, max are located consecutively. ). 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

- → U = (b d , a ′ d,1 , a ′ d,2 , . . . , a ′ d,ℓ d ) = (u 1 , u 2 , . . . , u ℓ d +1
) and ), where each component is defined by one of the nine letters 0, 1, . . . , 8 described in Table 3.

- → V = (b d+1 , a ′ d+1,1 , a ′ d+1,2 , . . . , a ′ d+1,ℓ d+1 ) = (v 1 , v 2 , . . . , v ℓ d +1
We then force the components of vector -→ 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 ϵ to states t ̸ = 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 and 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 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 t ̸ = force the two conditions to not use the same arguments. . 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.

Pre-computing the

-For each possible combination of values p of parameter P wrt the potential values of a ′ d,

- → U - → V -→ W Condition (s) (-1, 1) (-1, 1) (0, 4) none ( 0, 2) (-1, 1) (1, 5) ¬Cd(1)
( 0, 3) (-1, 1) (1, 5) ¬Cd (2)
( 0, 3) ( 0, 2) (2, 7) ¬Cd(2) ¬Cd+1(1) ( 1, 2) (-1, 1) (1, 5) Cd(1) ( 1, 3) (-1, 1) (1, 5) Cd(2)
( 1, 3) ( 0, 2) (2, 7) Cd( 2) ¬Cd+1( 1)

( 1, 3) ( 1, 2) (4, 7) Cd(2) Cd+1(1) (A) (B)
x1 x2 xc [x1 -x2] [x2 -x1] [x1 mod 3] [x2 mod 3] 1 2 0 -1 1 1 2 2 1 0 1 -1 2 1 1 2 1 -1 1 1 2 1 3 1 -2 2 1 0 1 4 1 -3 3 1 1 V ♢ d,p = ∅ (i.e.
if there is only one value the condition would always be true), otherwise V ♢ d,p = V d,p . • [♢ is '≤' or '≥']: let α and ω respectively be the smallest and the largest value of the set V d,p ; then V ♢ d,p = V d,p \ {α, ω}. The intuition for ♢ ='≤' is as follows: if we keep α then ♢ ='≤' is equivalent to ♢ ='=' ; if we keep ω the condition will always be true. For '≥' the intuition is symmetrical.

-We may further reduce the set V ♢ d,p 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 pos d,p (resp. V neg d,p ) such sets. From these sets, we compute the further restricted set V ♢,g d,p as follows:

• [g is '∧']: if ♢ is '=' then V ♢,g d,p = V pos d,p else V ♢,g d,p = V pos d,p ∩ V ♢ d,p , • [g ∈ {' ∨ ', ' + '}]: V ♢,g d,p = V ♢ d,p \ V neg d,p , • [g / ∈ {' ∧ ', ' ∨ ', ' + '}]:V ♢,g d,p = V ♢ d,p . -Finally, we set up the table constraint table a ′ d,1 , . . . , a ′ d,ℓ d , c d,1 , . . . , c d,ℓ ′ d , S
where S corresponds to the union of cartesian products ∪ p∈P (p × V ♢,g d,p ).

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 mod c 2,1 ≥ c 2,2 ].
• For C 1 we have only two options for p = {a 1,1 , a 1,2 }, namely:

1) p = {1, 2}: V 1,p = {-3, -2, -1, 1}, V = 1,p = V 1,p , V =,'∧' 1,p = {-3, -2, -1}, V =,'∨' 1,p = V = 1,p \ {-1, 1} = {-3, -2}. 2) p = {2, 1}: V 1,p = {-1, 1, 2, 3}, V = 1,p = V 1,p , V =,'∧' 1,p = {1, 2, 3}, V =,'∨' 1,p = V = 1,p \ {-1, 1} = {2, 3}.
• 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}, α = 1, ω = 2, V ≥ 2,p = V 2,p \ α, ω = ∅, i.
e. this set of options for this condition is not considered any further.

2) p = {2, 3}:

   V 2,p = {0, 1, 2}, α = 0, ω = 2, V ≥ 1,p = V 2,p \ {α, ω} = {1}, V pos 2,p = {1}, V neg 2,p = {1, 2}, V ≥, '∧' 2,p = V pos 2,p ∩ V ≥ 2,p = {1}, V ≥,'∨' 2,p = V ≥ 2,p \ V neg 2,p = ∅.

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 V and a set of ordered pairs of vertices A with the restriction that each vertex of V occurs in at least one pair of A [START_REF] Beldiceanu | Global constraints as graph properties on a structured network of elementary constraints of the same type[END_REF]. -rooted tree: a connected acyclic undirected graph where a vertex is designed as the "root" of the tree [START_REF] Knuth | Art of Computer Programming[END_REF]. -rooted forest: a disjoint union of rooted trees [START_REF] Knuth | Art of Computer Programming[END_REF]; we also consider a variant, rooted forest2, where all rooted trees have at least two vertices. -partition: a partition of a set S is a collection of possibly empty subsets of S such that every element of S is in exactly one of the subsets of the collection. The use of a partition was motivated the by fact that a partition can be interpreted as a solution to the conjunction of the nvalue (i.e. the number of partition subsets, see [START_REF] Pachet | Automatic generation of music programs[END_REF]) 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 [START_REF] Bessière | The balance constraint family[END_REF], we also consider a version of partition named parti-tion0 where all subsets of 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 [START_REF] Pesant | A filtering algorithm for the stretch constraint[END_REF]; 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 [START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF]. We evaluate the CP models of Sect. 4 and 5 wrt to the following two aspects: third columns) discovered compared to the model described in [START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF], which only looked for formulae with polynomials and arithmetic functions involving two polynomials (i.e. the P. Model).

= 1 + [¬(s ≤ c ∧ oc ≤ 1)] digraph 20 c0, c, s, s c0 = [¬ voting(c = s, c = 1, min(c, s) = 1)] rooted tree 6 d, v, f d = (v = f ∨ v = 1 ? 0 : f ) rooted forest 11 p, d, t d = 2 -([p = 0] + [(t -p) = 1]) partition 14 n, nval, m nval = 1 + [2 • m ≤ n] stretch 26 sr , dr , dm dm = [(sr + dr ) ≥ 1] cyclic stretch 26 osc, n, ng osc = [¬ card1(n = 2 • ng, n • ng = 3, n • ng ≤ 3)]

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 [START_REF] Blum | Relevant examples and relevant features: Thoughts from computational learning theory[END_REF], and provides a survey of various algorithms in [START_REF] Blum | Selection of relevant features and examples in machine learning[END_REF]. 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 [START_REF] Nguifo | Using lattice-based framework as a tool for feature extraction[END_REF][START_REF] Mossel | Learning functions of k relevant variables[END_REF][START_REF] Forman | Extremely fast text feature extraction for classification and indexing[END_REF]. In [START_REF] Mutlu | Review on graph feature learning and feature extraction techniques for link prediction[END_REF], 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 [START_REF] Yu | Computing optimal decision sets with sat[END_REF] or neural networks [START_REF] Mereani | Exact and approximate rule extraction from neural networks with boolean features[END_REF]. Lastly, there are papers [START_REF] Jakobovic | Toward more efficient heuristic construction of boolean functions[END_REF][START_REF] Golia | Engineering an efficient boolean functional synthesis engine[END_REF] 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 [START_REF] Jun | Learning dispatching rules using random forest in flexible job shop scheduling problems[END_REF], decision trees [START_REF] Aung | Comparing analytical decision support models through boolean rule extraction: A case study of ovarian tumour malignancy[END_REF][START_REF] Barbareschi | Advancing synthesis of decision treebased multiple classifier systems: an approximate computing case study[END_REF][START_REF] Kosman | Mining logical arithmetic expressions from proper representations[END_REF], Bayesian rule lists [START_REF] Yang | Scalable bayesian rule lists[END_REF], fuzzy association rules [START_REF] Au | Mining fuzzy association rules in a bank-account database[END_REF] and rough sets [START_REF] Lambert-Torres | Application of rough sets in power system control center data mining[END_REF] 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 [START_REF] Kosman | Mining logical arithmetic expressions from proper representations[END_REF] 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 [START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF] 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.

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 [START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF] 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.

3 .

 3 Quite often, using BAE allows one simplifying formulae with min and max as illustrated now. Let v, c, c 23 and 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 . . . . . . . we have v = 7, c = 3, c 23 = 2, s = 2. As discovered by the CP model of[START_REF] Beldiceanu | Acquiring maps of interrelated conjectures on sharp bounds[END_REF], when c is minimal, we have c 23 = (v.s ≤ 3 ? min(v -1, 1) : 0),1 which can be replaced by the Boolean relation c 23

[

  Case aggregator g is '∨' ] -For each positive row j (with j ∈ [1, r]), we post the constraint ∨ m d=1 [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 ∈ [1, m]) and each negative row j (with j ∈ [1, r]), we post the constraint table(⟨(b d , b d,j

  [1, r]), we post the constraint tab[j, c] = m d=1 [b d = b d,j ] to ensure that the appropriate number of conditions are satisfied.

  Class g Positive entries (tab[j, c] = 1) Negative entries (tab[j, c] = 0) I '∨' ∨ m d=1 [b d = b d,j ]

Example 2 (

 2 Continuation of Example 1).

5. 1

 1 Linking the Number of Conditions, their Arity, and the Number of Attributes

3

  k=1 n AC,k and3 k=1 k • n AC,k = c i=2 o i ,where o i is the number of occurrences of value i in the variables a ′ d,1 , a ′ d,2 , . . . , a ′ d,ℓ 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 ∈ [1, 3]):

  For each pair of consecutive conditions C d a d,1 , . . . , a d,ℓ d , c d,1 , . . . , c d,ℓ ′ d , C d+1 a d+1,1 , . . . , a d+1,ℓ d+1 , c d+1,1 , . . . , c d+1,ℓ ′ d+1 (with d ∈ [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

′ d - 1 ,

 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 ♢ used in condition C d , we derive for each combination of values p of parameter P , the set of values of coefficient c d,ℓ ′ d which does not make condition C d always true or always false. We denote such sets as V ♢ d,p . They are obtained from the sets V d,p in the following way. • [♢ is '=']: when the coefficient c d,ℓ ′ 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 no condition is used

Fig. 1 .

 1 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 -→ U , -→ V , -→ W and corresponding used conditions with their arguments (each condition mentions one single attribute).

  the variables a d,1 , . . . , a d,ℓ 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 , . . . , c d,ℓ ′ d represents the coefficients used in the arithmetic expression of condition C d .

	potential candidate BAC C d of f (with d ∈ [1, m]) mentioning ℓ d
	columns of the tab table (with ℓ d ∈ [1, 3]) and ℓ ′ d coefficients (with ℓ ′ d ∈ [0, 2]) is
	represented by the term C d	a d,1 , . . . , a d,ℓ d , d c d,1 , . . . , c d,ℓ ′	, where:

  j,2 , . . . , v d,j,ℓ d ) . Now, based on the aggregator g, we state a few row constraints for each used condition C d (with d ∈ [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 ∈ [1, m]) falsifies the Boolean arithmetic expression f . Aggregators '∨' 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 '+', '⊕', '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.

Table 1 .

 1 Row constraints which are posted on a positive or a negative table entry for computing the value of a Boolean arithmetic expression f , depending on the used aggregator g of classes I, II; for class III the same row constraint is posted for all entries.

Table 2 .

 2 Illustrating

the core model on the table tab[1..9, 1..4] (with columns x1, x2, x3, x4) for acquiring a Boolean-arithmetic expression explaining x4 wrt x1, x2, x3 using the '∨' aggregator with two conditions C1 and C2 selected from the following potential candidate conditions C1 : xi -xj = cst, C2 : xi ≤ cst and C3 : xi = xj.

  Table 2 summarises the acquisition of the BAE x 4

  ). 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 , . . . , a ′ d,ℓ d are all in the range [2, c] as we applied the offset +1. By pairwise comparing the k-th components of vectors

	we create the following vector	-→ W = (w	-→ U and	-→ V (with k ∈ [1, ℓ d + 1])

1 , w 2 , . . . w ℓ d +1

  Combinations of Possible Values of the Coefficients of a Condition Most BACs C d a d,1 , . . . , a d,ℓ d , c d,1 , . . . , c d,ℓ ′

		can be presented as a comparison of the form
	d d (with ♢ ∈ {≤, =, ≥}), where C ′ d (P ) ♢ c d,ℓ ′ C ′ d (P ) is an arithmetic expression
	parameterised by P =	a ′ d,1 , . . . , a ′ d,ℓ d , c d,1 , . . . , c d,ℓ ′ d -1

Table 4 .

 4 Example table for pre-computing the possible values of the coefficients for conditions C1 and C2

  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 for-
	mulae 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 5 .

 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) c0: 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.

	Combinatorial	Number Some of the	Examples of discovered
	object	of char.	used char.	conjectures
	digraph	20	c, c, s, oc	c

Table 6 .

 6 Computing time for the Core and the Enhanced models wrt aggregators (left side) and combinatorial objects (right side)

			Number of	Average time	Combinatorial Number of	Average time
	g	n AC	conjectures	per conjecture	object	conjectures	per conjecture
				C. Model E. Model			C. Model E. Model
	∧	1	2311	0.36s	0.35s	digraph	546	43s	10s
	∧	2	341	25.5s	11s	rooted tree	56	1.5s	1s
	∧	3	5	2591s	542s	rooted forest	229	3.4s	1.3s
	∨	2	190	18.9s	6.1s	rooted forest2	586	18.2s	5.9s
	∨	3	1	3062s	292s	partition	24	2.7s	1.7s
	eq	2	143	35.7s	14.7s	partition0	24	0.8s	0.5s
	eq	3	47	309s	50s	stretch	1059	10s	2.7s
	+	2	662	2s	1.3s	cyclic stretch	1182	6.4s	1.8s
	card1 3	2	1003s	27.5s
	voting 3	4	345s	66s	Total	3706	14.4h	3.9h

Table 7 .

 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

	Combi-	Number of (BF) which are:	Combi-	Number of (BF) which are:
	natorial	found	replacing	new	natorial	found	replacing	new
	object		polynomials		object		polynomials
	digraph	164	118	46	partition	20	20	0
	rooted tree	26	26	0	partition0	10	10	0
	rooted forest	91	86	5	stretch	93	93	0
	rooted forest2 149	145	4	cyclic stretch 145	144	1

The expression (cond ? x : y) denotes x if condition cond holds, y otherwise.

Input letter Corresponding condition

Comment

Both conditions are unused.

The 1st condition is used positively, and the negation of the 2nd condition is used.

The negation of the 1st condition is used, and the negation of the 2nd condition is used.

k > 1: attributes of both conditions are unused.

u k is an attribute of the 1st condition, and v k an unused attribute of the 2nd condition, as the 2nd condition is unused.

u k and v k are attributes of the two used conditions, such that u k < v k .