Abdelmajid Amine

Temporarily Vulnerable Consumers in a Bank Services Setting

Keywords: Temporarily vulnerable customer, bank advisor, coping strategies, social inclusion, wellbeing, case study

published or not. The documents may come   L'archive ouverte pluridisciplinaire


domain: math info

text:
We survey some of the most well known results of Professor Ivo G. Rosenberg as well as present some new ones related to the study of maximal partial clones and their intersections.

After a long struggle with Parkinson's disease, yet hard working and keeping a very kind spirit, Professor Ivo G. Rosenberg died on January 18, 2018. He was born in Brno (Moravia, Czech Republic), on December 13, 1934. One year before obtaining the doctoral degree, he published his Completeness Criterion [START_REF] Rosenberg | La structure des fonctions de plusieurs variables sur un ensemble fini[END_REF] in 1965. In July 1966, Professor Rosenberg received his doctoral degree on his very same wedding day. Together with his wife Vlasta (known as Loty to all family friends), he moved to Saskatoon, Canada, in September 1968. After the birth of their two children, Madeleine (known as Misha) and Marc, the family moved to Montréal in September 1971. Ivo held the position of researcher with the rank of Full Professor from 1971 to 1983 at the "Centre de recherches mathématiques de l'Université de Montréal", and later he was appointed as a full Professor at the "Département de mathématiques et de statistique" from 1983 to August 2011. Ivo retired in August 2011.

Professor Ivo G. Rosenberg was an eminent scholar, brilliant mathematician, and one of the leading experts in universal algebra and discrete mathematics. His huge impact and contributions to these areas of mathematics are very hard to assess due to the great extension and ramifications of his works. According to [START_REF] Machida | His contribution to ISMVL[END_REF], Ivo Rosenberg wrote more than 200 papers and several books, and the number of his co-authors exceeds 55, among which are the three authors of this paper.

Professor Rosenberg contributed to more than 50 conference papers in the various International Symposia on Multiple-Valued Logic. Some of his contributions to these symposia are listed and discussed in [START_REF] Machida | His contribution to ISMVL[END_REF]. He was extremely generous towards his colleagues and provided great hospitality both personally and through his position at the University of Montréal. He wrote numerous research reports and doctoral thesis reports.

For his outstanding research and contributions to mathematics, Professor Rosenberg received two honorary doctorates: the first from the Technische Universität Wien (Vienna Poly-technic) in 2006 and the second from the Universität Rostock (Rostock University) in 2013.

Ivo Rosenberg organized several scientific meetings in Montréal and elsewhere, notably many sessions of the well known "Séminaire de Mathématiques Supérieures de l'Université de Montréal" like, for example, the "24e session: Algèbre universelle et relations" (Montréal, July 23-August 10, 1984), and the "30e session "Algèbres et ordres" (Montréal, July 29-August 9, 1991) as well as the "premier colloque montréalais sur la combinatoire et l'informatique" (Montréal, April 27-May 2, 1987).

Together with Maurice Pouzet, he organized the conference "Aspects of Discrete Mathematics and Computer Science" (Lyon, June [START_REF] Haddad | Foreword: Ivo G. Rosenberg's 65th Birthday, Multiple-Valued Logic[END_REF][START_REF] Haddad | Maximal and Minimal Partial Clones[END_REF][START_REF] Haddad | Intervals of partial clones containing Maximal Clones[END_REF][START_REF] Haddad | Monoidal Intervals of Partial Clones[END_REF]1987) within the first "Entretiens du Centre Jacques-Cartier". The second "Entretiens", called "Discrete Mathematics and Computer Science" (Montréal, October 12-14, 1988) Several of his students became prominent mathematicians and computer scientists, to mention a few: Anne Fearnley, Jens-Uwe Grabowski, Lucien Haddad, Simone Hazan, Sebastian Kerkhoff, Gérard Kientega, Benoît Larose, Maxime Lauzon, Florence Magnifo, Qinghe Sun, Bogdan Szczepara and Calvin Wuntcha. The main goal of this survey is not to give an exhaustive account of Professor Rosenberg's contributions, but rather to give a very brief survey of some of his most influential works in mathematics. For further information see, e.g., [START_REF] Haddad | Foreword: Ivo G. Rosenberg's 65th Birthday, Multiple-Valued Logic[END_REF], [START_REF] Haddad | Some Aspects of the Mathematics of Ivo Rosenberg[END_REF], [START_REF] Machida | His contribution to ISMVL[END_REF].

I. CLONES

A. Completeness in Multiple-Valued Logic

Professor Ivo G. Rosenberg has been extremely active in research and became one of the world's leading mathematicians in universal algebra and discrete mathematics. He became known in the 70's for his general completeness criterion in multiple-valued logic. It was first presented in 1965 [START_REF] Rosenberg | La structure des fonctions de plusieurs variables sur un ensemble fini[END_REF] and the full proof was published in [START_REF] Rosenberg | Über die funktionale Vollständigkeit in den mehrwertigen Logiken[END_REF]. Rosenberg's completeness criterion is one of the most fundamental results in multiple valued logic and universal algebra, and its impact is impossible to estimate given the ever increasing number of research papers that followed it.

Let k := {0, 1, . . . , k-1}, Op(k) be the set of all operations on k and let Π k be the set of all projections on k. For X ⊆ Op(k), we denote by Clone(X) the set of all operations on k that can be realized by composing functions from X ∪ Π k . A set X ⊆ Op(k) is a clone if Clone(X) = X and X is said to be complete if Clone(X) = Op(k). Thus X is complete if and only if any function f : k n → k can be realized by composing functions from X ∪ Π k . For a relation ρ on k, let Pol (ρ) be the set of all functions f ∈ Op(k) preserving ρ.

As a closure system, the set of all clones constitutes a lattice under C ∧ C = C ∩ C and C ∨ C = Clone(C ∪ C ), and where Op(k) and Π k are its greatest and least elements. It is also well known that this lattice is atomic and co-atomic, and its atoms and co-atoms are referred to as minimal and maximal clones, respectively.

For the purpose of presenting Rosenberg's classification of all maximal clones over k, we recall some families of relations on k. For 1 ≤ h ≤ k, let

ι h k := {(a 1 , . . . , a h ) ∈ k | a i = a j for some 1 ≤ i < j ≤ h}.
Let ρ be an h-ary relation on k and denote by S h the set of all permutations on {0, . . . , h -1}. For π ∈ S h set ρ (π) := {(x π(1) , . . . , x π(h) ) | (x 1 , . . . , x h ) ∈ ρ}.

The h-ary relation ρ is said to be 1) totally symmetric (or simply symmetric in the case h

= 2) if ρ (π) = ρ for every π ∈ S h , 2) totally reflexive (in case h = 2 reflexive) if ι h k ⊆ ρ, 3) prime affine if h = 4, k = p m
where p is a prime number, m ≥ 1, p := {0, . . . , p -1} and we can define an elementary abelian p-group (k, +) on k so that

ρ := {( a, b, c, d) ∈ k 4 | a + b = c + d}. 4) central, if ρ = k h , ρ is totally symmetric, totally reflexive and {c}×k h-1 ⊆ ρ for some c ∈ k (notice that for h = 1 each ∅ = ρ ⊂ k is central and for h ≥ 2 such c is called a central element of ρ), 5) elementary, if k = h m , h ≥ 3, m ≥ 1 and (a 1 , a 2 , . . . , a h ) ∈ ρ ⇐⇒ ∀ i = 0, . . . , m -1, (a [i] 1 , a [i] 2 , . . . , a [i] h ) ∈ ι h h ,
where

a [i] (a ∈ {0, 1, . . . , h m -1}) denotes the i-th digit in the h-adic expansion a = a [m-1] • h m-1 + a [m-2] • h m-2 + • • • + a [1] • h + a [0] ,
6) a homomorphic inverse image of an h-ary relation ρ on k , if there is a surjective mapping q : k → k such that (a 1 , . . . , a h ) ∈ ρ ⇐⇒ (q(a 1 ), . . . , q(a h )) ∈ ρ for all a 1 , . . . , a h ∈ k, 7) h-universal, if ρ is a homomorphic inverse image of an h-ary elementary relation.

Furthermore, we denote by

• C k the set of all central relations on k;

• C h k the set of all h-ary central relations on k; • U k the set of all non-trivial equivalence relations on k;

• P k,p the set of all fixed-point-free permutations on k consisting of cycles of the same prime length p ;

• S k,p := {s 0 | s ∈ P k,p }, where s 0 := {(x, s(x)) | x ∈ k} is the graph of s; • S k := {S k,p | p is a prime divisor of k}; • M k the set
of all order relations on k with a least and a greatest element; • M k the set of all lattice orders on k; • L k the set of all prime affine relations on k;

• B k the set of all h-universal relations, 3 ≤ h ≤ k -1.
Endowed with this terminology and notation, we can now state Rosenberg's celebrated classification of maximal clones on k.

Theorem 1. ([49], [50]) Let k ≥ 2. Every proper clone on k is contained in a maximal one. Moreover a clone M is a maximal clone over k if and only if M = Pol ρ for some relation ρ ∈ C k ∪ M k ∪ S k ∪ U k ∪ L k ∪ B k .
Since every clone C = Op(k) is contained in a maximal clone on k, we have the following completness criterion. Theorem 2. A set of functions X ⊆ Op(k) is complete if and only if for every relation ρ described in Theorem 1, X contains a function f not preserving ρ.

Several variant completeness criteria have been obtained from Theorem 1. For example, we say that X ⊆ Op(k) is complete with constants if the set X ∪ {c a | a ∈ k} is complete, where c a : k → k is the unary constant map with value {a}. Here are two examples of sets that are complete with constants.

A simple group is a non-trivial group with only two normal (trivial) subgroups. A simple ring is a non-zero ring (i.e., there are x, y such that xy is not the zero element) with no nontrivial double-sided ideals. We have Corollary 3. (1) A finite group is complete with constants if and only if it is a simple non-abelian group.

(2) A finite ring is complete with constants if and only if it is a simple ring.

B. Minimal clones

Recall that a clone C is said to be minimal if C is an atom in the lattice of all clones, or, equivalently, if C is generated by any of its non-trivial functions. A non-trivial function of smallest arity in a minimal clone is called a minimal function.

The following is one of the deepest results in the literature concerning minimal clones. It is due to Ivo Rosenberg and was first published in [START_REF] Rosenberg | Minimal clones I: the five types[END_REF].

Theorem 4. Let f be a minimal function of arity n over k. Then f satisfies one of the following conditions:

1) n = 1 and f satisfies f 2 = f or f p (x) = x for some prime number p, 2) n = 2 and f is an idempotent function, i.e., f (x, x) = x, 3) n = 3 and f is a majority function, i.e., f (x, x, y) = f (x, y, x) = f (y, x, x) = x, 4) n = 3 and f (x, y, z) = x + y + z, where (k, +) is an elementary 2-group, or 5) n > 2 and f is an n-ary semiprojection, i.e., there is an i ∈ {1, . . . , n} such that f (x 1 , . . . , x n ) = x i whenever |{x 1 , . . . , x n }|< n.

A significant amount of research has been devoted to the study of minimal clones because, among other things, of their use in the study of strongly rigid relations. This is discussed in Section 3. Further fruitful applications of minimal clones and their descriptions can be found in the theory of constraint satisfaction problems (CSPs, see, e.g. [START_REF] Jeavons | An Algebriac Characterization of Tractable Constraints[END_REF]) and the theory of essential arguments of functions [START_REF] Berman | On the number of operations in a clone[END_REF], [START_REF] Čimev | On some properties of functions[END_REF], [START_REF] Couceiro | A survey on the arity gap[END_REF], [START_REF] Salomaa | On essential variables of functions, especially in the algebra of logic[END_REF], [START_REF] Willard | Essential arities of term operations in finite algebras[END_REF].

II. PARTIAL CLONES

Professor Rosenberg made significant contributions in many other areas of multiple-valued logic, like for example to the theory of partial clones. We will focus here on one of his main contributions in this domain, the completeness criterion for finite partial algebras and some related results.

A. Completeness Criterion for Finite Partial Algebras.

Denote by Par(k) the set of all partial functions on k and for a relation ρ over k, we denote by pPol ρ the set of all partial functions f ∈ Par(k) that preserve ρ. We need to introduce some terminology to state the Completeness Criterion for Finite Partial Algebras.

A relation ρ on k extremal if M := pPol ρ is a maximal partial clone and if ρ is of minimal size among all relations that determine the same maximal partial clone M . Let E h denote the set of all equivalence relations on the set h, and let ω h be the smallest element in E h , i.e.,

ω h := {(x, x) | x ∈ h}. Then for ε ∈ E h , put ∆ ε := {(x 0 , . . . , x h-1 ) ∈ k h | (i, j) ∈ ε ⇒ x i = x j }.
We often denote ∆ ε by ∆ X1,...,Xn , where X 1 , . . . , X n are the nonsingleton equivalence classes of ε. Moreover let

Γ h k := 0≤i<j≤h-1 ∆ {i,j} .
Notice that Γ h k is the set of all tuples (a 0 , . . . , a h-1 ) ∈ k h such that a i = a j for some 0 ≤ i < j ≤ h -1.

An h-ary relation ρ is said to be (a) diagonal if there exists ε

∈ E h such that ρ = ∆ ε , (b) areflexive if ρ ∩ ∆ ε = ∅ for each ε ∈ E h , ε = ω h ,
i.e., for all (x 0 , . . . , x h-1 ) ∈ ρ, x i = x j holds for all

0 ≤ i < j ≤ h -1, (c) quasi-diagonal if ρ = σ ∪ ∆ ε where σ is a non-empty areflexive relation, ε ∈ E h \{ω h }, and in addition, ρ = k 2 if h = 2, (d) totally reflexive if Γ h k ⊆ ρ.
Let σ be an h-ary relation on k and suppose that there is a subgroup G of S h such that σ = σ (π) for all π ∈ G and σ ∩ σ (α) = ∅ for all α ∈ S h \ G. Then G is called the group of symmetries of the relation σ. An h-ary relation ρ is totally symmetric if S h is its group of symmetries, i.e., if

(x 0 , . . . , x h-1 ) ∈ ρ ⇔ (x π(0) , . . . , x π(h-1) ) ∈ ρ, ∀π ∈ S h .
The following quaternary relations on k play an important role in the study of maximal partial clones (see Theorem 5). Let

R 1 := ∆ {0,1},{2,3} ∪ ∆ {0,2},{1,3} ∪ ∆ {0,3},{1,2} , R 2 := ∆ {0,1},{2,3} ∪ ∆ {0,3},{1,2} , R 3 := ∆ {0,1},{2,3} ∪ ∆ {0,2},{1,3}
, and

R 4 := ∆ {0,2},{1,3} ∪ ∆ {0,3},{1,2} . Observe that (x 0 , x 1 , x 2 , x 3 ) ∈ R 2 if and only if [x 0 = x 1 and x 2 = x 3 ] or [x 0 = x 3 and x 1 = x 2 ].
Now let σ be an areflexive h-ary relation and let

F ⊂ E h . Put G σ : = {π ∈ S h | σ ∩ σ (π) = ∅} and suppose that the h-ary relation ρ is of the form ρ = σ ∪ ( ε∈F (∆ ε )).
Then the model of ρ is the h-ary relation

M (ρ) : = {(π(0), . . . , π(h -1)) | π ∈ G σ } ∪ ε∈F {(x 0 , . . . , x h-1 ) ∈ h h | (i, j) ∈ ε ⇒ x i = x j } on the set h.
Furthermore, suppose that h, F and σ satisfy one of the following five conditions:

1) h ≥ 2, F = ∅ and σ = ∅, i.e., ρ is a nonempty h-ary areflexive relation; 1) when either of conditions (1) or ( 2) are satisfied,

2) h ≥ 2, F = {ε} where ε = ω h , σ = ∅ and σ ∪ ∆ ε = k 2 , i.e., ρ is a nontrivial quasi-diagonal h-ary relation; 3) h = 4 and F = {{[0, 1], [2, 3]}, {[0, 3], [1, 2]}, {[0, 2], [1, 3]}}, i.e., ρ = σ ∪ R 1 ,
G σ = {π ∈ S h | σ (π) = σ} and π(ε) := {(π(x), π(y)) | (x, y) ∈ ε} = ε, ∀ π ∈ G σ ;
2) when condition (3) is satisfied,

G σ = {π ∈ S 4 | σ (π) = σ} = {π ∈ S 4 | π(F ) = F } = S 4 ;
3) when condition ( 4) is satisfied,

G σ = {π ∈ S 4 | σ (π) = σ} = {π ∈ S 4 | π(F ) = F };
4) when condition ( 5) is satisfied,

G σ = {π ∈ S h | σ (π) = σ} = S h ; and
(B) for every non-empty subrelation σ ⊆ σ, there exists a relational homomorphism γ : k → h from σ to M (ρ) such that (γ(i 0 ), . . . , γ(i h-1 )) = (0, . . . , h -1) for at least one h-tuple (i 0 , . . . , i h-1 ) ∈ σ . The description of all maximal partial clones on a k-element set as given in [START_REF] Haddad | Completeness theory for finite partial algebras[END_REF] follows.

Theorem 5 ([18], [START_REF] Haddad | Completeness theory for finite partial algebras[END_REF], [START_REF] Haddad | Intervals of partial clones containing Maximal Clones[END_REF]). Let k ≥ 2. Every proper partial clone on k extends to a maximal one. If M is a maximal partial clone on k, then either Besides the completeness problem for partial algebras, Professor Rosenberg deeply contributed to the research on partial clones on a finite set. For space limitation, we will mention only one main contribution to the study of clones of partial Boolean functions. Let k = {0, 1}, I(SM ) be the interval of all partial clones containing the self-dual and monotone functions on {0, 1}. In the late 2000's it was widely believed that this interval must be finite. A breakthrough was obtained when the second author constructed an infinite set of partial clones contained in the interval I(SM ) (see [START_REF] Haddad | Infinite chains of partial clones containing all self-dual monotonic partial functions[END_REF]) proving that the interval is actually infinite. Later on, the first two authors, together with Ivo Rosenberg, proved that this interval is not just infinite, but it has the cardinality of the continuum ( [START_REF] Couceiro | Partial clones containing all Boolean monotone self-dual partial functions[END_REF]). Ivo Rosenberg came with the main construction of this paper and that construction, adapted to different situations, led to the complete solution, for the case of Boolean functions, to the following open problem in clone theory due to D. Lau: For each total clone C on k, describe the interval of partial clones

C = O k ∪ {f ∈ P k | dom (f ) = ∅} or M is
I(C) := {D | D is a partial clone on k and D ∩ O k = C}.
This problem was considered by several authors and many partial results were available in the literature. It is shown in [START_REF] Couceiro | A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones[END_REF] that if C is a clone on {0, 1}, then the interval of partial clones I(C) is finite for some finitely many clones listed in [START_REF] Couceiro | A Solution to a Problem of D. Lau: Complete Classification of Intervals in the Lattice of Partial Boolean Clones[END_REF] and I(C) has the cardinality of the continuum otherwise.

III. RIGIDITY AND PROJECTIVITY

Many works of Professor Rosenberg deal with several notions of rigidity and projectivity. We briefly survey a few in this section.

A relational structure R := (A, (ρ i ) i∈I ) on a set A is

• rigid if the identity is the only endomorphism of R;

• strongly rigid if the projections are the only maps of several variables which preserve R; • semirigid if the only unary functions which preserve ρ are the identity and all constant maps; • n-projective if the only idempotent n-ary functions which preserve R are the projections.

A. Rigidity and strong rigidity

In 1965, Vopěnka, Pultr, and Hedrlín [START_REF] Vopěnka | A rigid relation exists on any set[END_REF] proved that a rigid binary relation exists on any set. The existence of rigid relations was known for cardinality less that the first inaccessible cardinal and used by Pultr [START_REF] Pultr | Concerning universal categories[END_REF] to prove that the category R of binary relations is universal in the sense that every small category (the collection of objects is a set) is a full subcategory of R. This result supposed that no inaccessible existed. With the above result this restriction was not needed. Rosenberg [START_REF] Rosenberg | Strongly rigid relations[END_REF] observed that the relation constructed in [START_REF] Vopěnka | A rigid relation exists on any set[END_REF] is not strongly rigid and he proved that strongly rigid binary relations exist on any set with at least three elements.

B. Semirigidity

We recall that R is semirigid if the functions that preserve R are either the projections or the constant maps (Langer and Pöschel). Demetrovics, Miyakawa, Rosenberg, Simovici and Stojmenović [START_REF] Demetrovics | Intersections of isotone clones on a finite set[END_REF] introduced the following notion: two orders ρ and τ on the same set E are orthogonal if (E, τ, ρ) is semirigid. Nozaki, Miyakawa, Pogosyan and Rosenberg [START_REF] Nozaki | The number of orthogonal permutations[END_REF] investigated the existence of a linear order orthogonal to a given finite linear order. They observed that there is always one provided that the number of elements is not equal to three and proved: Theorem 7. The proportion q(n)/n! of linear orders orthogonal to the natural order on [n] := {1, ..., n} goes to e -2 = 0.1353... when n goes to infinity.

Their counting argument was based on the fact that two linear orders on the same finite set are orthogonal if and only if they do not have a common nontrivial interval. The notion capturing the properties of intervals of a linear order was extended a long time ago to posets, graphs and binary structures and a decomposition theory has been developed (see, e.g., [START_REF] Ehrenfeucht | The theory of 2-structures: a framework for decomposition and transformation[END_REF], [START_REF] Fraïssé | On a decomposition of relations which generalizes the sum of ordering relations[END_REF], [START_REF] Fraïssé | L'intervalle en théorie des relations; ses généralisations; filtre intervallaire et clôture d'une relation[END_REF], [START_REF] Gallai | Transitiv orientbare graphen[END_REF]). One of the terms in use for this notion is autonomous set; structures with no nontrivial autonomous subset-the building blocks in the decomposition theory-are called prime (or indecomposable). With this terminology, the above fact can be expressed by saying that two linear orders ρ and τ on the same finite set V are orthogonal if and only if the binary structure B := (V, ρ, τ ), that we call a bichain, is prime. This lead to results relating primality and orthogonality ( [START_REF] Rival | Perpendicular orders[END_REF], [START_REF] Zaguia | Prime two-dimensional orders and perpendicular total orders[END_REF]).

The notion of primality and Theorem 7 reappeared in recent years under quite a different setting: a study of permutations motivated by the Stanley-Wilf conjecture, now settled by Marcus and Tardos [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF]. This study, which developed in many papers, can be presented as follows: To a permutation σ on [n] associate first the linear order ≤ σ defined by x ≤ σ y if σ(x) ≤ σ(y) for the natural order on [n]; next associate the bichain B σ := ([n], (≤, ≤ σ )). On the set S := ∪ n∈N S n of all permutations, set σ ≤ τ if B σ is embeddable into B τ . Say that a subset C of S is hereditary if σ ≤ τ and τ ∈ C imply σ ∈ C. The goal is to evaluate the growth rate of the function ϕ C which counts for each integer n the number ϕ C (n) of permutations σ on [n] which belong to C (the Stanley-Wilf conjecture asserted that ϕ C is bounded by an exponential if C = S). For this purpose, simple permutations were introduced. A permutation σ is simple if ≤ σ and the natural order ≤ on [n] have no nontrivial interval in common. Arbitrary permutations being obtained by means of simple permutations, the enumeration of permutations belonging to a hereditary class of permutations can be then reduced to the enumeration of simple permutations belonging to that class. This fact was illustrated in many papers ( [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF], [START_REF] Klazar | Overview of general results in combinatorial enumeration[END_REF], see also [START_REF] Brignall | A survey of simple permutations[END_REF] for a survey on simple permutations and [START_REF] Albert | The enumeration of simple permutations[END_REF], where the asymptotic result mentioned in Theorem 7 is rediscovered).

Research on classes of finite permutations leads to the study of infinite bichains and particularly the prime one. But, in the infinite, primality and orthogonality no longer coincide. In [START_REF] Sauer | The order on the rationals has an orthogonal order with the same order type[END_REF], it was proved that the chain of the rational numbers admits an orthogonal linear order of the same order type. Pairs of orthogonal countable well-ordered chains have been described recently [START_REF] Laflamme | Pairs of countable orthogonal ordinals[END_REF].

Relational systems of equivalence relations are prototypes of semirigid systems, since, if a set E has at least three elements, only the constant functions and the identity preserve all equivalence relations on E. From this it follows that if a set {ρ i : i ∈ I} generates by means of joins and meets the lattice of equivalences on E then M := (E, (ρ i ) i∈I ) is semirigid. The converse does not hold. Indeed, according to Strietz [START_REF] Strietz | Über Erzeugendenmengen endlicher Partitionenverbände[END_REF], if E is finite with at least four elements, four equivalences are needed to generate the lattice of equivalence relations on E and Zádori [START_REF] Zádori | Generation of finite partition lattices[END_REF] has described for every set E, whose size |E| is finite and distinct from 2 and 4, a semirigid system made of three equivalence relations. A general method of constructing semirigid systems of three equivalence relations on sets of cardinality at most the continuum and distinct from 2 and 4 is developed in [START_REF] Delhommé | Semirigid Systems of Three Equivalence Relations[END_REF].

C. Projectivity

Corominas [START_REF] Corominas | Sur les ensembles ordonnés projectifs et la propriété du point fixe[END_REF] introduced the notion of 2-projectivity for ordered sets (posets). For posets, 2-projectivity is equivalent to n-projectivity [START_REF] Pouzet | A projection property[END_REF]. Larose, then a student Professor Rosenberg, showed that for P with at least three elements, projectivity is equivalent to the apparently weaker notion of quasiprojectivity 1 (projections beeing replaced by quasi-projections, i.e., maps f such that f (x 1 , . . . , x n ) ∈ {x 1 , . . . , x n }) [START_REF] Larose | Finite projective ordered sets[END_REF], [START_REF] Larose | A property of projective ordered sets[END_REF]. With Tardif [START_REF] Larose | Strongly rigid graphs and projectivity[END_REF] he obtained the same conclusion for graph (with no loops). More results of the same vein were obtained by Hazan [START_REF] Hazan | On triangle-free projective graphs[END_REF], another student of Professor Rosenberg, and by Delhommé [START_REF] Delhommé | Propriétés de projection des graphes sans triangle ni carré[END_REF] for posets and reflexive graphs. In [START_REF] Pouzet | A projection property[END_REF] it was shown that a relational structure R on a set A is 2-projective and not n-projective for some n > 2 if and only if its clone is the clone of maps which preserve the congruences of a 2-elementary group on a set of at least four elements. As a consequence, a proof of a form of Arrow's theorem on social choice is obtained.

IV. CONCLUSION

In "Ivo G. Rosenberg, A commemoration of his outstanding research contributions and friendship", (IEEE Computer Society, 2012), several colleagues wrote wonderful tributes about Ivo Rosenberg as a mathematician and even more about his exceptional qualities. Ivo will always be remembered not only for his huge contributions to mathematics, but also for all his human values, for the ways he treated colleagues, visitors, young researchers and graduate students. He will be remembered for his generosity, his modesty and for his extreme kindness. As our late colleague Dietlinde Lau described him, Ivo Rosenberg was a real gentleman of the old school. May his soul rest in peace.

  where σ is a (possibly empty) areflexive 4-ary relation; 4) h = 4 and F = {{[π(0), π(1)], [π(2), π(3)]}, {[π(0), π(3)], [π(1), π(2)]}}, where π ∈ S 4 , i.e., ρ = σ ∪ R i , where i = 2, 3, 4 and σ is a (possibly empty) areflexive 4-ary relation; 5) h = 2, h ≤ k, F = i<j {i, j} and ρ = k h , i.e., ρ is a totally reflexive and totally symmetric nontrivial relation. Then the h-ary relation ρ is said to be coherent if (A) the following conditions hold:

  , took place in Montréal the year after. It was organized by Ivo Rosenberg together with A. Achache, M. Algebras and Orders (1991) with Gert Sabidussi (Proceedings published in Nato Advanced Study Institute Series, Math. and Phys. Sci., 389), and (3) Structural Theory of Automata, Semigroups and Universal Algebra, (2003), with V. B. Kudryavtsev (Proceedings published in Nato Science Series, Math. Phys. and Chem. 207).

	Pouzet (Lyon) and G. Hahn (Montréal). Still within his col-
	laboration with French colleagues, Ivo organized a French-
	Quebec project "Ordered sets and their applications" from
	1984 to 1986.
	On the other hand, Ivo Rosenberg organized several col-
	loquia such as (1) Algebraic, Extremal and Metric Combina-
	torics, (1986) with M. Deza and P. Frankl (Proceedings pub-
	lished in London Mathematical Society Lecture Notes Series,
	131), (2)

  determined by an extremal relation on k. Furthermore a relation ρ is an extremal relation on k if and only if it is of one of the following types of relations: 1) an h-ary areflexive or quasi-diagonal relation which is coherent and h ≥ 2, 2) an h-ary non-trivial totally reflexive and totally symmetric relation and h = 2, 3) one of the quaternary relations R 1 or R 2 , 4) a quaternary coherent relation σ ∪ R i where i = 1, . . . , 4 and σ = ∅ is a quaternary areflexive relation. Remark 6. The number of maximal partial clones on a finite set k greatly exceeds the number of maximal clones on k. For example, Theorem 1 says that any order relation that is bounded defines a maximal clone, while Theorem 5 says that any non-trivial order relation defines a maximal partial clone on k. Let M k and pM k be the families of all maximal and maximal partial, respectively, clones on k. It is known (see, e.g., [16], [56]) that |M 2 |= 5 and |pM 2 |= 8, |M 3 |= 18 and |pM 3 |= 58, |M 4 |= 82 and |pM 4 |= 1102, |M 5 |= 634 and |pM 5 |= 325, 722, |M 6 |= 15, 182 and |pM 6 |= 5, 242, 621, 816.


domain: info math

text:
Professor Ivo Rosenberg Miguel Couceiro

Lucien Haddad
email: haddad-l@rmc.ca

Victor Lagerkvist
email: victor.lagerkvist@liu.se

Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey Dedicated to the memory of

Constraint satisfaction problems (CSPs) are combinatorial problems with strong ties to universal algebra and clone theory. The recently proved CSP dichotomy theorem states that finite-domain CSPs are always either tractable or NP-complete. However, among the intractable cases there is a seemingly large variance in complexity, which cannot be explained by the classical algebraic approach using polymorphisms. In this contribution we will survey an alternative approach based on partial polymorphisms, which is useful for studying the finegrained complexity of NP-complete CSPs. Moreover, we will state some challenging open problems in the research field.

I. ALGEBRAIC BACKGROUND

Let k ≥ 2 be an integer and let k be a k-element set. Without loss of generality we assume that k := {0, . . . , k -1}. An n-ary relation R over k is a subset of k n , and we write ar(R) = n to denote its arity, and Rel k for the set of all relations over k. For a positive integer n, an n-ary partial operation on k is a map f : dom(f ) → k where dom(f ) is a subset of k n , called the domain of f . Let Par (n) (k) denote the set of all n-ary partial operations on k and let Par(k) := n≥1 Par (n) (k). An n-ary partial operation g is said to be a total operation if dom(g) = k n , and we let Op (n) (k) be the set of all n-ary total operations on k and Op(k) := n≥1 Op (n) (k). For every positive integer n and each 1 ≤ i ≤ n, let e n i denote the n-ary i-th projection defined by e n i (a 1 , . . . , a n ) = a i for all (a 1 , . . . , a n ) ∈ k n . Furthermore, let J k := {e n i | 1 ≤ i ≤ n, n ∈ N \ {0}} be the set of all (total) projections. Partial operations on k are composed in a natural way. For additional details we refer the reader to Lau [START_REF] Lau | Function Algebras on Finite Sets: Basic Course on Many-Valued Logic and Clone Theory[END_REF].

Definition 1: A clone is a composition closed subset of Op(k) containing J k , and a partial clone on k is a composition closed subset of Par(k) containing J k . A partial clone is said to be strong if it is closed under taking suboperations 1 .

It is well known that a partial clone C is strong if and only if Str(J k ) ⊆ C (see, e.g., Lemma 2.11 in Haddad and Börner [START_REF] Börner | Maximal partial clones with no finite basis[END_REF]).

Moreover, strong partial clones are exactly those partial clones that are determined by relations in the following way. Let h, n ≥ 1 be integers, and let R be an h-ary relation on k. An n-ary partial operation f on k is said to preserve R if for every h × n matrix M = [M ij ] whose columns M * j ∈ R, and whose rows M i * ∈ dom(f ), the h-tuple (f (M 1 * ), . . . , f (M h * )) ∈ R. Note that if there is no h×n matrix M = [M ij ] whose columns M * j ∈ R and whose rows M i * ∈ dom(f ), then f preserves R. It is not difficult to see that pPol(R) := {f ∈ Par(k) | f preserves R} is a strong partial clone called the partial clone determined by the relation R. Similarly, if Γ is a set of relations over k we write pPol(Γ) for the set R∈Γ pPol(R). In the total case we similarly write Pol(R) for the set of total polymorphisms of R and Pol(Γ) if Γ is a set of relations. If F ⊆ Par(k) then we also write Inv(F ) for the set of relations preserved by all partial operations in F . Sets of the form Inv(F ) are known as relational clones, or co-clones, if each operation in F is total, otherwise they are called weak systems or weak co-clones.

The set of partial clones on k forms a lattice L P k under inclusion, in which the infimum is the set-theoretical intersection. Similarly, the set of strong partial clones on k also forms a lattice L Str(P k ) , which is a sublattice of L P k . By definition, J k and Str(J k ) are the least elements of L P k and L Str(P k ) , respectively. For further background see, e.g., [START_REF] Börner | Maximal partial clones with no finite basis[END_REF], [START_REF] Couceiro | Intersections of finitely generated maximal partial clones[END_REF], [START_REF] Couceiro | Partial clones containing all boolean monotone self-dual partial functions[END_REF]. For F ⊆ Par(k), let [F ] s denote the intersection of all strong partial clones on k containing F . Similarly, for F ⊆ Op(k), let [F ] be the intersection of all clones on k containing F , and in both cases we write [f ] or [f ] s when F = {f } is singleton.

II. CONSTRAINT SATISFACTION PROBLEMS

In a constraint satisfaction problem (CSP) the objective is to assign values to variables subjected to a set of constraints deciding permissible assignments. It is typically phrased as the decision problem of determining if there exists an assignment respecting all constraints, and we begin with the following definition which is predominant in computer science literature.

A constraint satisfaction problem (CSP) over a set k is defined as follows. INSTANCE: A tuple (V, C) where V is a finite set, and C a finite set of the form (R i , t i ) where R i ∈ Rel k and t i ∈ V ar (Ri) . QUESTION: Does there exist a function f :

V → k such that (f (x 1 i ), . . . , f (x ar(Ri) i )) ∈ R i for each (R i , (x 1 i , . . . , x ar(Ri) i )) ∈ C?
The set k is called the domain of the CSP -not to be confused with the domain of a partial operation. If k = 2 then k is said to be Boolean. The members of V are referred to as variables and are usually denoted by x or v. A tuple (R i , t i ) ∈ C is called a constraint, and we typically write R(t i ) instead of (R i , t i ). The function f , if it exists, is called a solution, a model, or a satisfying assignment.

CSPs can be further specified by fixing a set of relations Γ, called a constraint language. This problem is then referred to as CSP(Γ) and is restricted to instances (V, C) where R i ∈ Γ for each constraint (R i , t i ) ∈ C. If Γ is Boolean then CSP(Γ) can be viewed as a satisfiability problem, usually written SAT(Γ).

Observe that if we associate a constraint language Γ over a domain D with a relational signature τ , Γ can be treated as a relational structure Γ τ . With this viewpoint an instance {{v 1 , . . . , v n }, C} of CSP(Γ) can be viewed as an existentially quantified τ -formula ∃v 1 , . . . , v n : (Ri,ti)∈C R i (t i ), and the question is then simply to check whether this τ -formula admits at least one model. It is also possible to rephrase CSP(Γ) as a homomorphism problem, i.e., an instance I of CSP(Γ) can be seen as a τ -structure I and the goal is then to check if there exists a homomorphism between I and Γ τ .

Example 1: Let R 1/3 = {(0, 0, 1), (0, 1, 0), (1, 0, 0)}. Then SAT({R 1/3 }) can be seen as an alternative formulation of the monotone 1-in-3-SAT problem which is well-known to be NP-complete. By choosing a suitable Boolean Γ, a large range of satisfiability problems can be represented as a CSP(Γ) problem. For example, for each k ≥ 1 let Γ k SAT be the set of relations of the form {0, 1} k \ {t} for a single k-ary Boolean tuple t. Then SAT(Γ k SAT ) can be verified to be an alternative formulation of k-SAT which is NP-complete for k ≥ 3.

Example 2: Let us also consider a few non-Boolean examples. One of the prototypical examples of a CSP is the k-COLOURING problem: given an undirected graph (V, E), can (V, E) be coloured using at most k colours? To formulate this problem as a CSP we take the relation R = k = {(x, y) ∈ k 2 | x = y} and for each (x, y) ∈ E introduce a constraint R = k (x, y). It is also easy to find examples of tractable CSPs, i.e., CSPs solvable in polynomial time. One such example is systems of linear equations x 1 + . . . + x n = 0 (mod k) which can be solved in polynomial time using Gaussian elimination. As we will see in Section III this discrepancy in complexity between tractable and NP-complete CSPs can be explained using algebraic methods.

Although and the RECTANGLE ALGEBRA (cf. the surveys [START_REF] Bodirsky | A model-theoretic view on qualitative constraint reasoning[END_REF], [START_REF] Dylla | A survey of qualitative spatial and temporal calculi: Algebraic and computational properties[END_REF]).

III. POLYMORPHISMS AND THE COMPLEXITY OF CSP

Feder & Vardi conjectured that CSP(Γ) is either tractable or NP-complete [START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory[END_REF]; this conjecture is usually referred to as the CSP dichotomy conjecture. It was then realized that several classical algorithms resulting in tractability, e.g., Gaussian elimination and k-consistency, in a uniform manner could be explained by the presence of certain polymorphisms of Γ [START_REF] Jeavons | Closure properties of constraints[END_REF]. More generally, Jeavons proved the following reducibility result, usually interpreted as "the polymorphisms of Γ determine the complexity of CSP(Γ) up to polynomial-time reductions".

Theorem 2 ( [START_REF] Jeavons | On the algebraic structure of combinatorial problems[END_REF]): Let Γ and ∆ be two finite constraint languages over k. If Pol(∆) ⊆ Pol(Γ), then CSP(Γ) is polynomial-time many-one reducible to CSP(∆).

Proof: The condition Pol(∆) ⊆ Pol(Γ) is well-known to be equivalent to the condition Γ ⊆ Inv(Pol(∆)) [START_REF] Bodnarchuk | Galois theory for Post algebras[END_REF], [START_REF] Bodnarchuk | Galois theory for Post algebras[END_REF], [START_REF] Geiger | Closed systems of functions and predicates[END_REF]. This is furthermore known to imply that each R ∈ Γ can be expressed as a conjunction of constraints over ∆, possibly with the introduction of additional variables and equality constraints, and the reduction then proceeds as a classical "gadget reduction" where each constraint is transformed into the corresponding constraints over ∆.

To obtain a dichotomy for CSP(Γ) over k one would then need to fully describe all operations over k and determine all combinations resulting in tractable CSPs. However, such an undertaking turned out to be unecessary, due to the realization that the classical complexity of CSP(Γ) only depends on the identities, or the Strong Maltsev conditions, satisfied by the polymorphisms of Γ [START_REF] Bulatov | Classifying the complexity of constraints using finite algebras[END_REF]. For example, if Pol(Γ) contains a Maltsev operation satisfying the identities m(x, x, y) ≈ y, m(x, y, y) ≈ x, then CSP(Γ) is tractable since it can be solved by the simple algorithm for Maltsev constraints [START_REF] Bulatov | A simple algorithm for Mal'tsev constraints[END_REF]. The main advantage of this viewpoint is therefore that it suffices to describe all identities resulting in tractable CSPs rather than all concrete operations. This approach recently culminated in the following dichotomy theorem.

Theorem 3 ([9], [START_REF] Zhuk | The proof of CSP dichotomy conjecture[END_REF]): Let Γ be a constraint language over k. Then CSP(Γ) is either tractable or NP-complete.

For additional details concerning the classification project of CSP and the algebraic approach based on Strong Maltsev conditions, see e.g. the survey by Barto [START_REF] Barto | Constraint satisfaction problem and universal algebra[END_REF].

IV. PARTIAL POLYMORPHISMS AND THE FINE-GRAINED

COMPLEXITY OF CSP We begin this section by discussing the rather vague term "fine-grained complexity" in relationship to CSPs in Section IV-A, before we describe how the algebraic approach based on partial polymorphisms can be used to study this question in Section IV-B and Section IV-C.

A. Fine-Grained Complexity

Recall from Section III that polymorphisms are useful for studying the classical complexity of CSPs up to polynomialtime reductions. However, there is reason to believe that even NP-complete problems can exhibit a striking difference in complexity, and that it may be disadvantageous to group them together under the guise of polynomial-time reductions. For example, SAT({R 1/3 }) from Example 1, is known to be solvable in O(1.0984 n ) time, where n denotes the number of variables [START_REF] Wahlström | Algorithms, measures and upper bounds for satisfiability and related problems[END_REF], whereas it is not known whether the unrestricted SAT problem SAT(Rel {0,1} ) is solvable in O(c n ) time for c < 2. This phenomena is not restricted to CSPs: for example, van Rooij et al. [START_REF] Bodlaender | Partition into triangles on bounded degree graphs[END_REF] proved that the PARTITION INTO TRIANGLES problem restricted to graphs of maximum degree 4 can be solved in O(1.0222 n ) time despite being NP-complete.

Our main concern in this survey paper is thus to study the complexity of NP-complete CSPs with regards to O(c n ) time complexity (although we will also mention related applications in Section IV-B). To make this question more precise we begin with the following definition.

Definition 4: Let k ≥ 2. For Γ ⊆ Rel k we define T(Γ) as

T(Γ) = inf{c | CSP(Γ) is solvable in time 2 cn }
where n is the number of variables in an instance of CSP(Γ).

Note that it might be the case that CSP(Γ) is solvable in O(2 (c+ε)n ) time for every ε > 0 despite not being solvable in O(2 cn ) time -hence, the use of infimum in Definition 4 is necessary. It is important to observe that no concrete value of T(Γ) is known when CSP(Γ) is NP-complete. Before we begin studying the function T and its connection to partial polymorphisms we need to state the following conjecture, which is of central importance in current research on fine-grained complexity and lower bounds.

Definition 5: The exponential-time hypothesis (ETH) [START_REF] Impagliazzo | On the complexity of k-SAT[END_REF] conjectures that T(Γ 3 SAT ) > 0. In other words, the ETH states that there exists a c > 0 such that 3-SAT is not solvable in O(2 cn ) time. Although not immediate from Definition 5, the ETH is also known to imply that the sequence T(Γ 3 SAT ), T(Γ 4 SAT ), . . . increases infinitely often, i.e., that for every k there exists k > k such that T(Γ k SAT ) < T(Γ k SAT ) [START_REF] Impagliazzo | On the complexity of k-SAT[END_REF]. This makes it tempting to also conjecture that the limit of the sequence T(Γ 3 SAT ), T(Γ 4 SAT ), . . . equals 1; a conjecture known as the strong exponential-time hypothesis (SETH) [START_REF] Calabro | The complexity of satisfiability of small depth circuits[END_REF], [START_REF] Impagliazzo | On the complexity of k-SAT[END_REF]. Hence, under this conjecture the unrestricted SAT problem cannot be solved in O(2 cn ) time for any c < 1.

Let us also remark that CSP(Γ) for Γ ⊆ Rel k is always solvable in O(k n ) time by simply enumerating all possible assignments over k. Hence,

T(Γ) ≤ log 2 (k) for every Γ ⊆ Rel k . It is also known that if Γ ⊂ Rel k is finite then CSP(Γ) is solvable in O(c n ) time for a c < k [40], implying that T(Γ) < log 2 (k).

B. Weak Bases

Schnoor & Schnoor [START_REF] Schnoor | Partial polymorphisms and constraint satisfaction problems[END_REF] investigated connections between partial polymorphisms and the complexity of CSPs. However, their motivation was not to study the fine-grained complexity of CSPs, but to analyse the classical complexity of CSP-like problems incompatible with polymorphisms.

Example 3: CSP(Γ) is sometimes said to be a priori compatible with polymorphisms due to the existence of Theorem 2. In contrast, there exist problems proven to be a posteriori compatible with polymorphisms, in the sense that Pol(Γ) determines whether the problem is tractable or intractable, but where an analogue of Theorem 2 cannot be proven. One such example is the problem of finding a surjective model of a SAT(Γ) instance (SUR-SAT(Γ)), which is NP-complete if Pol(Γ) is essentially unary and tractable otherwise. Curiously, almost all CSP-like problems studied in the literature turn out to be either a priori or a posteriori compatible with polymorphisms, and only a handful of concrete counter examples exist, e.g., enumerating models of CSP(Γ) with polynomial delay [START_REF] Schnoor | Enumerating all solutions for constraint satisfaction problems[END_REF], the inverse satisfiability problem over infinite constraint languages [START_REF] Lagerkvist | A dichotomy theorem for the inverse satisfiability problem[END_REF], and the maximum satisfiability problem [START_REF] Creignou | A dichotomy theorem for maximum generalized satisfiability problems[END_REF].

Problems that are not a priori compatible with polymorphisms may instead be compatible with partial polymorphisms. It is, for example, straightforward to prove that if pPol(Γ) ⊆ pPol(∆) then SUR-SAT(∆) is polynomial-time many-one reducible to SUR-SAT(Γ). However, since the lattice of Boolean strong partial clones L Str(P {0,1} ) is largerly unexplored, this is not as useful as one might first believe. Schnoor & Schnoor [START_REF] Schnoor | Partial polymorphisms and constraint satisfaction problems[END_REF] realized that for many classification purposes, there is typically no need to consider the whole lattice L Str(P {0,1} ) , but only a small fragment corresponding to weak bases. Example 4: Let us again consider SUR-SAT(Γ) and assume that we are given a weak base Γ w of a co-clone Inv(C). If we can prove that SUR-SAT(Γ w ) is NP-complete, then NPcompleteness also carries over to every Γ such that Pol(Γ) = C. Hence, equipped with a weak base of each Boolean co-clone, we in practice only need to consider Post's lattice [START_REF] Post | The two-valued iterative systems of mathematical logic[END_REF] rather than L Str(P {0,1} ) .

Schnoor & Schnoor [START_REF] Schnoor | Partial polymorphisms and constraint satisfaction problems[END_REF] also described a procedure for constructing weak bases for co-clones satisfying the preconditions in Definition 6, which was leveraged by Lagerkvist to provide a list of weak bases for all Boolean co-clones [START_REF] Lager | Weak bases of Boolean co-clones[END_REF]. We will not describe this method in detail, but remark that it is based on the observation that the algebra whose universe consists of all n-ary operations in C can be viewed as a relation R, with the property that any partial operation not preserving R can be extended to a total operation. In the literature, this construction has been referred to as a n-generated free algebra [START_REF] Barto | Constraint satisfaction problem and universal algebra[END_REF], or the n-th graphic [START_REF] Pöschel | Funktionen-und Relationenalgebren[END_REF]. Using a similar strategy as in Example 4, weak bases have been used to obtain complexity dichotomies for several Boolean CSP-like problems incompatible with polymorphisms [START_REF] Behrisch | Give me another one![END_REF], [START_REF] Behrisch | As close as it gets[END_REF], [START_REF] Lagerkvist | A dichotomy theorem for the inverse satisfiability problem[END_REF], [START_REF] Schnoor | Partial polymorphisms and constraint satisfaction problems[END_REF], [START_REF] Schnoor | The weak base method for constraint satisfaction[END_REF].

C. An Algebraic Approach Based on Partial Polymorphisms

We are now ready to present the link between partial polymorphisms and the function T, allowing us to study the fine-grained complexity of CSPs using partial polymorphisms.

Theorem 7 ( [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF]): Let Γ and ∆ be two finite sets of relations. If pPol(Γ) ⊆ pPol(∆) then T(∆) ≤ T(Γ).

Proof: The proof is similar to Theorem 2: pPol(Γ) ⊆ pPol(∆) is known to be equivalent to the condition ∆ ⊆ Inv(Pol(Γ)) [START_REF] Geiger | Closed systems of functions and predicates[END_REF], [START_REF] Romov | The algebras of partial functions and their invariants[END_REF], which in turn implies that each R ∈ ∆ can be written as a set of constraints over Γ without introducing any fresh variables. If each constraint in a CSP(∆) instance is rewritten in this manner we obtain an instance of CSP(Γ) over the same set of variables, giving the bound T(∆) ≤ T(Γ).

Now, let C be a clone such that Pol(Γ) = C and CSP(Γ) is NP-complete. Theorem 7 then offers an algebraic method to analyse T(Γ) by studying the properties of I Str (C) := {pPol(Γ) | Pol(Γ) = C}. For example, if I Str (C) is finite, then the fine-grained complexity of CSP(Γ) would fall into a finite number of cases. Hence, as a rough approximation, we would like to know the cardinality of I Str (Pol(Γ)) when CSP(Γ) is NP-complete. A dichotomy has been proved for Boolean clones, with the surprising implication that these sets are always either finite or equal to the continuum.

Theorem 8 ( [START_REF] Couceiro | A solution to a problem of D. Lau: Complete classification of intervals in the lattice of partial boolean clones[END_REF], [START_REF] Schölzel | Dichotomy on intervals of strong partial Boolean clones[END_REF]): Let C be a Boolean clone. Then I Str (C) is finite if C ⊇ Pol({{(0, 1), (1, 0)}, {(0, 1)}}) or C ⊇ Pol({{(0, 0), (0, 1), (1, 1)}, {(0, 1)}}), and is of continuum cardinality otherwise.

By inspecting Post's lattice of Boolean clones [START_REF] Post | The two-valued iterative systems of mathematical logic[END_REF] one can then verify that the finite cases of Theorem 8 hold for only 10 clones. Furthermore, it is known that SAT(Γ) is NPcomplete if and only if Pol(Γ) = [f ¬ ] or Pol(Γ) = J {0,1} , where f ¬ (x) = 1 -x [START_REF] Schaefer | The complexity of satisfiability problems[END_REF], implying that I Str (Pol(Γ)) is of continuum cardinality whenever SAT(Γ) is NP-complete. Clearly, the fact that I Str (Pol(Γ)) is of continuum cardinality in these cases says very little of their actual complexity, but at least suggests that one needs a different line of attack than trying to obtain a characterization akin to Post's lattice.

Let us for the moment concentrate on Boolean constraint languages Γ such that Pol(Γ) = J {0,1} , which subsume the examples 1-IN-3-SAT and k-SAT from Example 1. Even though fully describing I Str (J {0,1} ) does not appear straightforward due to Theorem 8, there are still plenty of questions relevant for the fine-grained complexity of SAT(Γ). For example, does I Str (J {0,1} ) admit a greatest element, and if this is the case, is it then possible to describe the maximal elements? Similarly, is it possible to describe the minimal strong partial clones of I Str (J {0,1} ) -provided they exist (note that a unique least element trivially exists, namely Str(J {0,1} ))2 . These questions are of interest in fine-grained complexity since we from Theorem 7 would expect that "small" members of I Str (J {0,1} ) corresponds to SAT problems with high time complexity, and that "large" members of I Str (J {0,1} ) give rise to SAT problems of low time complexity. In fact, recalling the concept of a weak base R of a co-clone Inv(C) from Section IV-B, one of these questions can be answered immediately: pPol(R) ⊇ pPol(Γ) for each pPol(Γ) ∈ I Str (J {0,1} ) implies that pPol(R) is the greatest element. Furthermore, Inv(J {0,1} ) is known to admit a particularly simple weak base R = = =01 1/3 = {(0, 0, 1, 1, 1, 0, 0, 1), (0, 1, 0, 1, 0, 1, 0, 1), (1, 0, 0, 0, 1, 1, 0, 1)} [START_REF] Lager | Weak bases of Boolean co-clones[END_REF]. This observation was then leveraged by Jonsson et al. [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF] to show that SAT({R = = =01 1/3 }) results in the "easiest NP-complete SAT problem", in the following sense.

Theorem 9 ( [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF]):

SAT({R = = =01 1/3 }) is NP-complete and T({R = = =01 1/3
}) ≤ T(Γ) for any Boolean constraint language Γ such that SAT(Γ) is NP-complete.

Proof: We give a short sketch of the most important ideas. If SAT(Γ) is NP-complete then by Schaefer's dichotomy theorem either

Pol(Γ) = [f ¬ ] or Pol(Γ) = J {0,1} [35]. It is then known that the relation R = R = = =01 1/3 ∪ {(f ¬ (t) | t ∈ R = = =01 1/3
)} is a weak base of Inv({f ¬ }) [START_REF] Lager | Weak bases of Boolean co-clones[END_REF], and from Theorem 7 we then conclude that T({R}) ≤ T(Γ) or T(

{R = = =01 1/3 }) ≤ T(Γ), since pPol(Γ) ⊆ pPol(R) or pPol(Γ) ⊆ pPol(R = = =01 1/3
). Hence, it is sufficient to prove that T({R = = =01 1/3 }) ≤ T({R}), which can be accomplished by a polynomial-time many-one reduction only introducing a constant number of fresh variables (see Lemma 19 in Jonsson el al. [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF]).

This result was later extended to a broad class of finitedomain CSPs, so-called ultraconservative CSPs, which can be viewed as CSP(Γ) problems where Γ contains all unary relations over the domain.

Theorem 10 ( [START_REF] Jonsson | Time complexity of constraint satisfaction via universal algebra[END_REF]): For each k there exists a relation R k ∈ Rel k such that (1) CSP({R k }) is NP-complete, and (2) T({R}) ≤ T(Γ) for any ultraconservative Γ ⊆ Rel k such that CSP(Γ) is NP-complete.

Jonsson et al. [START_REF] Jonsson | Strong partial clones and the time complexity of SAT problems[END_REF] also conjectured that the strong partial clones between pPol(R 1/3 ) and pPol(R = = =01 1/3 ) had a simple structure consisting of only three elements pPol(R

01 1/3 ), pPol(R =01 1/3 ), pPol(R = =01 1/3 ), such that pPol(R 1/3 ) ⊂ pPol(R 01 1/3 ) ⊂ pPol(R =01 1/3 ) ⊂ pPol(R = =01 1/3 ) ⊂ pPol(R = = =01 1/3
). However, this turned out to be false: Lagerkvist & Roy first showed the existence of countably many strong partial clones between pPol(R 01 1/3 ) and pPol(R =01 1/3 ), pPol(R =01 1/3 ) and pPol(R = =01 1/3 ), and pPol(R = =01 1/3 ) and pPol(R = = =01 1/3

) [START_REF] Lagerkvist | A Preliminary Investigation of Satisfiability Problems Not Harder than 1-in-3-SAT[END_REF]. This was later refined by Couceiro et al. [START_REF] Couceiro | On the interval of Boolean strong partial clones containing only projections as total operations[END_REF] where it was proven that one can actually construct a family of strong partial clones of continuum size between each of these pairs.

D. The Non-Existence of Minimal Strong Partial Clones

We now turn to the question of minimal strong partial clones in I Str (J {0,1} ), i.e., pPol(Γ) ∈ I Str (J {0,1} ) such that pPol(Γ) ⊃ Str(J {0,1} ) but there does not exist pPol(∆) ∈ I Str (J {0,1} ) such that pPol(Γ) ⊃ pPol(∆) ⊃ Str(J {0,1} ). The existence of a minimal element pPol(Γ) would have interesting consequences in the light of the SETH, in particular if if T(Γ) < 1, since SAT(Γ) would then belong to the class of "hardest" NP-complete SAT problems which are still easier than the unrestricted SAT problem. However, this question has a surprisingly straightforward resolution, as proven by Couceiro et al. [START_REF] Couceiro | On the lower part of the lattice of partial clones[END_REF]: there are no minimal strong partial clones. More specifically, for each k (k > 1) it is proven that if f ∈ Str(J k ) then the strong partial clone [f ] s contains a family of strong partial subclones of continuum cardinality. Two slightly different constructions are needed depending on whether f is constant (i.e., there exists x ∈ k such that f (α i ) = x for all α i ∈ dom(f )) or not, and we provide a sketch of the latter construction.

Let f be an n-ary partial operation not in Str(J k ) and not constant. In the sequel we assume that the partial operation f is n-ary and with domain α 1 , . . . , α m ∈ k n , where α i := (a i 1 , . . . , a i n ), and we let A be the m × n matrix whose rows are α 1 , . . . , α m . Let us first define the following. Let Col(A) be the set of columns of A, and

v f = f (A) ∈ k m . For x := (x 1 , . . . , x h ) ∈ k h and ≥ 1, let x × ∈ k h be x × = (x 1 , . . . ,
X = {x 1 < • • • < x |X| } and a ∈ X, let next X (a) ∈ X be defined by next X (a) := x i+1 if a = x i and i < |X|, x 1 if a = x |X| . Furthermore, for x = (x 1 , . . . , x h ) ∈ [v f ] h and 1 ≤ i ≤ h, let c i (x) be the tuple c i (x) := (x 1 , . . . , x i-1 , next [v f ] (x i ), x i+1 , . . . , x h ).
Since the partial operation f is non-constant, the set [v f ] contains at least two different elements, and so c i (x) = x for all x ∈ [v f ] h and all i = 1, . . . , h. Let t ≥ 0 be the number of columns u ∼ in the matrix A that satisfy

[u ∼ ] = [v f ].
Without loss of generality, assume that all those t columns (if any) are the first columns to the left of A.

For each ≥ 1, define the relation ρ of arity d f by

ρ := {c i (v × f ) | 1 ≤ i ≤ d f } ∪ {u ∼ × | u ∼ ∈ Col(A)}. Notice that |ρ | = d f + n.
Let M be the matrix with d f rows, whose ( d f + n) columns are the tuples of ρ in the following order:

c 1 (v × f ), . . . , c d f (v × f ), u ∼ 1 × , . . . , u ∼ n × ,
where u ∼ 1 , . . . , u ∼ n are the columns of A written in the same order as they appear in A. By f × we denote the ( d f + n)-ary partial operation whose domain is the set of all rows of M and defined by

f × (M ) = v × f . Notice that for every x = (x 1 , . . . , x d f +n ) ∈ dom(f × ), we have that x 1 , . . . , x d f +t ∈ [v f ]. Example 5: Let k = {0, 1, 2}, = 3 and f   0 0 0 1 0 1 0 0 2   =   0 0 1   .
Then v f = (0, 0, 1), v ×3 f = (0, 0, 0, 0, 0, 0, 1, 1, 1),

A =   0 0 0 1 0 1 0 0 2   , Col(A) = {(0, 1, 0) T , (0, 0, 0) T , (0, 1, 2) T }, and f ×3 (M 3 ) = f ×3              
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1

1 1 1 1 1 1 0 1 1 0 0 2 1 1 1 1 1 1 1 0 1 0 0 2 1 1 1 1 1 1 1 1 0 0 0 2               =               0 0 0 0 0 0 1 1 1               .
This construction yields the following results. Lemma 11 ([16]):

For every ≥ 1, f × ∈ [f ] s . Moreover, for ≥ 1, f × ∈ pPolρ iff = .
Corollary 12: Let C be a strong partial clone on k and suppose that C contains a partial operation f ∈ Str(J k ) that is not a constant operation. Then the set of strong partial clones contained in C is of continuum cardinality.

V. OPEN QUESTIONS

The study of fine-grained complexity is still in its infancy and we have only concentrated a handful of results relevant in the context of partial polymorphisms. Now we present a few concrete questions arising from the results presented thus far.

On the non-existence of minimal strong partial clones: We provided a sketch of the construction from Couceiro et al. [START_REF] Couceiro | On the lower part of the lattice of partial clones[END_REF], which shows that there for any non-constant f / ∈ Str(J {0,1} ) exists g / ∈ Str(J {0,1} ) such that [g] s ⊂ [f ] s . Assuming T(Inv({f })) < 1, can this construction be used to find g such that T(Inv({f })) < T(Inv({g}))?

Maximal elements of I Str (J k ): We have seen that I Str (J {0,1} ) has a largest element pPol(R = = =01 1/3 ), resulting in the "easiest NP-complete SAT problem" SAT({R = = =01 1/3 }). Given the non-existence of minimal strong partial clones one might be sceptical about the existence of maximal elements of I Str (J {0,1} ). However, such elements do in fact exist, one can for example prove that pPol({R = = =01 , {(1)}), implying that these elements are not interesting from a complexity theoretical point of view. This raises the question of whether there exists a maximal element pPol(Γ) of I Str (J {0,1} ) such that T({R = = =01 1/3 }) < T(Γ).

Strong Maltsev conditions and partial polymorphisms:

Lagerkvist & Wahlström [START_REF] Lagerkvist | Which NP-hard SAT and CSP problems admit exponentially improved algorithms?[END_REF] propose a usage of partial polymorphisms which is similar to how strong Maltsev conditions are used to characterize the classical complexity of CSPs. For example, given the identities defining a Maltsev operation m(x, x, y) ≈ y, m(x, y, y) ≈ x one for every k we can define a partial operation f such that dom(f ) = {(x, x, y), (x, y, y) | x, y ∈ k} and such that f (x, x, y) = y and f (x, y, y) = x for all values where it is defined. The operation f is then called a partial Maltsev operation. The objective is then, given a partial operation f constructed in this manner, to construct an algorithm for CSP(Inv(f )) with a running time better than O(k n ). Surprisingly, this is indeed possible for the partial Maltsev operation, where one obtains the upper bound O(k n 2 ). An interesting continuation to this line of research is to consider the identities defining near unanimity operations and edge operations, and investigate if similar improved bounds can be obtained for the corresponding partial operations.

Definition 6 :

 6 [START_REF] Schnoor | Partial polymorphisms and constraint satisfaction problems[END_REF] Let C = Pol(Γ) be a clone over k where Γ is finite. A set of relations Γ w ⊆ Rel k is said to be a weak base of Inv(C) if (1) Pol(Γ w ) = C and (2) pPol(∆) ⊆ pPol(Γ w ) for each set ∆ ⊆ Rel k such that Pol(∆) = C.

1 / 3 , 3 , 3 }

 1333 {(0)}}) and pPol({R = = =01 1/{(1)}}) are both maximal elements. The caveat here is that T ({R = = =01 1/

  and let [x] = {x 1 , . . . , x h }. For a set X ⊆ k with

	x 1	, x 2 , . . . , x 2	, . . . , x h , . . . , x h	),
	times	times	times

For f, g ∈ Par(k), g is a suboperation of f , g ≤ f , if g = f | dom(g). For F ⊆ Par(k), we denote its closure under taking suboperations by Str(F ).

We follow the standard terminology where minimal/maximal clones are those directly above/below the greatest/least element in the clone lattice.


Rémi Giraud

Vinh-Thong Ta

Nicolas Papadakis

Yannick Berthoumieu

TEXTURE-AWARE SUPERPIXEL SEGMENTATION

Keywords: Superpixels, Texture, Patch, Segmentation

Most superpixel algorithms compute a trade-off between spatial and color features at the pixel level. Hence, they may need fine parameter tuning to balance the two measures, and highly fail to group pixels with similar local texture properties. In this paper, we address these issues with a new Texture-Aware SuperPixel (TASP) method. To accurately segment textured and smooth areas, TASP automatically adjusts its spatial constraint according to the local feature variance. Then, to ensure texture homogeneity within superpixels, a new pixel to superpixel patch-based distance is proposed. TASP outperforms the segmentation accuracy of the state-of-the-art methods on texture and also natural color image datasets.

INTRODUCTION

Superpixel segmentation approaches that locally group pixels into regions have become very popular in image processing and computer vision applications. The aim is to exploit the local redundancy of information to lower the computational burden and to potentially improve the performances by reducing the noise of a processing at the pixel level. Superpixels can also be considered as a multi-resolution approach that preserves image contours, contrary to standard regular downsampling methods. It is thus a very interesting pre-processing for applications such as visual saliency estimation [START_REF] Liu | Superpixel-based spatiotemporal saliency detection[END_REF]2], data association across views [3], segmentation and classification [4, 5, 6] and object detection [7,8,9] or tracking [START_REF] Chang | A video representation using temporal superpixels[END_REF][START_REF] Reso | Temporally consistent superpixels[END_REF].

For the past years, most superpixel methods have tended to produce equally-sized regions with homogeneous pixels in terms of color. This paradigm is usually in line with the segmentation of a natural image objects, whose contours can be detected by color changes. Hence, to cluster the pixels into regions, state-of-the-art methods such as [12,13,14,15,16], only use distance terms in spatial and color (e.g., CIELab) spaces. In [17,18], more advanced feature spaces are defined to improve the segmentation performances. More recently, [19] proposes to consider contour information in the cluster-Preprint available at: https://arxiv.org/abs/1901.11111 ing to ensure the respect of the object boundaries. Nevertheless, such framework requires the need for prior contour detection, at the expense of a global higher complexity.

Most of these state-of-the-art methods only use the pixel information as clustering feature. Therefore, they can be severely impacted by high frequency contrast variations and fail to produce equally-sized regions having the same textural properties. The proposed method TASP is compared in Figure 1 to the state-of-the-art approaches on a synthetic texture image. While TASP produces a relevant segmentation, all other methods are highly misleaded by the texture patterns. We used the regularity parameters recommended by the authors for tunable methods [14,15,[START_REF] Yao | Realtime coarse-to-fine topologically preserving segmentation[END_REF]18,19], but no other setting would enable to capture texture information. Superpixel methods are indeed generally optimized and evaluated on noise-free natural color images, although specific tasks require to decompose highly textured or low resolution grayscale images, for instance in medical applications [START_REF] Tian | Superpixel-based segmentation for 3D prostate MR images[END_REF].

To overcome the limitations of handcrafted color spaces, deep learning approaches have been proposed [START_REF] Jampani | Superpixel sampling networks[END_REF][START_REF] Tu | Learning superpixels with segmentation-aware affinity loss[END_REF]. Nevertheless, the gain obtained with learned features on a training dataset may come at the expense of usual deep learning limitations, i.e., important learning time, need for a substantial training database and material resources, and direct applicability limited to similar images. Moreover, these approaches do not directly extend to supervoxels and prevent from setting the shape regularity, which can highly impact the performances of superpixel-based tasks. It is thus still necessary to increase the robustness of non-deep learning superpixel methods to textures, while preserving their desired properties: adaptability, low complexity and limited parameter settings.

Contributions. In this work, we propose a new Texture-Aware SuperPixel (TASP) clustering method able to accurately segment highly textured images, but also any input image, e.g., natural color ones, using the same parameters.

To be able to generate relevant superpixels on textured images (see Figure 1), TASP adjusts its spatial constraint, according to the feature variance within the superpixel. This way, TASP also addresses the need for fine manual regularity setting. Most recent state-of-the-art methods globally set this parameter according to the image nature, leading default or sub-optimal settings to highly impact the results [START_REF] Giraud | Evaluation framework of superpixel methods with a global regularity measure[END_REF]. Initial image ERS [12] SEEDS [13] SLIC [14] ERGC [15] ETPS [START_REF] Yao | Realtime coarse-to-fine topologically preserving segmentation[END_REF] LSC [18] SNIC [16] SCALP [19] TASP Fig. 1. Comparison of the TASP method to state-of-the-art approaches on a synthetic texture image for 100 superpixels. Only TASP succeeds in capturing the textures while other methods are highly misleaded by high frequency contrast variations.

Then, to ensure the texture homogeneity, we introduce a new patch-based framework enabling to easily evaluate the similarity of a pixel neighborhood to a superpixel.

We validate TASP on natural color images from a standard segmentation dataset [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF], and on two new datasets proposed to evaluate texture segmentation performances. TASP significantly outperforms the state-of-the-art methods on texture segmentation performances, while performing as well, or better, on natural images, using the same parameters.

TEXTURE-AWARE SUPERPIXELS

The TASP method improves the superpixel decomposition approach used in [14,18,19], that is first presented in this section. Then, we propose a method to locally set the spatial regularity of superpixels, to automatically adapt to the image content. Finally, we introduce a new pixel to superpixel texture homogeneity measure to group pixels in terms of texture.

K-means-based Iterative Clustering

The standard framework of [14] only requires the number of superpixels to produce and a regularity parameter. The algorithm is based on an iteratively constrained K-means clustering of pixels. Superpixels S i are first regularly set over the image domain as blocks of size s×s, and are described by their average intensity feature F Si (CIELab colors for [14]) and their spatial barycenter

X Si = [x i , y i ] of pixels in S i . The clustering relies on a feature d F (F p , F Si )= F p -F Si 2 , and a spatial distance term d s (X p , X Si )= X p -X Si 2 .
At each iteration, each superpixel S i is compared to all pixels p, of feature F p at position X p , within a (2s+1)×(2s+1) region around its barycenter X Si . A pixel p is associated to the superpixel S i minimizing the distance D defined as:

D(p, Si) = dF (Fp, FS i ) + ds(Xp, XS i ) m 2 s 2 , (1)
with m the parameter setting the superpixel shape regularity.

A post-processing step finally ensures region connectivity. Although this method can accurately gather pixels having similar colors, m is globally set and cannot adapt to all local image contours. It also highly fails to capture texture patterns, as it only considers feature information at the pixel level.

Local Adaptation of Superpixel Regularity

For most methods, including [14,18,19], the regularity parameter m must be manually set, according to the dynamic of the feature term d F . Hence, default parameters for natural color images may lead model (1) to generate highly irregular clustering on textures, and the post-processing step enforcing connectivity to irrelevantly merge regions (see Figure 1). We address this issue by using for each superpixel S i , a regularity parameter m i defined according to the feature variance σ i (F p ) of all pixels p ∈ S i such that:

mi = m exp σi(Fp) 2 β , (2)
with a scaling parameter β. Such regularity term m i is able to increase the spatial constraint in the TASP model (5) for superpixels having high feature variances, and to reduce it in smooth areas, so the superpixel boundaries can capture image objects that are perceptible from limited feature variations. This way, without manually adapting m in (2), TASP can compute relevant superpixels on both highly textured images (see Figure 2

Texture Homogeneity Measure

Pixel to Superpixel Patch-based Distance

In this section, we propose a method to measure the texture similarity between a pixel neighborhood and the content of a superpixel, thus between two regions of different sizes. A texture descriptor at patch and superpixel levels would yield higher complexity and additional parameter settings. Moreover, texture cannot be preserved as well as for color and spatial information with a global average over the whole superpixel. The framework must preserve its limited complexity, and to be able to adapt to any image content without any prior information. Such constraints also prevent from using costly dictionary or learning-based approaches.

To address these issues, we propose a new framework using square patches to naturally capture texture information. For a pixel p, of patch P (p), and a superpixel S i , a nearest neighbor algorithm (see section 2.3.2) is used to find similar patches P (p i ) such that p i ∈ S i , and outside a δneighborhood around p (see Figure 3). The new term d P computes the average distance to the selected p i ∈ S i :

dP (p, Si) = 1 N p i ∈Kp dP (p, pi), (3)
with K p the set of N selected pixels p i ∈ S i , compared with a patch distance in the feature space, such that d P (p, p i ) =

1 n F P (p) -F P (pi) ) 2 , with n the patch size. Any feature can be used in term (3). This way, we propose a general model that can easily evaluate the texture compliance of a pixel neighborhood to a superpixel, while leveraging the need for complex texture classification approaches.

Patch-based Nearest Neighbor Search

The search for similar patches can be performed by any nearest neighbor (NN) method. We choose to use PatchMatch, a fast iterative approximate-NN algorithm based on the propagation of good matches from adjacent neighbors [START_REF] Barnes | PatchMatch: A randomized correspondence algorithm for structural image editing[END_REF]. The computation of d P (p, S i ) can be directly performed for all pixels p in the (2s + 1)×(2s + 1) area around the barycenter X Si of S i . The algorithm being partly random, N patches in S i can be selected in parallel for each pixel p, to increase the robustness of the texture homogeneity term (3).

Texture Unicity within Superpixels

In the texture term (3), the patch similarity is computed regardless of any spatial information. Hence, a pixel p to cluster may find similar local textures in restricted areas, leading a superpixel to potentially group several textures (Figure 2(c)).

To ensure the texture unicity within a superpixel S i , we consider in d P the spatial distance between the selected patches P (p i ), at position X pi ∈ S i , and X Si , the spatial barycenter of the superpixel S i such that:

dP (p, pi) = 1 n F P (p) -F P (p i ) ) 2 + m 2 i s 2 Γ Xp i , XS i , (4)
with Γ, a scaling function defined such that Γ(X pi , X Si ) = 2s 2 (1 -exp (-X pi -X Si 2 2 /s 2 )). Such term iteratively contributes to restrict the search area and the diversity of textures within S i by highly penalizing similar patches found far from X Si . Hence, the barycenter is encouraged to move to a homogeneous textured area and to be contained within the superpixel (see Figure 2(d)). This also increases the shape regularity, which is a desirable property [START_REF] Giraud | Evaluation framework of superpixel methods with a global regularity measure[END_REF].

The clustering distance in TASP is finally computed as:

D(p, Si) = dF (Fp, FS i ) + ds(Xp, XS i ) m 2 i s 2 + dP (p, Si). (5)
This way, TASP becomes a very general method, able to handle textures, and efficient on various image types with the exact same parameters, as demonstrated in the next section.

RESULTS

Validation Framework

Similarly to [START_REF] Randen | Filtering for texture classification: A comparative study[END_REF], we create two new datasets to evaluate texture segmentation performances. A highly challenging synthetic stripe (mix-Stripes) dataset of 10 images of size 300×400 pixels, is created by putting stripes similar to the ones in Figure 1, in variable shaped regions of minimum size 1000 pixels. Natural textures with normalized intensity are also taken from the Brodatz dataset [28], to create 100 composite images (mix-Brodatz), that can contain up to 10 different textures. Finally, we consider the standard Berkeley Segmentation Dataset (BSD) [START_REF] Martin | A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics[END_REF], containing 200 natural color test images of size 321×481 pixels. Most parameters are empirically set once and for all, and their tuning has a moderate impact on performances. For the patch search, N = 8 patches of size 5×5 pixels are selected outside a δ = 3 neighborhood. In the clustering model, m is set to 0.1 and β to 25 in (2). Color features F are computed as in [19]. Finally, the whole clustering process of TASP is performed in 10 iterations as in [14].

TASP is compared to the recent state-of-the-art methods SLIC [14], ERGC [15], ETPS [START_REF] Yao | Realtime coarse-to-fine topologically preserving segmentation[END_REF], LSC [18], SNIC [16], and SCALP [19]. Performances are evaluated with standard Achievable Segmentation Accuracy (ASA), and contour detection metric F-measure (F) as defined in [START_REF] Giraud | Evaluation framework of superpixel methods with a global regularity measure[END_REF], and we report quantitative results for an average number of 250 superpixels.

LSC [18] SNIC [16] SCALP [19] TASP

Influence of Contributions

The visual impact of contributions is shown in Figure 2, and ASA and F measures are reported in Table 1 on the three considered datasets. Our new texture homogeneity term (3) and constraint of texture unicity within superpixels (4) both significantly improve performances on each data type.

Comparison to the State-of-the-Art Methods

TASP is compared to state-of-the-art approaches on an image similar to the mix-Stripes dataset in Figure 1, and to the most recent methods on mix-Brodatz and BSD images in Figure 4. A quantitative evaluation is also performed on the three datasets in Table 2. TASP significantly increases the performances on the synthetic (mix-Stripes) and natural (mix-Brodatz) texture datasets, demonstrating its ability to provide texture-aware superpixels. TASP also obtains the best results on natural color images (BSD), using the same parameters, while other methods fail at providing accurate results on the three data types at the same time. Note that compared methods are used with parameters recommended by the authors.

Nevertheless, no other approach explicitly captures texture information, so TASP with default parameters still outperform state-of-the-art methods manually optimized for each dataset. 0.7256 0.4048 0.7784 0.4607 0.9445 0.4706 ERGC [15] 0.6107 0.3717 0.7796 0.4677 0.9477 0.4571 ETPS [START_REF] Yao | Realtime coarse-to-fine topologically preserving segmentation[END_REF] 0.7769 0.2953 0.7568 0.4354 0.9433 0.4710 LSC [18] 0.6979 0.3156 0.7908 0.4552 0.9503 0.4421 SNIC [16] 0.6659 0.3529 0.7662 0.4815 0.9410 0.4617 SCALP [19] 0.7307 0.3290 0.7977 0.4759 0.9499 0.4914 TASP 0.8706 0.4232 0.8139 0.4824 0.9503 0.4992

Table 2. TASP compared to the state-of-the-art methods.

Best and second results are respectively bold and underlined.

CONCLUSION

In this paper, we address the severe non-robustness of superpixel approaches to texture images by proposing a textureaware decomposition method. A new patch-based framework is introduced to gather pixels having both similar color and local textural properties. The proposed method is general, removes the need for manual setting of regularity constraint, and also naturally can extend to generate supervoxels. We outperform the segmentation of state-of-the-art methods on color, and synthetic and natural texture datasets, by using the same parameters. This work opens the way for larger use of superpixels and efficient application of our approach to medical image segmentation or video object tracking.

  Fig.2. SLIC[14] with optimal regularity for color images (a) vs TASP contributions (b)-(d), that accurately decomposes both texture and color images with the same parameters (d).

  (b)-top), and natural color ones (see Figure 2(b)bottom), since m i (2) automatically adjusts the trade-off between d F and d s in (5). Nevertheless, the clustering accuracy still has to be improved to capture texture information.

Fig. 3 .

 3 Fig. 3. Selection of similar patches P (p i ) in a superpixel S i of barycenter X Si , outside a δ-neighborhood, to compute the texture homogeneity term (3) for a patch P (p).

Fig. 4 .

 4 Fig. 4. Comparison between TASP and most recent state-of-the-art methods. TASP produces a more relevant result on a natural texture composite image (top) and on a natural color image example from the BSD (bottom), for 200 superpixels.

Table 1 .

 1 Influence of contributions in the TASP method.

		mix-Stripes	mix-Brodatz	BSD
	Method	ASA	F	ASA	F	ASA	F
	TASP w/o (3),(4) 0.8303 0.3498 0.7969 0.4736 0.9484 0.4945
	TASP w/o (4)	0.8486 0.3882 0.8112 0.4812 0.9493 0.4961
	TASP	0.8706 0.4232 0.8139 0.4824 0.9503 0.4992