Claudette Cayrol

Andrea Cohen

M-Christine Lagasquie-Schiex

Towards a New Framework for

Keywords: Abstract argumentation, bipolar argumentation, recursive interactions

.

Introduction

Argumentation has become an essential paradigm especially for reasoning from contradictory information [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF][START_REF] Amgoud | A reasoning model based on the production of acceptable arguments[END_REF], and for formalizing the exchange of arguments between agents in, e.g., negotiation [START_REF] Amgoud | Modelling dialogues using argumentation[END_REF]. Formal abstract frameworks have greatly eased the modelling and study of argumentation. For instance, a Dung's argumentation system (AS) [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] consists of a collection of arguments interacting with each other through an attack relation, enabling to determine "acceptable" sets of arguments called extensions.

In the last decade, extensions of Dung's AS were proposed for including a positive interaction between arguments, called support. The support relation has been rst introduced in [START_REF] Karacapilidis | Computer supported argumentation and collaborative decision making: the HERMES system[END_REF][START_REF] Verheij | De og: on the logical interpretation of prima facie justi ed assumptions[END_REF]. In [START_REF] Cayrol | On the acceptability of arguments in bipolar argumentation frameworks[END_REF], the support relation is left general so that the obtained bipolar AS (BAS) keeps a high level of abstraction. However there is no single interpretation of support, and a number of researchers proposed specialized variants of the support relation (deductive support [START_REF] Villata | Modelling defeasible and prioritized support in bipolar argumentation[END_REF], necessary support [START_REF] Nouioua | Argumentation frameworks with necessities[END_REF], evidential support [START_REF] Oren | Moving between argumentation frameworks[END_REF]). Each specialization was developed quite independently, based on different intuitions and provided with an appropriate formalization. In order to restate those proposals in a common setting, [START_REF] Cayrol | Bipolarity in argumentation graphs: towards a better understanding[END_REF] proposed a comparative study using the BAS. Following the same line, recent works have been proposed that enforce the important role of necessary support (see e.g., [START_REF] Polberg | Revisiting support in abstract argumentation systems[END_REF][START_REF] Prakken | On support relations in abstract argumentation as abstraction of inferential relations[END_REF][START_REF] Cayrol | An axiomatic approach to support in argumentation[END_REF][START_REF] Nouioua | AFs with necessities: further semantics and labelling characterization[END_REF]). Another line of work extending Dung's AS regards high-order attacks: attacks to the attack relation [START_REF] Modgil | Reasoning about preferences in argumentation frameworks[END_REF][START_REF] Baroni | AFRA: Argumentation framework with recursive attacks[END_REF] and attacks to attacks and supports [START_REF] Villata | Modelling defeasible and prioritized support in bipolar argumentation[END_REF]. More generally, [START_REF] Cohen | An approach to abstract argumentation with recursive attack and support[END_REF] proposes an Attack-Support Argumentation Framework (ASAF) which allows for attack and support to the attack and support relations, at any level.

The authors in [START_REF] Cohen | An approach to abstract argumentation with recursive attack and support[END_REF] encode an ASAF by turning it into a BAS with necessary support, and then into an AS by adding extended attacks. As [START_REF] Cayrol | An axiomatic approach to support in argumentation[END_REF] presents different frameworks for encoding necessary support, it is interesting to enrich them with recursive interactions. So, in this paper we propose to translate the ASAF into a special AS using metaarguments2 (called MAS), and compare this MAS with the AS obtained in [START_REF] Cohen | An approach to abstract argumentation with recursive attack and support[END_REF]. Note that our aim is not to replace the ASAF with the MAS; although recursive interactions can be modelled using the MAS, the ASAF is a more intuitive and visual representation tool.

This paper is organized as follows: BAS (with necessary support) and its axiomatization are presented in Sect. 2. Background on the ASAF is given in Sect. 3. In Sect. 4 we extend the MAS proposed in [START_REF] Cayrol | An axiomatic approach to support in argumentation[END_REF] to model recursive interactions. Then, Sect. 5 compares this MAS with the ASAF. Finally, Sect. 6 concludes and suggests lines of future work.

Bipolar abstract argumentation system

The abstract bipolar argumentation system presented in [START_REF] Cayrol | On the acceptability of arguments in bipolar argumentation frameworks[END_REF][START_REF] Cayrol | Coalitions of arguments: a tool for handling bipolar argumentation frameworks[END_REF] extends Dung's AS [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] by adding a positive interaction between arguments: the support relation. S is admissible iff it is con ict-free and ∀b ∈ S, b is acceptable wrt S. S is a preferred extension of AS iff it is a maximal (wrt ⊆) admissible set.

Def. 1 (BAS) A bipolar argumentation system (BAS) is a tuple

A, R att , R sup ,
Handling support and attack at an abstract level has the advantage to keep genericity and to give an analytic tool for studying complex attacks and new semantics considering both attack and support relations, among others. However, the drawback is the lack of guidelines for choosing the appropriate de nitions and semantics depending on the application. For solving this problem, some variants of the support relation have been proposed recently, including the necessary support. This kind of support was initially proposed in [START_REF] Nouioua | Argumentation frameworks with necessities[END_REF] with the following interpretation: If cR sup b then the acceptance of c is necessary to get the acceptance of b, or equivalently the acceptance of b implies the acceptance of c. Suppose now that aR att c. The acceptance of a implies the non-acceptance of c and so the non-acceptance of b. Also, if cR sup a and cR att b, the acceptance of a implies the acceptance of c and the acceptance of c implies the non-acceptance of b. So, the acceptance of a implies the non-acceptance of b. These constraints relating a and b are enforced by adding new complex attacks from a to b:

Def. 3 ([13] Extended attack) Let BAS = A, R att , R sup .
There is an extended attack from a to b iff either (1) aR att b; or (2) a 1 R att a 2 R sup . . . R sup a n , n ≥ 3, with a 1 = a, a n = b; or (3) a 1 R sup . . . R sup a n , and a 1 R att a p , n ≥ 2, with a n = a, a p = b. Graphically: Among the frameworks proposed in [START_REF] Cayrol | An axiomatic approach to support in argumentation[END_REF] for handling necessary supports, we focus on the one encoding the following interpretation: If cR sup b, "the acceptance of c is necessary to get the acceptance of b" because "c is the only attacker of a particular attacker of b":

Def. 4 ([7] MAS associated with a BAS) Let BAS = A, R att , R sup with R sup being a set of necessary supports. Let A n = {N cb |(c, b) ∈ R sup } and R n = {(c, N cb )|(c, b) ∈ R sup } ∪ {(N cb , b)|(c, b) ∈ R sup }. The tuple MAS = A ∪ A n , R att ∪ R n
is the metaargumentation system associated with BAS (it is a Dung's AS).

Recursive interactions

Recursive interactions were explored in [START_REF] Baroni | AFRA: Argumentation framework with recursive attacks[END_REF] for recursive attacks (the AFRA) and in [START_REF] Cohen | An approach to abstract argumentation with recursive attack and support[END_REF] for recursive supports plus attacks (the ASAF). The idea is to model that the validity of an interaction may depend on other interactions (e.g., because of preferences [START_REF] Modgil | Reasoning about preferences in argumentation frameworks[END_REF]). Here we focus on the ASAF [START_REF] Cohen | An approach to abstract argumentation with recursive attack and support[END_REF], where arguments interact with other arguments or interactions:

Def. 5 (ASAF) An Attack-Support Argumentation Framework (ASAF) is a tuple A, R att , R sup where A is a set of arguments, R att ⊆ A × (A ∪ R att ∪ R sup ) is an attack relation, and R sup ⊆ A × (A ∪ R att ∪ R sup ) is a necessary support relation. Note that R sup
is assumed to be irre exive and transitive. We assume that R att ∩ R sup = ∅.

[8] translates an ASAF into an AS in two steps: rst, the ASAF is turned into a BAS with necessary support; then, this BAS is turned into an AS by adding extended attacks. For the rst step, the following schemas describe the translation of the 4 basic cases:

ASAF Associated BAS ASAF Associated BAS a c b β α a α c b β a c b β α a α + α - c b β a c b β α a α c b β + β - a c b β α a α + α - c b β + β -
Given the BAS associated with the ASAF, the second step followed in [START_REF] Cohen | An approach to abstract argumentation with recursive attack and support[END_REF] is to create an AS by adding complex attacks, namely Case 2 -extended attacks (see Def. 3):

Def. 6 (AS associated with BAS and with ASAF)

Let BAS = A, R att , R sup be the BAS associated with ASAF. The pair AS ′ = A ′ , R ′ , where A ′ = A and R ′ = R att ∪ {(a, b)| there is a sequence a 1 R att a 2 R sup . . . R sup a n , n ≥ 3, with a 1 = a, a n =
b} is the AS associated with BAS and ASAF.

Encoding recursive interactions in MAS

In this section, we propose to use the MAS (see Sect. 2) for encoding recursive interactions, addressing the following issues:

• distinguish between labelled and unlabelled interactions, i.e. between interactions that may be involved in a recursion (either as a target, or as targeting another interaction) and the other interactions; • encode labelled interactions, i.e. the ability to reason about them; and • encode recursive interactions, i.e. the impact of an interaction on another one.

For this purpose, we need to formalize the notion of labelled interaction. So we propose a slightly modi ed version of the ASAF, which we call the labelled ASAF.

Def. 7 (Labelled ASAF)

A labelled ASAF is a 5-uple A, R att , R sup , V , L where A is a set of arguments, R att ⊆ A × (A ∪ R att ∪ R sup ) is an attack relation, R sup ⊆ A × (A ∪ R att ∪R sup ) is a necessary support relation, V is a set of labels (denoted by greek letters) and L is a bijection from R ⊆ (R att ∪ R sup ) to V . We still assume that R att ∩ R sup = ∅.
The above de nition enables to distinguish interactions that are not involved in a recursion; they may be considered as always "valid" and will be called "basic" in the following. Since the aim of labels is to enable reasoning about interactions and encode recursive interactions, basic interactions do not require labels. 4 Moreover, each label corresponds to a unique labelled interaction and vice-versa. The main difference between Def. 7 and Def. 5 is the explicit integration of labels into the ASAF. In the following, a labelled interaction will be confused with its label. In order to de ne the MAS associated with a labelled ASAF, next we explain the encoding of each component of the ASAF. Encoding basic attacks/supports. Such interactions correspond to unlabelled interactions and can be directly encoded using the MAS given in [START_REF] Cayrol | An axiomatic approach to support in argumentation[END_REF] (see Def. 4). Encoding labelled interactions. In order to reason about an interaction that is attacked or supported we must be able to refer to it; hence, it must be labelled and its label will be used as a "meta-argument". A labelled interaction α = (a, b) encompasses two types of links. One link relates α to b, representing the role of α (either an attack or a support), and will be called the effect-link. The other link relates α to its source a, representing the grounding of α, and will be called the ground-link. The idea of "grounded" interaction is close to the notion of evidential argumentation in the work of [START_REF] Oren | Moving between argumentation frameworks[END_REF][START_REF] Polberg | Revisiting support in abstract argumentation systems[END_REF]. It means that "an interaction makes sense only if its source argument is accepted".

These two links suggest two kinds of validity for the interaction. We reserve the term validity for the effect-link. For instance, in a graph containing only α attacked by b (through an attack β = (b, α)), α is not valid. Similarly, if α is supported by c (with a support γ = (c, α)) and c is attacked by d, then α is not valid. Concerning the groundlink, we use the term grounded. For instance, α = (a, b) is not grounded if a is attacked and not defended. Note that a support can be valid even though its source is not accepted. So interactions may be valid and not grounded, or grounded and not valid. We call active an interaction which is both valid and grounded. Intuitively, if α is only attacked by a non-active interaction (whatever the origin of this non-activation), then α should be valid. If α is supported by an interaction β which is valid but not grounded, then α should not be valid. However, if β is not valid, the validity of α cannot be affected by β . The following table synthetizes the above notions for a labelled interaction α = (a, b). The ground-link is a necessary support between the meta-argument and the source argument; thus, an interaction α = (a, b) will be "grounded" only if a is accepted. This support is basic since it is not defeasible. The effect-link of an attack (resp. a support) α = (a, b) is a basic attack (resp. support) from α to b. We encode a labelled interaction α with basic interactions since an attack (or a support) to α will be encoded by attacks (supports) to the meta-arguments that are introduced. So, a labelled attack α = (a, b) is encoded by a=⇒α-→b and a labelled support β = (c, d) is encoded by c=⇒β =⇒d. That is, a labelled interaction is encoded in two steps: rst, a meta-argument is introduced with a basic support from its source (ground-link) and a basic attack or support to its target (effect-link); then, the basic supports are encoded in MAS (see Sect. 2). So, α (resp. β ) is encoded in the MAS by a-→N aα -→α-→b (resp. c-→N cβ -→β -→N β d -→d). Encoding recursive interactions. Our aim is to encode an attack (resp. a support) on a labelled interaction through attacks (resp. supports) on the meta-arguments associated with it (the labels and the N i j , see the previous paragraph). However, every metaargument does not play the same role and a deeper analysis is needed in order to identify the meta-arguments that will be affected by the recursive interaction. Let α = (a, b) and β = (c, α) be two labelled interactions. We discuss their encoding on two cases, with two sub-cases each, considering the intuitively desirable preferred extension of the MAS denoted by E. All these cases will be synthetized in Def. 8. Case 1: α is an attack. Encoding α produces the meta-arguments α and N aα .

• Case 1.1: α is attacked by β . In this case, E should be {a, c, β , b}. So a and c are accepted, β is active, α is not active (it is grounded but not valid) and b can be accepted; this result holds whatever the status of a. Now, if c is attacked by d (with a basic attack) E should be {a, d, N cβ , α}, which corresponds to the set {a, d, α}5 after removing the meta-argument N cβ . Since c is not accepted β is not grounded nor active, and α can be valid. Also, since a is accepted α is grounded, thus active. So a and b cannot belong to the same extension.

• Case 1.2: α is supported by β . E should be {a, c, β , α}. So a and c are accepted, β and α are active and thus, b cannot be accepted. Now, if c is attacked by d (with a basic attack), E should be {a, d, N cβ , N β α , b}, which corresponds to the set {a, d, b} after removing the meta-arguments N cβ and N β α . Since c is not accepted, β is not grounded. Furthermore, since β is valid, α is not valid nor active. Thus, a and b can belong to the same extension (whatever the status of a). Case 2: α is a support. Encoding α produces the meta-arguments α, N aα and N αb .

• Case 2.1: α is attacked by β . If β is active, then α is not valid; this is captured by an attack from the meta-argument β to the meta-argument N αb . Thus, α is not active, captured by an attack from β to α in MAS. If β is not active (e.g., if c is attacked) and β is the only interaction that impacts α, then α is valid; hence, b is accepted implies a is accepted. If a is attacked by e (with a basic attack), E should be {e, c, N aα , β , b}, which corresponds to the set {e, c, β , b}. Since c is accepted, β is grounded. Moreover, β is valid and so active. Therefore, α is not valid nor active and b (not being attacked) can be accepted even though a is not accepted. Note that the presence of N aα in E means that α is not grounded. Moreover, if c is attacked by d (with a basic attack), E should be {e, d, N aα , N cβ , N αb }, which corresponds to the set {e, d}. Now, c is not accepted; so β is not grounded nor active, and α is valid. However, since a is not accepted, α is not grounded nor active and b cannot be accepted. Lastly, if we remove the attack on a by e, E should be {a, d, α, N cβ , b}, which corresponds to {a, d, α, b}. c is not accepted, β is not grounded nor active, and α is valid. Also, α is grounded (thus active), so a and b are accepted.

• Case 2.2: α is supported by β . If β is valid and not grounded, then α is not valid nor active; this is captured by attacks from N β α to N αb and α in MAS. If a is attacked by e and c by d (with basic attacks), E should be {e, d, N aα , N cβ , N β α , b}, which corresponds to the set {e, d, b}. Since c is not accepted, β is not grounded nor active. Then, α is not valid (nor active) and b can be accepted even though a is not accepted.

Def. 8 (Attacked or supported attacks/supports in MAS)

The following schemas describe the encoding of an attacked (resp. supported) attack/support in a MAS.

Labelled ASAF Associated BAS Associated MAS Case 1.1: a b c α β a α b c β a N aα α b c N cβ β Case 1.2: a b c α β a α b c β a N aα α b c N cβ β N β α Case 2.1: a b c α β a α b c β a N aα α N αb b c N cβ β Case 2.2: a b c α β a α b c β a N aα α N αb b c N cβ β N β α
Given a labelled interaction α = (a, b) and an extension E, the following cases can occur: Let us now consider a labelled support α = (a, b). The rst step of the ASAF approach (Sect. 3) produces a=⇒α + -→α --→b, where two meta-arguments are used for representing the support α. In contrast, the rst step of the MAS approach (Sect. 4) produces a=⇒α=⇒b, where only one meta-argument is created for representing α. However, when encoding α=⇒b, the second step of the MAS approach will produce α-→N αb -→b. So α (resp. N αb ) in the MAS plays the role of α + (resp. α -) in the asso- ciated BAS of the ASAF. Indeed, they mainly differ in the encoding of the ground-link.

The second step produces different AS. The ASAF approach handles the remaining supports through extended attacks. Thus, since by Def. 6 no extended attacks are added, a=⇒α + -→α --→b is turned into: a α + α - b and the preferred extension of the AS is {a, α + , b}, which corresponds to {a, α, b} in the ASAF. In contrast, the MAS approach handles both supports by creating meta-arguments (according to Def. 4). So a=⇒α=⇒b is turned into: a N aα α N αb b and the preferred extension of MAS (and BAS) is {a, α, b}.

Note that, in the ASAF approach, the resulting AS has no connection between the source a and the meta-arguments associated with α. Differently, the MAS links a and α with a sequence of attacks going through the meta-argument N aα . This is because the ASAF approach does not treat all supports in the same way, whereas the MAS approach provides a uni ed handling through the addition of meta-arguments.

Let us now consider a labelled ASAF represented by c β -→a α =⇒b. On the one hand, following the ASAF approach, the associated BAS is c=⇒β -→a=⇒α + -→α --→b. By Def. 6, there is an extended attack from β to α + . So the resulting AS is:

c β a α + α -
b and the preferred extension of the AS is {c, β , α -}, which is mapped into {c, β , α} in the ASAF. Since the ASAF approach deems all interactions as labelled, the resulting AS can be uselessly complex. To address this issue, the MAS approach offers two alternatives: • If interactions are always labelled (even though they are not involved in a recursion) the associated BAS is c=⇒β -→a=⇒α=⇒b, and the resulting AS is:

c N cβ β a N aα α N αb b
{c, β , N aα , N αb } is the preferred extension of MAS, corresponding to {c, β } in BAS.

• If labels are only used for reasoning about interactions involved in a recursion, we can directly apply Def. 4 to obtain a simpler system: c a N ab b

Here, the preferred extension is {c, N ab }, corresponding to the extension {c} of the BAS.

A main difference between both approaches regards the presence of interactions in their extensions. Every interaction in an extension of a MAS is active (grounded and valid). In contrast, the meaning ascribed by the ASAF approach differs in the case of attacks and supports. As in the MAS approach, the presence of an attack in the extension obtained by the ASAF approach means that this attack is active. This is because the ASAF approach condenses the validity and groundess of an attack α through the metaargument α. However, by combining these features, it does not allow to easily identify situations in which α is not grounded but valid (or vice-versa). On the other hand, if a support β belongs to an extension of the ASAF, we can only assure that it is valid. This is because β is represented by meta-arguments β +/-in the associated AS, which also capture the groundness (resp. non-groundness) of the support. As a result, the MAS approach is more exible than the ASAF because of handling the different features of an interaction separately. Also, it ascribes the same meaning to the presence of every interaction in its extensions, in contrast with the ASAF.

Conclusion and future works

We have introduced a new framework for handling recursive interactions in bipolar argumentation systems, extending the work of [START_REF] Cohen | An approach to abstract argumentation with recursive attack and support[END_REF]. Our study addresses the following issue: "How can the validity of an interaction be affected if this interaction is attacked or supported by another one?". Drawing on examples, we identi ed different kinds of validity of interactions (namely the notions of "grounded interaction", "valid interaction" and "active interaction"). Then, we proposed a new method for attening an ASAF using meta-arguments. The comparison with the original approach of [START_REF] Cohen | An approach to abstract argumentation with recursive attack and support[END_REF] highlights the similarities and differences between the frameworks, and con rms the choices given in [START_REF] Cohen | An approach to abstract argumentation with recursive attack and support[END_REF].

Encodings of attacks and supports through meta-arguments can be found in [START_REF] Villata | Modelling defeasible and prioritized support in bipolar argumentation[END_REF] for the purpose of representing second-order attacks. Our work goes further since the MAS enables to represent attack and support to both attack and support relations, at any level.

Our study has been essentially carried out from examples. So it opens several lines for future work: give a formal proof of the intuitions behind the meaning of the metaarguments; formally de ne the expected outcomes of our framework; and compare more deeply our proposal with the existing works, particularly in terms of outcomes.

3 Def. 2 (

 32 where A is a nite and non-empty set of arguments, R att ⊆ A × A is an attack relation and R sup ⊆ A × A is a support relation. A BAS can be represented by a directed graph with two kinds of edges: ∀a, b ∈ A, aR att b (resp. aR sup b) is represented by a-→b (resp. by a=⇒b). Semantics introduced by Dung for AS can only be used if R sup = ∅. They characterize sets of arguments that satisfy some properties and some form of optimality. For instance: Preferred extensions of AS) Let AS = A, R att and S ⊆ A. S is con ict-free iff ∄a, b ∈ S, s.t. aR att b. a ∈ A is acceptable wrt S iff ∀b ∈ A s.t. bR att a, ∃c ∈ S s.t. cR att b.

  by interactions on α) ground-link describes the existence of α wrt a groundness (takes into account only the source of α) If an attack α = (a, b) is active, then a and b cannot belong to the same extension. And if a support α = (a, b) is active, then if b is accepted then a must be also accepted.

  ∈ E and N aα ∈ E: α is not active nor grounded. The validity of α depends on supporters and attackers of α present in E

	5. Comparison with ASAF
	Let us compare the ASAF and MAS approaches for encoding labelled and recursive
	interactions. Both approaches follow two steps. The rst step produces a BAS in both
	cases; however, they differ in the encoding of supports. Moreover, the second step is
	quite different. Let us rst consider the encoding of a labelled attack.
	Prop. 1 Let α = (a, b) be a labelled attack. The translation of α given in Sect. 3 is exactly
	the same as the one given in Sect. 4: a

support α α ∈ E: α is active and in that case N aα / ∈ E and N αb / ∈ E α / ∈ E and N aα / ∈ E: α is grounded but not active, so it is not valid α / ∈ E, N aα ∈ E and N αb ∈ E: α is not active, not grounded, but valid α / ∈ E, N aα ∈ E and N αb / ∈ E: α is not active, not grounded and not valid attack α α ∈ E: α is active and in that case N aα / ∈ E α / ∈ E and N aα / ∈ E: α is grounded but not active, so it is not valid α / α -→ b becomes a=⇒α-→b where α denotes a meta-argument associated with the attack (a, b).

A similar idea is presented in[START_REF] Villata | Modelling defeasible and prioritized support in bipolar argumentation[END_REF] for representing defeasible attacks and supports.

"iff" means "if and only if", "s.t." means "such that" and "wrt" means "with respect to".

Note that if all interactions are unlabelled (V = ∅), the labelled ASAF is reduced to a simple BAS.

This set could be considered as the extension of the labelled ASAF; however, since this paper reports only a preliminary study, the expected outcomes of the framework following our approach are not yet de ned.


Aldo Gonzalez-Lorenzo

Mateusz Juda

Alexandra Bac

Jean-Luc Mari

Pedro Real

Fast, Simple and Separable Computation of Betti Numbers on Three-dimensional Cubical Complexes

Keywords: Cubical complex, Betti numbers, 3D, separable, computational topology, homology

Betti numbers are topological invariants that count the number of holes of each dimension in a space. Cubical complexes are a class of CW complex whose cells are cubes of different dimensions such as points, segments, squares, cubes, etc. They are particularly useful for modeling structured data such as binary volumes. We introduce a fast and simple method for computing the Betti numbers of a three-dimensional cubical complex that takes advantage on its regular structure, which is not possible with other types of CW complexes such as simplicial or polyhedral complexes. This algorithm is also restricted to three-dimensional spaces since it exploits the Euler-Poincaré formula and the Alexander duality in order to avoid any matrix manipulation. The method runs in linear time on a single core CPU. Moreover, the regular cubical structure allows us to obtain an efficient implementation for a multi-core architecture.

Introduction

Understanding a discrete volume can be addressed by determining its volume, its convexity, its diameter or any other geometrical descriptor. A higher level analysis can be made through topology, which tolerates continuous deformations. This could be seen as a less interesting approach, as we could not distinguish a sphere from a cube, but it actually furnishes a more essential information of the object. Homology is a powerful tool as its formalizes the concept of hole.

Holes of dimension 0, or 0-holes, correspond to connected components. 1-holes are tunnels or handles, which are particularly difficult to count in a volume depending on their shape. 2-holes correspond to voids in a volume. These notions can be generalized to higher dimensions, but they do not have an intuitive interpretation. We can compute the number of holes in each dimension or even draw them on the volume, though this is not useful with a complex shape.

Homology can be used for understanding an object without visualizing it, or to compare objects in a flexible way. It has been applied to dynamical systems [START_REF] Mischaikow | Conley index theory[END_REF][START_REF] Mrozek | Index pairs algorithms[END_REF], material science [START_REF] Day | Verified homology computations for nodal domains[END_REF][START_REF] Teramoto | Morphological characterization of the diblock copolymer problem with topological computation[END_REF], electromagnetism [START_REF] Gross | Electromagnetic Theory and Computation[END_REF][START_REF] Lotko | Efficient cohomology computation for electromagnetic modeling[END_REF], image understanding [START_REF] Allili | Topological analysis of shapes using Morse theory[END_REF][START_REF] Mrozek | Homological methods for extraction and analysis of linear features in multidimensional images[END_REF] and sensor networks [START_REF] Dlotko | Distributed computation of coverage by homological methods[END_REF].

In this article we aim at counting the number of holes (the Betti numbers) of a cubical complex embedded in a three-dimensional space. This is far from being an abstract work, as binary volumes (3D binary images, with voxels instead of pixels) can be transformed into equivalent cubical complexes. Our algorithm has a very specific input, since it cannot treat meshes or higher dimension cubical complexes, but it benefits from a good time complexity (linear) and a wide range of applications where data is structured in a lattice.

There have been a lot of works in computational homology in the last decades. Many of them [START_REF] Munkres | Elements of algebraic topology[END_REF][START_REF] Harker | Discrete morse theoretic algorithms for computing homology of complexes and maps[END_REF][START_REF] Peltier | Computation of homology groups and generators[END_REF] can compute the homology groups of more general spaces in cubical time. Computing only the Betti numbers (number of holes), which are the ranks of these groups, should be faster, but this has not been algorithmically proved. Delfinado and Edelsbrunner [START_REF] Jose | An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere[END_REF] introduce an algorithm with almost linear time complexity that computes the Betti numbers of a simplicial complex which is a subcomplex of a triangulation of S 3 . The software library RedHom [START_REF] Juda | CAPD::RedHom v2 -homology software based on reduction algorithms[END_REF] is optimized for computing the homology in the context of cubical complexes. Wagner [START_REF] Wagner | Efficient computation of persistent homology for cubical data[END_REF] also proposes an adapted algorithm for computing persistent homology on a cubical complex.

We propose an algorithm that is based on the computation of connected components and avoids any matrix manipulation. This is possible due to the Euler-Poincaré formula and the Alexander duality, which turn to be extraordinarily useful in the context of three-dimensional cubical complexes.

A simple description of the algorithm is given in Sect. 3. Then, we explain in Sect. 4 how to parallelize the computation by considering a different method for counting the connected components which is more adapted to the input data. Sections 5 and 6 explain the implementation of the algorithm and compare it with a previous software respectively.

Preliminaries

nD Cubical Complex

An elementary interval is an interval of the form [k, k + 1] or a degenerate in- terval [k, k],
where k ∈ Z. An elementary cube is the Cartesian product of n elementary intervals, and the number of non-degenerate intervals in this product is its dimension. An elementary cube of dimension d will be called d-cube for short. Given two elementary cubes p and q, we say that p is a face of q if p ⊂ q.

The Khalimsky coordinates of an elementary cube deduced from its Khalimsky coordinates. For a cube q we denote its Khalimsky coordinates by q[] and its ith component by q[i].

An nD cubical complex is a set of elementary cubes. The boundary of a dcube is the collection of its (d -1)-dimensional faces. By virtue of its regular structure, an nD cubical complex can be represented as an n-dimensional array (called CubeMap in [START_REF] Wagner | Efficient computation of persistent homology for cubical data[END_REF]), where the cubes are represented by their Khalimsky coordinates.

From now on we assume that cubes of a given nD cubical complex K have all positive coordinates bounded by integers w i (1 ≤ i ≤ n). A K is the binary n-dimensional array of size L := n i=1 (2w i + 1) where elementary cubes are represented by a Boolean equal to true associated to their Khalimsky coordinates. An element of the array with coordinates x = (x 1 , . . . , x n ) is denoted by

A K [x 1 ] . . . [x n ] or A[x] for short. The element A K [q[]] associated to the cube q is denoted by A K [q].
It is straightforward to provide an enumeration of Khalimsky coordinates in

n i=1 [0, 2w i ].
Namely, there exists a bijection I :

n i=1 [0, 2w i ] → [0, L -1]
. Such bijection I will be referred to as the index map and its image as the index set. For a cube q, I(q) means I(q[]) = I(q[1], . . . , q[n]).

The support of K, denoted by supp(K), is the nD cubical complex containing all the elementary cubes in n i=1 [0, w i ]. Thus, A K encodes both K and supp(K)\ K.

Homology

A chain complex (C, d) is a sequence of R-modules C 0 , C 1 , . . . (called chain groups) and homomorphisms d 1 : C 1 → C 0 , d 2 : C 2 → C 1 , . . . (called differential
or boundary operators) such that d q-1 d q = 0, for all q > 0, where R is some ring, called the ground ring or ring of coefficients. In this paper we will fix R = Z 2 .

An nD cubical complex K induces a chain complex. C q is the free R-module generated by the q-cubes of K. Its elements (called q-chains) are formal sums of q-cubes with coefficients in Z 2 , so they can be interpreted as sets of q-cubes. The linear operator d q maps each q-cube to the sum of its (q -1)-dimensional faces.

A q-chain x is a cycle if d q (x) = 0, and a boundary if x = d q+1 (y) for some (q + 1)-chain y. By the property d q-1 d q = 0, every boundary is a cycle, but the reverse is not true: a cycle which is not a boundary contains a "hole". The qth homology group of the chain complex (C, d) contains the q-dimensional "holes": H(C) q = ker(d q )/im(d q+1 ). This set is a finite-dimensional vector space, so there is a basis typically formed by the holes of the complex, whose elements are called homology generators. The ranks of the homology groups are called the Betti numbers, which count the number of holes in each dimension.

There is a slightly different homology theory called reduced homology where d 0 is defined otherwise. Thus, the zeroth Betti number β 0 is decremented by one. This avoids exceptional cases in several theorems.

In this section we give a first presentation of our algorithm. It considers a restricted class of complexes: 3D cubical complexes. We explain in the following how we obtain each Betti number.

0th Betti number -It is well known that β 0 (K) is the number of connected components of K. This is easy to compute with a traversal of the complex.

2nd Betti number -Alexander duality relies the homology of a complex K of dimension 3 and its complementary in the three-dimensional sphere S 3 \ K.

Proposition 1 (Alexander duality) Let K be a 3D cubical complex. Then H q (K) and H 2-q (S 3 \ K) are isomorphic for reduced homology and cohomology.

As a consequence, β 2 (K) = β 0 (S 3 \ K) -1. That is, the number of voids in K is the number of connected components in the complementary minus one.

This result, which holds for more general spaces, is computationally interesting in the context of cubical complexes. First, the sphere S n is easy to build. Figure 1 shows the spheres S 1 and S 2 as cubical complexes. Also, the complementary of a cubical complex is obvious to compute given its regular structure. Figure 2 illustrates the complementary of a cubical complex.

We want to obtain the number of connected components (minus one) of S 3 \K for deducing β 2 (K). Nevertheless, we do not need to build S 3 \ K. It suffices to count the connected components in supp(K) \ K and consider only those which do not contain a cube in the boundary of supp(K). These connected components are connected to S 3 \ supp(K), thus making only one connected component in S 3 \ K. Note that this fact is far easier to understand for a 1D or a 2D cubical complex.

Fig. 2. A two-dimensional cubical complex K and its complementary S 2 \ K 1st Betti number -Once β 0 (K) and β 2 (K) are known, β 1 (K) is easy to obtain via the Euler-Poincaré formula. The Euler-Poincaré characteristic of a 3D cubical complex K is the alternating sum of its cubes. Formally,

χ(K) = k 0 -k 1 + k 2 -k 3 ,
where k q denotes the number of cubes of dimension q in K. This number, which is easy to compute, is a topological invariant.

Proposition 2 (Euler-Poincaré formula) Let K be a 3D cubical complex. Then χ(K) = β 0 (K) -β 1 (K) + β 2 (K). Therefore, β 1 (K) = β 0 (K) + β 2 (K) -χ(K).
Algorithm 1 combines these three ideas. It passes by all the elements of A K and traverses the connected components of K and supp(K) \ K. For the sake of simplicity we do not explicitly describe the computation of χ(K) in Algorithm 1. It can be obtained by adding χ ← χ + (-1) dim(p) to line 16. As each cube is connected to six other cubes in A K (except for the cubes in the boundary of A K ), the complexity of the algorithm is O(n+6n) = O(n) where n is the number of cubes in supp(K).

Recursive version of the Algorithm

The core of the previous algorithm is the computation of connected components through a traversal of the three-dimensional array A K . This is difficult to parallelize because it uses a queue data structure. In this section we describe an algorithm for computing connected components of an nD cubical complex K in parallel. The algorithm total CPU utilization (i.e. work) is almost linear. It significantly uses the representation of a cubical complex as a multidimensional array A K with an index map I.

Algorithm 1 BettiViaCC

Input: K a 3D cubical complex; AK its associated binary array Output: The Betti numbers of K: β0, β1, β2

1: β0 ← 0, β2 ← 0 2: for all p ∈ AK not marked do 3: b ← false 4:

Q ← an empty queue 5:

Q.push(p); mark p 6:

while Q not empty do 7:

q ← Q.pop() 8:

if q belongs to the boundary of AK then 9:

b ← true 10:

end if 11:

for all q ′ 6-neighbor of q, AK [q ′ ] = AK [q], q ′ not marked do 12:

Q.push(q ′ ); mark q ′ 13:

end for 14:

end while 15:

if AK [p] = true then 16:

β0 ← β0 + 1 17:

else if b = false then 18:

β2 ← β2 + 1 19:

end if 20: end for 21: β1 ← β0 + β2χ(K) 22: return (β0, β1, β2)

In Sect. 3 we count connected components by traversing the connectivity graph of the cubical complex. Another well known approach to compute connected components is to use disjoint set data structure. The data structure maintains a collection S = { S 1 , . . . , S k } of disjoint sets. Each set in S is identified by a representative, which is a member of the set (see [START_REF] Thomas | Introduction to Algorithms[END_REF]Chapter 21]). The following operations may be performed on the disjoint set data structure C:

-C. makeSet(x) -creates a new set whose only member (and thus representative) is x. -C. find(x) -returns a pointer to the representative of the (unique) set containing x. -C. union(x, y) -merges the sets that contain x and y into a new set that is the union of these two sets.

To compute connected components of a cubical complex it is enough to call C. union(x, y) for each pair x, y of adjacent cubes. A parallel version of such algorithm requires synchronization, so in practice it cannot be implemented efficiently. However, the regular structure of a cubical complex allows us to propose a different approach where synchronization is not needed. The idea is to recursively cut the complex in two halves, find the connected components in each half and then merge them.

Let K be a cubical complex and I the index map of Khalimsky coordinates. Let J be a subset of the index set associated with K. We define K J := { q ∈ K | I(q) ∈ J }. We also define the left slice, right slice and middle slice of J in dimension d by x respectively as

S(J, x -, d) := { y ∈ J | I -1 (y)[d] < x } S(J, x + , d) := { y ∈ J | x ≤ I -1 (y)[d] } S(J, x, d) := { y ∈ J | x -1 ≤ I -1 (y)[d] ≤ x }.
For a j ∈ J we denote by cc J (j) the connected component of K J to which j belongs. Algorithm 2 computes recursively connected components of a cubical complex. Observe that at each step of the recursion the set J is split following some rule. We do not give an explicit description of the rule, but it should divide J into two sets of similar size by separating K J along alternate axes. We thus obtain three subsets that cover J, one of them intersecting the other two so we can merge the connected components computed on each side. The first two recursive steps (lines 4 and 5) work on independent data, so they can be executed in parallel. The third recursive step at line 6 always jumps to the line 8 (since J ≯ ǫ = ∞) and it depends on the previous two steps.

Algorithm 2 RecursiveCC

Input: K a 3D cubical complex; I its associated index map; J ⊂ I. Input: C a disjoint set data structure on the index set of K, such that C. find(i) =

C. find(j) for all i, j ∈ J. Input: Parameters: d ∈ Z and ǫ > 0. Output: For each pair i, j ∈ J we have ccJ (i) = ccJ (j) if and only if C. find(i) =

C. find(j). 1: if size of J > ǫ then 2:

d ← using d choose dimension for next slicing 3:

x ← choose slicing value in dimension d 4:

RecursiveCC(K, I, S(J, x-, d), d, ǫ, C) 5:

RecursiveCC(K, I, S(J, x + , d), d, ǫ, C) 6:

RecursiveCC(K, I, S(J, x, d), d, ∞, C) 7: else 8:

for all p ∈ KJ do 9:

for all q 2n-neighbor of p in KJ do 10:

C. union(I(p), I(q)) 11:

end for 12:

end for 13: end if Algorithm 3 computes the Betti numbers of a 3D cubical complex K. It computes the connected components of K and supp(K) \ K in two calls to Algorithm 2. Again, χ(K) can be computed during the traversal of the complex.

Algorithm 3 RecursiveBetti

Input: K a 3D cubical complex; I its associated index map. Input: Parameter ǫ > 0. Output: The Betti numbers of K: β0, β1, β2.

1: C1 ← a disjoint set for im I 2: for all q ∈ K do 3: C1. makeSet(I(q)) 4: end for 5: RecursiveCC(K, I, im I, 0, ǫ, C1) 6: β0 ← number of sets in C1 7: K0 ← supp(K) \ K 8: C0 ← a disjoint set for im I 9: for all q ∈ K0 do 10:

C0. makeSet(I(q)) 11: end for 12: RecursiveCC(K0, I, im I, 0, ǫ, C0) 13: r ← number of sets in C0 containing a cube in the boundary of supp(K) 14: β2 ← number of sets in C0 minus r 15: β1 ← β0 + β2χ(K) 16: return (β0, β1, β2)

Implementation

Algorithm 3 is implemented as a part of the CAPD::RedHom project [START_REF] Juda | RedHom[END_REF]. Our parallel version of the implementation uses Threading Building Blocks library [START_REF]Intel. Threading Building Blocks[END_REF]. A crucial part of the implementation is a data structure for efficient slicing of the index set. For this we use Boost.MultiArray, a library from Boost Project [START_REF]BoostCommunity[END_REF]. It is an implementation of a multidimensional array container. In our case the data structure contains the index set. It provides an efficient slicing operation implemented as views to the original container. We use it to implement the operation S from the algorithm. At each recursion step we take a direction an cut the multidimensional array in the middle of the direction.

The data structure provides a mapping from multidimensional indices (in our case Khalimsky coordinates) to the index set. Technically it is enough to implement a mapping from the set of indices to a linear space of memory [0, L-1] containing the value i at the ith position. Taking advantage of this fact, features of the C++ language, and Boost.MultiArray, we do not have to allocate memory for the index set. We get the index set and the slicing operation without any additional cost. Of course we can achieve it in many ways, however with our approach we can reuse well tested code.

Validation

Table 1 shows results of numerical experiments with the algorithm implementation. We compare also with standard approach for Betti numbers computa-tions using elementary reductions, coreduction, and Morse decomposition from CAPD::RedHom [START_REF] Juda | RedHom[END_REF]. All the computations were performed using one data structure, only algorithms vary.

Data sets N0001 and P0001 come from computer assisted proofs in dynamics. Data sets rand pP S were generated randomly, where S is the size of the grid and each 3-cube (together with its faces) is included with probability P. The data sets are in binary format, thus reading time can be omitted. Computations were performed on a 2,3 GHz Intel Core i7 (4 real cores, 8 virtual) with 16GB RAM. The results show that the parallel implementation is around 4 times faster than the sequential one. It suggest a perfect scalability with the number of real cores. Also, we see that for the new algorithm only grid size matters.

Conclusion

This paper introduces a linear algorithm that computes the Betti numbers of a 3D cubical complex. It counts the connected components of the complex and its complementary in S 3 and uses the Euler-Poincaré formula. The algorithm is specially conceived for cubical complex as it takes advantage of its regular structure both in a theoretical and a practical manner. It cannot be extended to 4D cubical complexes since the Euler-Poincaré formula does not suffices to obtain all the Betti numbers. An interesting issue that should be addressed in the near future is how to adapt this algorithm for simplicial complexes. The main problem is that we need a triangulation of the complementary of the complex in S 3 , which is not as easy as for cubical complexes.

The current implementation outperforms the existing software for computing Betti numbers on cubical complexes. It is available as a part of the CAPD::RedHom [START_REF] Juda | RedHom[END_REF] project. A more detailed comparison will be done in a forthcoming paper.

Fig. 1 .

 1 Fig. 1. Cubical complexes homeomorphic to S 1 and S 2 .

Table 1 .

 1 CPU time (format [h:]mm:ss) usage for cubical complexes. Computations with following algorithms from CAPD::RedHom: Alg. 3 parallel, Alg. 3 sequential, standard

	Parallel Sequential Standard

n i=1 [a i , b i ] are (a 1 + b 1 , • • • , a n +b n ).The dimension of an elementary cube and its faces can be easily

⋆ This research is supported by the Polish National Science Center under grant 2012/05/N/ST6/03621