Shaoyi Yin
email: yin@irit.fr

Igor Epimakhov
email: epimakhov@irit.fr

Franck Morvan
email: morvan@irit.fr

Abdelkader Hameurlain
email: hameurlain@irit.fr

Resource Allocation for Query Optimization in Data Grid Systems: Static Load Balancing Strategies

Keywords: Resource Allocation, Data Grid Systems, Query Optimization, Load Balancing

Resource allocation is one of the principal stages of relational query processing in data grid systems. Static allocation methods allocate nodes to relational operations during query compilation. Existing heuristics did not take into account the multi-queries environment, where some nodes may become overloaded because they are allocated to too many concurrent queries. Dynamic resource allocation mechanisms are currently developed to modify the physical plan during query execution. In fact, when a node is detected to be overloaded, some of the operations on it will migrate. However, if the resource contention is too heavy in the initial execution plan, the operation migration cost may be very high. In this paper, we propose two load balancing strategies adopted during the static resource allocation phase, so that the workload is balanced at the beginning, the operation migration cost is decreased during the query execution, and therefore the average response time is reduced.

Introduction

In recent years, large amount of scientific data have been produced and need to be shared by researchers from different organizations all over the world. Examples include the Large Hadron Collider (LHC) [1] at CERN and the Sloan Digital Sky Survey (SDSS) [2]. Data grid systems are designed to support such applications. With the objective of accessing and analyzing huge volume of data, the data grid systems rely on distributed, heterogeneous and autonomous computing resources [START_REF] Chervenak | The Data Grid: Towards an Architecture for the Distributed Management and Analysis of Large Scientific Datasets[END_REF]. On the one hand, a data grid system needs to perform query processing efficiently. On the other hand, a data grid system is characterized as large scale, heterogeneous and dynamic. Putting these two aspects together, many technical problems such as resource allocation become more challenging.

In a data grid system, there are different types of resources such as CPU, memory, storage and network. A node in the data grid system corresponds to a computer containing some of these resources. A user query is often issued on one of the nodes and is expressed using a declarative language such as SQL or OQL [START_REF] Smith | Distributed Query Processing on the Grid[END_REF]. The query processor then transforms the query statement into an algebraic tree, called a logical query plan, where nodes denote relational operations and edges represent data flows. Fig. 1 shows a query statement in SQL and its corresponding logical query plan.

At a given time, a node N of the data grid system which has access to a set of resources R = {r 1 , r 2 , …, r n } receives a query Q which consists of a set of operations {o 1 , o 2 , …, o l }. Assume that R is collected during a preceding stage called resource discovery [START_REF] Krauter | A taxonomy and survey of grid resource management systems for distributed computing[END_REF]. The problem of resource allocation is to assign one or more resources in R to each o i such that the execution time of Q is minimized. Thereafter, we call the node N an allocator. Note that, the query type that we deal with is the Scan-Project-Join query. Obviously, the complexity of an exhaustive matching algorithm is exponential, so heuristics [START_REF] Gounaris | Resource scheduling for parallel query processing on computational grids[END_REF][START_REF] Soe | Efficient scheduling of resources for parallel query processing on gridbased architecture[END_REF][START_REF] Liu | Grid query optimizer to improve query processing in grids[END_REF][START_REF] Epimakhov | GeoLoc: Robust Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF] have been proposed to solve this problem. However, most of these heuristics rely on the same principle: they first rank the operations according to certain criteria, then for each operation, they rank the available nodes and allocate the best ones to it. The criteria for ranking the operations, the criteria for ranking the nodes and the number of nodes to allocate are different in each heuristic method. These heuristics did not take into account the following constraints of the data grid system. Constraint 1: Multi-queries are treated by the same allocator. For each query, the allocator consumes the same list of candidate nodes, so the most powerful nodes are allocated to too many queries and become overloaded, while the least powerful nodes stay idle. Constraint 2: Multi-allocators co-exist in the data grid system (as shown in Fig. 2). The resources discovered for one allocator may also be discovered for other allocators. These resources will become overloaded if they are chosen by too many allocators.

Fig. 2. Multi-allocators in a data grid system

The overloading problem caused by the above constraints is currently addressed by adding a resource reallocation phase (which is called dynamic resource allocation) during the query execution [START_REF] Gounaris | Adaptive query processing and the grid: Opportunities and challenges[END_REF][START_REF] Gounaris | Practical adaptation to changing resources in grid query processing[END_REF][START_REF] Da Silva | An adaptive parallel query processing middleware for the grid[END_REF][START_REF] Avnur | Eddies: Continuously adaptive query processing[END_REF][START_REF] Patni | Load balancing strategies for grid computing[END_REF][START_REF] Epimakhov | Mobile Agent-based Dynamic Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF], that is, to move part of the work from overloaded resources to less loaded resources. The dynamic phase is very important, not only because the static allocation result may be under optimal, but also because in the data grid system, nodes may leave or enter at any time. However, the efficiency of the dynamic allocation is truly linked with the initial static allocation result. If the workload is already well balanced between nodes after the static resource allocation, much less work needs to be done during the dynamic phase, which is actually the objective of our paper.

In this paper, we propose two load-balancing strategies which aim at improving the physical execution plan generated by the static resource allocation, such that the average response time of the queries is reduced. They cannot replace the dynamic resource allocation phase, but they could make the latter more efficient. The principles of the proposed strategies are as follows:

• Local Load Balancing (LLB): virtually reserve resources of a node each time after it is allocated to an operation and virtually release the resources used by a query after it is finished; • Global Load Balancing (GLB): Instead of allocating directly the best node to an operation, the algorithm first proposes K candidates and collects the current workload information of their resources by contacting them, then ranks the K nodes and returns the best one.

The rest of the paper is organized as follows. Section 2 presents a brief survey of the existing static and dynamic resource allocation methods in data grid systems. Section 3 describes the principles of our strategies and the corresponding algorithms. Section 4 evaluates the proposed strategies by combining them with existing resource allocation methods. Section 5 concludes the paper.

Related Work

The earliest work dealing with the resource allocation problem for query optimization in the data grid environment is the work of Gounaris [START_REF] Gounaris | Resource scheduling for parallel query processing on computational grids[END_REF]. It is a static resource allocation method. During the initiation phase, only one node is allocated to each operation. Then the algorithm increases the degree of parallelism for the most costly operation by allocating the most powerful nodes one by one to it. When the benefit of increasing a node to the operation is less than a threshold, the algorithm chooses the next most costly operation and increases the degree of parallelism for it. The iteration continues like this. When the chosen operation does not change any more, the resource allocation is finished. The load balancing is not addressed at all by this work. Several other static resource allocation methods have been proposed [START_REF] Soe | Efficient scheduling of resources for parallel query processing on gridbased architecture[END_REF][START_REF] Liu | Grid query optimizer to improve query processing in grids[END_REF][START_REF] Epimakhov | GeoLoc: Robust Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF]. The most recent one is called GeoLoc [START_REF] Epimakhov | GeoLoc: Robust Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF]. It has two main contributions. First, it defines an Allocation Space (AS) for each operation. It distinguishes two kinds of nodes: data nodes which contain the relation fragments and computing nodes which do not con-tain any relation fragment. For a scan operation, the AS is defined to contain all the nodes storing the used relation fragments. For a join operation, the AS is defined to contain the nodes allocated to its input operations and the nodes geographically close to these nodes. Second, it takes into account the dependency between relational operations. It determines the degree of parallelism for each join operation according to the resource requirements driven by its input operations. For example, if the scan operations send 1000 tuples per second to a join operation, GeoLoc will allocate to that join operation just enough resources which can process 1000 tuples per second. Even though the load balancing problem is not explicitly addressed by the GeoLoc method, the usage of the AS decreases the resource contention. However, it is still possible that a same node is allocated for many queries simultaneously.

In the data grid system, due to the multi-queries and multi-allocators constraints, some nodes may become overloaded during the query execution, thus the average response time is increased. The current solution to this problem is to add a dynamic resource allocation phase which modifies the physical plan during the query execu-tion. There exist two main approaches: centralized and decentralized. In the central-ized approach, the workload status of the nodes is monitored by a dedicated resource broker [START_REF] Gounaris | Adaptive query processing and the grid: Opportunities and challenges[END_REF][START_REF] Gounaris | Practical adaptation to changing resources in grid query processing[END_REF][START_REF] Da Silva | An adaptive parallel query processing middleware for the grid[END_REF][START_REF] Avnur | Eddies: Continuously adaptive query processing[END_REF][START_REF] Patni | Load balancing strategies for grid computing[END_REF]. In the decentralized approach, each node detects if it is over-loaded and makes autonomously the decision of moving operations from it to other nodes [START_REF] Epimakhov | Mobile Agent-based Dynamic Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF]. In the work [START_REF] Epimakhov | Mobile Agent-based Dynamic Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF], each relational operation is implemented as a mobile agent running on the allocated node, meaning that, it keeps track of its own status and can migrate to another node at any time. Thanks to a two-level cooperation mechanism between the autonomous nodes and autonomous operations, the workload is dynamically balanced among the grid nodes during query execution. The dynamic resource allocation phase is very important for query optimization, especially when there are node leavings and enters. However, the total migration cost could be high if the static resource allocation result is too imbalanced. In this paper, we aim at producing a balanced resource allocation result during the static phase, so that the migration cost of the dynamic phase is reduced, and therefore the average query response time is decreased.

Static Load Balancing Strategies

After the resource discovery phase, the allocator keeps the resource information (for example the size of memory, the CPU speed, the IO throughput and the network bandwidth) of each discovered node in a local table. This information is used as metadata during the resource allocation for the arriving queries. When the queries arrive frequently or even in batch, it is not realistic to update the resource information for each query due to the expensive communication cost. It means that, for a group (hundreds or thousands) of queries, the allocator consumes the same resource infor-mation table. This may introduce a kind of resource contention: some more powerful nodes may be allocated to too many concurrent queries while some less powerful nodes stay almost idle. Since the nodes are shared by the entire grid system, there is another kind of resource contention: a same node may be discovered for several different allocators and then become overloaded easily. In order to relieve these two kinds of resource contention, we propose in this section two load balancing strategies.

Local Load Balancing (LLB) Strategy

This strategy is proposed to solve the resource contention problem caused by the multi-queries constraint. The principle is to balance the workload between nodes by taking into account the local resource allocation history. In the resource information table RIT, the allocator maintains a counter for each resource type. Table 1 is a snapshot of the RIT, where NB_DM_X denotes the number of active demands for a resource type X and RC_X denotes the resource capacity on X. For example, if node N is allocated to a query which needs only I/O and network resources, we increase each of the counters NB_DM_IO N and NB_DM_NET N by one.

…

When the allocator allocates nodes for an operation, instead of using RC_X of each node to estimate the execution cost, it uses the currently available resource AR_X, which is computed using the following formula (where N is the node ID): The allocator also maintains a table to register the resource demand of each treated operation. In this table, each tuple contains the query ID, node ID and the demand (DM_X, Boolean) for each resource type X. Each time after allocating a node to an operation, the allocator adds a tuple to this table. Each time a query is finished, the allocator decreases the demand counters in the resource information table RIT according to resource demand history related to the finished query. Finally, the history records related to that query are removed.

N N N X DM NB X RC X AR _ _ _ _ = (1)

Global Load Balancing (GLB) Strategy

This strategy is proposed to solve the resource contention problem caused by the multi-allocators constraint. When choosing a node to allocate for an operation, the allocator proposes several candidate nodes according to the local resource information, and then it contacts these nodes to collect their workload status at the moment. Using the new resource information, the allocator ranks these candidate nodes and chooses the best one. Table 3 shows an example of candidate nodes list CNL after contacting them, where CNB_DM_X means the current number of demands for resource X registered by the node. The allocator estimates then the execution cost using the available resource capacity AR_X computed by the new formula:

N N N X DM CNB X RC X AR _ _ _ _ =
(2)

…

Algorithm 3 illustrates the steps of using GLB to select a node N for an operation O. Note that, the current workload information collected from the nodes is used only to choose the best node for an operation, but not to update the RIT table. The RIT table could be only modified by the LLB strategy so that the information is kept consistent.

Performance Evaluation

We first measure the impact of LLB and GLB strategies on two existing static resource allocation methods: method of Gounaris [START_REF] Gounaris | Resource scheduling for parallel query processing on computational grids[END_REF] and GeoLoc method [START_REF] Epimakhov | GeoLoc: Robust Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF]. We then add the dynamic resource allocation phase to each method and measure again the impact of LLB and GLB. The dynamic allocation algorithm that we use is the work published in [START_REF] Epimakhov | Mobile Agent-based Dynamic Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF]. Our proposed load balancing strategies can be combined with other static or dynamic resource allocation methods, even though we choose only the above representatives for the performance evaluation.

For the experimentation, we use the grid simulator presented in [START_REF] Epimakhov | GeoLoc: Robust Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF], [START_REF] Epimakhov | Mobile Agent-based Dynamic Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF] with some extensions. The simulated data grid contains 2000 nodes that store 2000 relations. Each relation contains 5 equal fragments, each of which in turn is duplicated on 4 nodes. So in average we have 20 copies of different fragments on each node. To simulate the dynamicity of the grid system, 5% of the nodes quit the system at the 600 th millisecond and reenter at the 1200 th millisecond. The main parameters that we used for the simulation are listed in Table 4. Section 4.1 shows the impact of the proposed strategies on the static resource allocation, in terms of average query response time and optimization cost. Section 4.2 shows the impact of the proposed strategies on the static resource allocation combined with a dynamic resource allocation phase, in terms of average query response time and number of operation migrations. We also measured the effect of increasing the number of concurrent queries.

Impact of LLB and GLB on Static Resource Allocation

We take Gounaris' method and the GeoLoc method as two examples to examine our load balancing strategies. LLB and GLB strategies are evaluated in a gradual way, meaning that, we first measure the initial allocation method (named Gouna/GeoLoc), then the initial method combined with LLB (named GouLLB/GeoLLB), and finally the initial method combined with LLB and GLB (named GouLLB+GLB /GeoLLB+GLB).

Impact on Gounaris' Method. The average response time varying with the number of queries is shown Fig. 3. The speedup factor of the two strategies is illustrated in Fig. 4. Not surprisingly, we find that the speedup factor is more significant when there are more concurrent queries.

We measured also the average optimization cost of each query by varying the number of queries. The result can be found in Fig. 5. Interestingly, we see that the optimization time is not always longer when adding our load balancing strategies. This is because the query optimization contains several steps including mainly 1) generation of the logical plan, 2) selection of nodes for each operation and 3) generation of physical operators. When adding LLB or GLB, the first step does not change, the second step is slowed down, but the third step could be sped up or slowed down depending on the result of the second step. For example, when adding LLB strategy, fewer physical operators are generated during the third step, so the optimization time is shorter.

Number of queries

Gouna

GouLLB

GouLLB+GLB

Impact on GeoLoc Method. The average response time and the speedup factor are shown in Fig. 6 and Fig. 7 respectively. The impact of the load balancing strategies is less significant than for Gounaris' method, because GeoLoc has already balanced the workload to some extent thanks to the using of Allocation Space. However, the same conclusion can be drawn: the speedup factor of LLB and GLB is more important when there are more concurrent queries. The average optimization time of each query is given in Fig. 8. We have three remarks: 1) the optimization time is not always increased by adding the load balancing strategies; 2) even when the optimization time is increased, the discrepancy is not very high; 3) compared to the total response time, the optimization cost is trivial.

Impact of LLB and GLB on Dynamic Resource Allocation

We still take Gounaris' method and the GeoLoc method as two examples of static resource allocation methods. A dynamic resource allocation phase is added to each using the same mechanism published in [START_REF] Epimakhov | Mobile Agent-based Dynamic Resource Allocation Method for Query Optimization in Data Grid Systems[END_REF]. We evaluate the impact of our load balancing strategies in terms of the average response time of a query and the number of operation migrations in the system during query execution. The notations of the methods are the same as in Section 4.1.

Impact on Gounaris' Method. The average response time and the speedup factor are shown in Fig. 9 and Fig. 10 respectively. The speedup factor is less high than doing only static allocation, but it is still remarkable. The total number of operation migrations during the query execution is given by Fig. 11. We can see that LLB and GLB have avoided many operation migrations, and this is one of the reasons why the average response time is reduced.

Impact on GeoLoc Method. The average response time and the speedup factor are shown in Fig. 12 and Fig. 13 respectively. The number of operation migrations is not shown due to space limitation. The conclusion is that, LLB and GLB have avoided most of the operation migrations during execution, and the average response time is reduced accordingly.

Conclusion

In this paper, we presented two static load balancing strategies during resource allocation for query optimization in data grid systems, in order to avoid the node overload situation, so that the average query response time is reduced. When combined with the dynamic allocation phase, they could reduce the operation migration cost during execution and therefore decrease the query response time accordingly. The first strategy is called Local Load Balancing (LLB). It is designed to solve the resource contention problem caused by the multi-queries constraint of data grid systems. It makes fully use of the local resource allocation history to finally distribute the workload proportionally according to the capacity of the nodes. The second strategy is called Global Load Balancing (GLB). It is designed to solve the resource contention

Speedup factor

Number of queries

GeoLLB

GeoLLB+GLB problem caused by the multi-allocators constraint of data grid systems. It first chooses several candidate nodes for an operation using the local information, then contacts these nodes and collects their current workload status, and finally re-ranks these nodes to select the best one. The result of the performance evaluation has shown the efficiency of the proposed strategies. For example, by integrating our LLB and GLB strategies with Gounaris' method, the query execution time is reduced by 10 to 40 times; by integrating them with the GeoLoc method, the query execution time is reduced by 2 to 4 times. The proposed strategies could be combined with other existing static and dynamic resource allocation methods in data grid systems. They decrease significantly the query response time, but they don't increase much the allocation cost.

Fig. 1 .

 1 Fig. 1. A query statement and its logical query plan

Fig. 3 .Fig. 4 .Fig. 5 .

 345 Fig. 3. Average query response time varying with the number of queries

Fig. 6 .Fig. 7 .Fig. 8 .

 678 Fig. 6. Average query response time varying with the number of queries

Fig. 9 .Fig. 10 .Fig. 11 .Fig. 12 .Fig. 13 .

 910111213 Fig. 9. Average query response time varying with the number of queries

Table 1 .

 1 Snapshot of the resource information table RIT

	N_ID	RC_	RC_	RC_	RC_	NB_DM	NB_DM	NB_DM	NB_DM
		RAM	CPU	IO	NET	_RAM	_CPU	_IO	_NET
	205	15000	24000	19000	27000	10	5	8	10
	192	8000	36000	12000	35000	6	12	3	5

Table 2 .

 2 Snapshot of the resource demand table RDT

	Q_ID	N_ID	DM_RAM	DM_CPU	DM_IO	DM_NET
	11	205	0	0	1	1
	11	192	0	1	1	0
	12
	…

  Table 2 is a snapshot of the resource demand table RDT. For example, when query 11 is finished, we decrease each of the counters NB_DM_IO 205 , NB_DM_NET 205 , NB_DM_CPU 192 and NB_DM_IO 192 by one respectively, and we remove the first two tuples from table RDT. Algorithm 1 describes the process of the maintenance of the resource information table and the resource demand table each time after allocating a node N to an operation O of a query Q. Algorithm 2 describes the process of maintenance each time after a query Q is finished.

	Algorithm 1. VirtualResourceReservation()
	INPUT: Query Q, Node N, resource demand DM_X for each X
	BEGIN
	FOR each resource type X of node N DO
	IF DM_X > 0 THEN
	Increase the counter NB_DM_X N by one in table RIT;
	END IF
	END FOR
	Insert the tuple (Q, N, DM_RAM, …) into table RDT;
	END
	Algorithm 2. VirtualResourceRelease()
	INPUT: Query Q
	BEGIN
	FOR each node N related to query Q in RDT DO
	FOR each resource type X of node N DO
	IF DM_X N > 0 THEN
	Decrease the counter NB_DM_X N by one in table RIT;
	END IF
	END FOR
	END FOR
	Delete the tuples related to Q from table RDT;
	END

Table 3 .

 3 Example of the candidate nodes list CNL

	N_ID	CNB_DM	CNB_DM	CNB_DM	CNB_DM
		_RAM	_CPU	_IO	_NET
	39	12	6	9	10
	267	8	3	6	7

Table 4 .

 4 System configuration and database parameters

		Parameter	Value
	Node	CPU performance	100 -10 000 MIPS
		I/O throughput	10 -1000 Mb/s
		Memory amount	10 -1000 MB
		Network connection bandwidth	10 -1000 Mb/s
		Network connection latency	0.05s
	Relation	Number of attributes	10
		Size of attribute	1 -50 Bytes
		Cardinality of attributes	0.01 -1
		Number of tuples	1000 -11000
		Number of fragments	5
		Number of duplicates per fragment	4


Leila Amgoud

Philippe Besnard

A Formal Characterization of the Outcomes of Rule-Based Argumentation Systems

Rule-based argumentation systems are developed for reasoning about defeasible information. As a major feature, their logical language distinguishes between strict rules and defeasible ones. This paper presents the first study on the outcomes of such systems under various semantics such as naive, stable, preferred, ideal and grounded. For each of these semantics, it characterizes both the extensions and the set of plausible inferences drawn by these systems under a few intuitive postulates.

Introduction

There are two major categories of instantiations of Dung's abstract argumentation framework [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. A category uses deductive logics (such as propositional logic [START_REF] Amgoud | Inferring from inconsistency in preference-based argumentation frameworks[END_REF][START_REF] Gorogiannis | Instantiating abstract argumentation with classical logic arguments: Postulates and properties[END_REF] or Tarskian logics [START_REF] Amgoud | Logical limits of abstract argumentation frameworks[END_REF]). The second category uses rule-based languages [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF][START_REF] García | Defeasible logic programming: an argumentative approach[END_REF][START_REF] Governatori | Argumentation semantics for defeasible logic[END_REF] which distinguish between facts, strict rules (they encode strict information), and defeasible rules (they describe general behavior with exceptional cases). Despite the popularity of rulebased argumentation systems, the results they return have not been characterized yet.

The following questions are still open:

what are the underpinnings of the extensions under various semantics? do Dung's semantics return different results as at the abstract level? what is the number of extensions a system may have under a given semantics? what are the plausible conclusions with such systems?

In this paper, we answer all the above questions. We start with a knowledge base called a theory (a set of facts, a set of strict rules and a set of defeasible rules), we define a notion of a derivation schema which we use to generate arguments from the theory. For the sake of generality, the attack relation is left unspecified. We extend the list of postulates proposed in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF] with three new postulates. We investigate outputs of rule-based argumentation systems that satisfy all the postulates. We show that naive extensions return maximal options of the theory (an option being a sub-theory that gathers all the facts and strict rules, and a maximal -up to consistency-set of defeasible rules that do not conflict with the strict part). Every maximal option gives birth to a naive extension. Furthermore, the set of plausible conclusions under the naive semantics contains all the conclusions that are drawn from all the maximal options. Stable extensions return maximal options but not necessarily all of them, it depends on the attack relation at work. Should not all maximal options be picked as stable extensions, defining an attack relation that discard exactly the spurious ones turns out be tricky. The same results hold for preferred semantics. We characterize both ideal and grounded extensions.

Rule-Based Argumentation Systems

In what follows, we consider the language used in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF]. Let L is a set of literals, i.e., atoms or negation of atoms. The negation of an atom x from L is denoted ¬x. Three kinds of information (x, x 1 ...x n denoting literals in L) are distinguished:

-Facts, which are elements of L -Strict rules, which are of the form x 1 , . . . , x n → x -Defeasible rules, which are of the form x 1 , . . . , x n ⇒ x Throughout the text, rules are named r 1 , r 2 , . . . For each rule r = x 1 , . . . , x n → x (as well as r = x 1 , . . . , x n ⇒ x), the head of the rule is Head(r) = x and the body of the rule is Body(r) = {x 1 , . . . , x n }. A strict rule expresses general information that has no exception, e.g. "penguins cannot fly" whereas a defeasible rule expresses general information that may have exceptions, e.g. "birds can fly".

Definition 1 (Theory).

A theory is a triple T = (F , S, D) where F is a set of facts and S (resp. D) is a set of strict (resp. defeasible) rules.

Notation. Let T = (F , S, D) and let T ′ = (F ′ , S ′ , D ′ ) be two theories. We say that T is a sub-theory of T ′ , written T ⊑ T ′ , iff F ⊆ F ′ and S ⊆ S ′ and D ⊆ D ′ . The relation ⊏ is the strict version of ⊑ (i.e., it is the case that at least one of the three inclusions is strict).

The notion of consistency is defined as follows.

Definition 2 (Consistency

). A set X ⊆ L is consistent iff ∄x, y ∈ X s.t. x = ¬y. It is inconsistent otherwise. Assumption 1.
The body of every (strict/defeasible) rule is finite and not empty. Moreover, for each rule r, Body(r) ∪ {Head(r)} is consistent. We say that r is consistent.

The notion of a derivation schema generalizes derivations as defined in [START_REF] García | Defeasible logic programming: an argumentative approach[END_REF][START_REF] Marek | A theory of nonmonotonic rule systems I[END_REF] and others. It shows how literals can follow from a theory.

Definition 3 (Derivation schema).

Let T = (F , S, D) be a theory and x ∈ L. A derivation schema for x from T is a finite sequence d = (x 1 , r 1 ), . . . , (x n , r n ) s.t.

-x n = x -for i = 1 . . . n, • x i ∈ F and r i = ∅, or • r i ∈ S ∪ D and Head(r i ) = x i and Body(r i ) ⊆ {x 1 , .., x i-1 } Seq(d) = {x 1 , . . . , x n }. Facts(d) = {x i | i ∈ {1, . . . , n}, r i = ∅}. Strict(d) = {r i | i ∈ {1, . . . , n}, r i ∈ S}. Def(d) = {r i | i ∈ {1, . . . , n}, r i ∈ D}.
Notation. In order to improve readability, we somehow abuse the notation in derivation schemata: We use the name of the rules instead of the rules themselves.

A derivation schema is not necessarily consistent (such as [START_REF] Governatori | Argumentation semantics for defeasible logic[END_REF] below), as it may contain opposite literals in the form x i = ¬x j for some i and j (this is in accordance with Definition 2).

Example 1.

Consider T 1 such that F 1 , S 1 , D 1 are as follows.

F 1 p q S 1    p → s (r 1 ) q → ¬s (r 2 ) p, s → u (r 3 ) D 1    ¬s ⇒ t (r 4 ) t, u ⇒ ¬v (r 5 ) p ⇒ q (r 6 )
Each of ( 1)-( 7) below is a derivation schema from T 1

(p, ∅) (1) (q, ∅), (¬s, r 2 ) (2) (p, ∅), (s, r 1 ), (u, r 3 ) (3) (p, ∅), (s, r 1 ), (p, ∅), (u, r 3 ) (4)
(p, ∅), (q, ∅), (s, r 1 ), (u, r 3 )

(5) (p, ∅), (q, r 6 ), (¬s, r 2 ) (6) (p, ∅), (q, ∅), (¬s, r 2 ), (s, r 1 ), (u, r 3 ), (t, r 4 ), (¬v, r 5 )

A derivation schema may not be (⊆-)minimal. There are two reasons for that:

repeating pairs (x i , r i ) as in derivation (4) ((p, ∅) is repeated twice), involving literals that do not serve towards inferring the conclusion x, as is illustrated by (5) (q is of no use there). The derivation schema fails thus to be focussed.

Definition 4 (Minimal/focussed derivation schema). A derivation schema for x from

T is minimal iff none of its proper subsequences is a derivation schema for x from T . It is focussed iff it can be reduced to a minimal one by just deleting repeated pairs (x i , r i ).

Property 1. Let T = (F , S, D) be a theory. A derivation schema d = (x 1 , r 1 ), . . . , (x n , r n ) from T is minimal iff d is focussed and the literals x 1 , . . . , x n are pairwise distinct.

Notation. CN(T ) denotes the set of all literals that have a derivation schema from T . We call CN(T ) the potential consequences drawn from T (for short, consequences) but they need not be definitive as they may be dismissed by opposite conclusions.

Property 2. Let T = (F , S, D) be a theory.

-F ⊆ CN(T ) ⊆ F ∪ {Head(r) | r ∈ S ∪ D} ⊆ L -If T is finite, then CN(T ) is finite -F = ∅ iff CN(T ) = ∅ -If d is a derivation schema from T , Seq(d) ⊆ CN(T )
Some rules may not be activated (i.e., their body has no derivation schema). Let us consider the following example.

Example 2. Let T 2 = (F 2 , S 2 , D 2 ) such that F 2 p q S 2    p → t (r 1 ) q → t (r 2 ) s → u (r 3 ) D 2 p ⇒ q (r 4 ) u ⇒ v (r 5 )
There are rules here whose head is not a consequence of T 2 . CN(T 2 ) = {p, q, t} ⊂ {p, q, t, u, v}

= F 2 ∪ Head(S 2 ∪ D 2 ).
It is also easy to show that CN is monotonic.

Property 3. If T ⊑ T ′ then CN(T ) ⊆ CN(T ′ ).
The backbone of an argumentation system is naturally the notion of arguments. They are built from a theory using the notion of derivation schema as follows.

Definition 5 (Argument). Let T = (F , S, D) be a theory. An argument defined from T is a pair (d, x) s.t.

-x ∈ L -d is a derivation schema for x from T -Seq(d) is consistent -∄T ′ ⊏ (Facts(d), Strict(d), Def(d)) s.t. x ∈ CN(T ′ ) An argument (d, x) is strict iff Def(d) = ∅. Notation. If a = (d, x) is an argument then Conc(a) = x. For a set E of arguments, Concs(E) = {x | (d, x) ∈ E}. Arg(T )
is the set of all the arguments defined from T . For a set E of arguments,

Th(E) = ( (d,x)∈E Facts(d), (d,x)∈E Strict(d), (d,x)∈E Def(d)).
Theorem 1. Let T be a theory. For all consistent sequence d = (x 1 , r 1 ), . . . , (x n , r n ) from T , the following two statements are equivalent:

-(d, x) is an argument (from T ) -d is a focussed derivation schema from T s.t. x = x n Definition 6 (Sub-argument). An argument (d, x) is a sub-argument of (d ′ , x ′ ) iff (Facts(d), Strict(d), Def(d)) ⊑ (Facts(d ′ ), Strict(d ′ ), Def(d ′ )).
Notation Sub(a) denotes the set of all sub-arguments of a.

Example 1 (Cont). The argument ( (q, ∅), (¬s, r 2 ) , ¬s) has two sub-arguments: ( (q, ∅) , q) and itself. By contrast, ( (q, ∅) , q) is not a sub-argument of ( (p, ∅), (q, r 6 ) , q).

Clearly, if (d, x) is a sub-argument of (d ′ , x ′ ) then Seq(d) ⊆ Seq(d ′
), but the converse is not true as shown next.

Example 2 (Cont). Arguments a = ( (p, ∅), (t, r 1 ) , t) and b = ( (p, ∅), (q, r 4 ), (t, r 2 ) , t) are s.t. Seq(a) = {p, t} ⊆ {p, q, t} = Seq(b) but a is not a sub-argument of b.

From the monotonicity of CN, it follows that the construction of arguments is a monotonic process.

Proposition 1. If T ⊑ T ′ then Arg(T ) ⊆ Arg(T ′ ).
An argumentation system is defined as follows:

Definition 7 (Argumentation system). An argumentation system (AS for short) defined over a theory

T = (F , S, D) is a pair H = (Arg(T ), R) where R ⊆ Arg(T ) × Arg(T ) is called an attack relation.
In what follows, arguments are evaluated using semantics proposed in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. Before recalling them, let us first introduce the two requirements on which they are based.

Definition 8 (Conflict-freeness -Defence). Let H = (A, R) be an AS, E ⊆ A and

a ∈ A. -E is conflict-free iff ∄a, b ∈ E s.t. a R b. -E defends a iff ∀b ∈ A, if b R a then ∃c ∈ E s.t. c R b.
Definition 9 recalls the semantics of interest in the sequel.

Definition 9 (Acceptability semantics). Let H = (A, R) be an AS and

E ⊆ A. -E is a naive extensions iff it is a maximal (w.r.t. set ⊆) conflict-free set. -E is an admissible set iff it is conflict-free and defends all its elements. -E is a preferred extension iff it is a maximal (w.r.t. set ⊆) admissible set. -E is a stable extension iff it is conflict-free and ∀a ∈ A \ E, ∃b ∈ E s.t. b R a.
-E is a grounded extension iff it is a minimal (w.r.t. set ⊆) set that is admissible and contains any argument it defends. -E is an ideal extension iff it is the maximal (w.r.t. set ⊆) admissible set which is part of any preferred extension.

Notation. Ext x (H) denotes the set of all the extensions of a system H under semantics x where x ∈ {n, p, s} and n (resp. p, s) stands for naive (resp. preferred, stable).

Plausible conclusions are those common to all extensions.

Definition 10 (Plausible conclusions). If H = (Arg(T ), R) is an AS built over a theory T , the set of plausible conclusions of H is

Output(H) = E i ∈Ext x (H)
Concs(E i ).

From the above definitions, namely that of an argument, it follows that the plausible conclusions of an argumentation system are a subset of the consequences that follow wrt CN from the theory over which the system is built. Property 4. Let H = (Arg(T ), R) be an AS built over T . Output(H) ⊆ CN(T ).

Postulates for Argumentation Systems

We present rationality postulates that any rule-based argumentation system should satisfy. The first two were already proposed in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF] and the others are new. The first postulate ensures that the set of conclusions of arguments of each extension is consistent. This is compatible with the fact that each extension represents a coherent position.

Postulate 1 (Consistency)

. Let H = (Arg(T ), R) be an AS built over a theory T . For all E ∈ Ext x (H), Concs(E) is consistent. We say that H satisfies consistency.

It was shown in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF] that if an argumentation system H satisfies consistency, then its set Output(H) of plausible conclusions is consistent as well.

Property 5 ([3]). If an AS H satisfies consistency, then Output(H) is consistent.

The second postulate ensures that the extensions of an argumentation system are closed under strict rules. The idea is that if there is an argument with conclusion x in an extension and there exists a strict rule x → y, then y should also be supported by an argument in the same extension.

Postulate 2 (Closure under strict rules). Let H = (Arg(T ), R) be an AS built over a theory T . For all E ∈ Ext x (H), Concs(E) = CN((Concs(E), S, ∅)). We say that H is closed under strict rules.

It is known that if an argumentation system H is closed under strict rules, then its set Output(H) is necessarily closed under strict rules.

Property 6 ([3]). Let H be an AS built over a theory T = (F , S, D). If H is closed under strict rules, then Output(H) = CN((Output(H), S, ∅)).

It was also shown in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF] that a system that satisfies consistency and closure under strict rules satisfies indirect consistency.

Property 7 ([3]

). Let H be an AS built over a theory T = (F , S, D). If H satisfies consistency and is closed under strict rules, then for all E ∈ Ext x (H), CN((Concs(E), S, ∅)) is consistent.

We propose three new postulates. The first says that if an argument belongs to an extension, then all its sub-arguments should be in the extension. It means that an argument cannot be accepted in an extension if one of its sub-parts is rejected.

Postulate 3 (Closure under sub-arguments)

. Let H = (Arg(T ), R) be an AS built over a theory T . For all E ∈ Ext x (H), if a ∈ E then Sub(a) ⊆ E. We say that H is closed under sub-arguments.

The following result characterizes the extensions of an argumentation system which is closed under sub-arguments.

Proposition 2. If an AS H is closed under sub-arguments, then

∀E ∈ Ext x (H), -Concs(E) = CN(Th(E)) -∀(d, x) ∈ Arg(Th(E)), Seq(d) ⊆ Concs(E)
Importantly, even when a system is closed under sub-arguments, the equality E = Arg(Th(E)) is not always true. This depends on the semantics as we will see later. Since facts and strict rules are the "hard" part in a theory, it is natural that any strict argument should be in all extensions. This principle is applied in default logic [START_REF] Reiter | A logic for default reasoning[END_REF].

Postulate 4 (Strict precedence). Let H be an AS built over a theory T = (F , S, D).

For all E ∈ Ext x (H), Arg((F , S, ∅)) ⊆ E. We say that H satisfies strict precedence.

We show next that every argumentation system satisfying Postulate 4 infers all the conclusions that follow from the set of facts and the strict rules of a theory. Next is an important result for the rest of our study: it says that if an argumentation system over a theory T satisfies Postulates 2, 3, 4, then the set of literals deduced from Th(E), the theory of an extension E, is exactly the one obtained from Th(E) extended by all facts and strict rules of T which are not in Th(E). The last postulate ensures a form of completeness of the extensions. It says that if the sequence of an argument is part of the conclusions of a given extension, then the argument (Definition 5 ensures consistency) should belong to the extension. Informally: If each step in the argument is good enough to be in the extension, then so is the argument itself.

Postulate 5 (Exhaustiveness)

. Let H = (Arg(T ), R) be an AS built over a theory T = (F , S, D). For all E ∈ Ext x (H), for all

(d, x) ∈ Arg(T ), if Seq(d) ⊆ Concs(E), then (d, x) ∈ E.
The extensions (under any semantics) of any argumentation system that satisfies exhaustiveness and closure under sub-arguments are closed in terms of arguments. Proposition 6. If an AS H is closed under sub-arguments and satisfies the exhaustiveness postulate, then ∀E ∈ Ext x (H), E = Under some semantics like naive and stable, Postulate 5 follows from consistency and closure under sub-arguments. This is mostly the case when the attack relation is conflict-dependent, that is, it captures the inconsistency of the theory over which the argumentation system is built.

Definition 11 (Conflict-dependency). Let H = (Arg(T ), R) be an argumentation system. The attack relation

R is conflict-dependent iff for all (d, x), (d ′ , x ′ ) ∈ Arg(T ), if (d, x) R (d ′ , x ′ ) then Seq(d) ∪ Seq(d ′ ) is inconsistent.

Proposition 7. Let H = (Arg(T ), R) be an argumentation system built over a theory T s.t. R is conflict-dependent. If H satisfies consistency and closure under subarguments, then H satisfies exhaustiveness under naive and stable semantics.

Finally, it is worth noticing that conflict-dependent relations do not admit selfattacking arguments. Proposition 8. Let H = (Arg(T ), R) be an argumentation system. If R is conflictdependent, ∀a ∈ Arg(T ) (a, a) / ∈ R.

Outcomes of Argumentation Systems

This section analyzes the outputs of rule-based argumentation systems under the semantics recalled in Def. 9. In the sequel, we consider only systems that satisfy the postulates introduced in Section 3. As in [START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF][START_REF] García | Defeasible logic programming: an argumentative approach[END_REF][START_REF] Reiter | A logic for default reasoning[END_REF], we assume that the "hard" part of a theory is consistent. Formally: Assumption 2. For all theory T = (F , S, D), CN((F , S, ∅)) is consistent.

Let us first introduce a key concept: that of an option.

Definition 12 (Option). Let T = (F , S, D) be a theory. An option of T is a sub-theory

T ′ = (F ′ , S ′ , D ′ ) of T such that: -F ′ = F and S ′ = S (hence D ′ ⊆ D) -CN(T ′ ) is consistent -∀r ∈ D \ D ′ , CN((F , S, D ′ ∪ {r})) is inconsistent.
Let Opt(T ) denote the set of all options of T .

Example 3. Consider T 3 such that F 3 , S 3 , D 3 are as follows.

F 3    p q ¬s S 3 t, u, v → s (r 1 ) D 3    p ⇒ t (r 2 ) q ⇒ u (r 3 ) u ⇒ v (r 4 )
The theory T 3 has three options:

-O 1 = (F 3 , S 3 , {p ⇒ t, q ⇒ u}) -O 2 = (F 3 , S 3 , {p ⇒ t, u ⇒ v}) -O 3 = (F 3 , S 3 , {q ⇒ u, u ⇒ v})
When a theory is consistent, it has a unique option: itself. This is the case in Example 2: Opt(T 2 ) = {T 2 }. Property 8. Let T = (F , S, D) be a theory.

-Opt(T ) = {T } iff CN(T ) is consistent. -If CN((F , S, ∅)) is inconsistent, then Opt(T ) = ∅.
-For all r ∈ D, if CN((F , S, {r})) is consistent, then there exists an option O s.t.

(F , S, {r}) ⊑ O.

Note that the set of consequences of an option is not necessarily maximal for set inclusion as shown by Example 3.

Example 3 (Cont).

We have CN(O 1 ) = {p, q, ¬s, t, u}, CN(O 2 ) = {p, q, ¬s, t}, and CN(O 3 ) = {p, q, ¬s, u, v}. Thus, CN(O 2 ) ⊆ CN(O 1 ). Notation For a set B of theories, we denote its maximum as

Max(B) = {T ∈ B | ∄T ′ ∈ B s.t. CN(T ) ⊂ CN(T ′ )}. In Example 3, Max(Opt(T 3 )) = {O 1 , O 3 }.
The defeasible rules of a theory do not necessarily belong to an option of the theory as shown by the following example.

Naive Semantics

We start by characterizing the naive extensions of any argumentation system satisfying the above rationality postulates. We show that each naive extension returns a maximal option of the theory over which the system is built. Note that the theory of a naive extension may be a proper subset of the corresponding maximal option. This is mainly due to the fact that an option may contain non-activated rules while arguments are minimal and thus focussed.

Example 2 (Cont). Since theory T 2 is consistent, then it has a single (maximal) option which is the theory itself. Any AS built over T 2 and which obeys the postulates and whose attack relation is conflict-dependent will have a single naive extension E with Th(E) = (F , {r 1 , r 2 }, {r 5 }) ⊏ T 2 . Rules r 3 and r 5 are not used in arguments.

Notation For E naive extension of H s.t. O in Max(Opt(T )) satisfies Th(E) ⊑ O and

Concs(E) = CN(O), let Option(E) def = O.
We prove that no two naive extensions return the same option. Moreover, naive extensions are closed in terms of arguments. Theorem 3. Let H = (Arg(T ), R) be an AS built over a theory T s.t. R is conflictdependent and H satisfies the postulates 1, 2, 3, and 4.

-For all E, E ′ ∈ Ext n (H), if Option(E) = Option(E ′ ), then E = E ′ -For all E ∈ Ext n (H), E = Arg(Option(E))
We have shown that each naive extension captures exactly one maximal option and it supports all, and only, the consequences of that option. Theorem 4 states that every option has a corresponding naive extension. So, there is a bijection from the set of naive extensions to the set of maximal options. -

For all O ∈ Max(Opt(T )), Arg(O) ∈ Ext n (H). -For all O ∈ Max(Opt(T )), O = Option(Arg(O)) -For all O, O ′ ∈ Max(Opt(T )), if Arg(O) = Arg(O ′ ) then O = O ′ .
Example 3 (Cont). The theory T 3 has three options, of which only two are maximal: Max(Opt(T )) = {O 1 , O 3 }. For all argumentation system H built over T 3 , if the attack relation of H is to be conflict-dependent and the postulates satisfied, then Ext n (H) = {Arg(O 1 ), Arg(O 3 )}.

It is thus possible to delimit the number of naive extensions of any argumentation system that satisfies the four postulates. What about the plausible conclusions that are drawn from a theory using an argumentation system that satisfies the postulates? From the previous results, it is easy to show that they are the literals that follow from all the maximal options. Theorem 5. Let H = (Arg(T ), R) be an AS built over a theory T s.t. R is conflictdependent and H satisfies the postulates 1, 2, 3, and 4.

Output(H) = O i ∈Max(Opt(T )) CN(O i )
Example 3 (Cont). Any argumentation system H that can be built over the theory T 3 and has a conflict-dependent attack relation and satisfies the postulates 1, 2, 3, 4 will have as output the set Output(H) = CN(O 1 ) ∩ CN(O 2 ) = {p, q, ¬s, u}.

Stable Semantics

We now analyze the outcomes of rule-based argumentation systems under stable semantics, again considering only systems that satisfy the rationality postulates. We show that such systems have stable extensions if the set of facts is not empty. Theorem 6. Let T = (F , S, D) be a theory.Whenever H = (Arg(T ), R) is an AS satisfying postulate 4, |Ext s (H)| = 0 iff F = ∅.

As for naive extensions, stable extensions of any argumentation system that satisfies the postulates return maximal options of the theory at hand. Theorem 7. Let H = (Arg(T ), R) be an AS defined over a theory T s.t. R is conflictdependent and H satisfies the postulates 1, 2, 3, 4. For all

E ∈ Ext s (H), ∃!O ∈ Max(Opt(T )) s.t. -Th(E) ⊑ O and Concs(E) = CN(O). -E = Arg(O).
Two stable extensions capture distinct options. Systems that use relations in ℜ s 1 choose a proper subset of the maximal options of T and make inferences from them. Their output sets are as follows: Theorem 9. Let H = (Arg(T ), R) be an argumentation system built over a theory

Theorem 8. Let H = (Arg(T ), R) be an AS defined over a theory T s.t. R is conflict- dependent and H satisfies the postulates 1, 2, 3, 4. For all E, E ′ ∈ Ext s (H), if Option(E) = Option(E ′ ) then E = E ′ .
T s.t. R ∈ ℜ s 1 . Output(H) = O i ∈S CN(O i ) with S = {O i ∈ Max(Opt(T )) | Arg(O i ) ∈ Ext s (H)}.
These attack relations introduce a "critical discrimination" between the maximal options of a theory. Hence, great care must be exercised when designing rule-based argumentation systems based on stable semantics: The principles governing the interaction between ⇒ and R must be both rigorously and meticulously specified so as to avoid trouble of which the following example is an easy case.

Example 5. Let T 5 be s.t. F 5 = {p, q} and S 5 = ∅ and D 5 = {p ⇒ s, q ⇒ ¬s}. T 5 has two maximal options: O 1 = (F 5 , S 5 , {p ⇒ s}) and O 2 = (F 5 , S 5 , {q ⇒ ¬s}).

For any system H = (Arg(T 5 ), R) s.t. R ∈ ℜ s 1 , either i) Ext s (H) = {Arg(O 1 )} or ii) Ext s (H) = {Arg(O 2 )}. In case (i), s ∈ Output(H) and ¬s / ∈ Output(H). In case (ii), ¬s is the plausible conclusion. Either choice would be arbitrary.

Attack relations of category ℜ s2 induce a bijection between the stable extensions of an argumentation system and the maximal options of the theory over which it is built.

Theorem 10. Let T = (Arg(T ), R) be an argumentation system over a theory T s.t. R ∈ ℜ s2 . For all O ∈ Max(Opt(T )), Arg(O) ∈ Ext s (H).

Argumentation systems with an attack relation from ℜ s2 are coherent, meaning that the preferred extensions exhaust all and only the stable ones.

Theorem 11. Let T = (Arg(T ), R) be an argumentation system over a theory T s.t.

R ∈ ℜ s2 . Ext s (H) = Ext p (H) = Ext n (H).
Attack relations in category ℜ s2 conform exactly to the result obtained under naive semantics: Plausible conclusions for them are already characterized in Theorem 5.

To sum up, attack relations satisfying the postulates can be split into two categories: ℜ s 1 and ℜ s 2 . Relations from ℜ s 2 do not offer added value as they make the stable semantics case to collapse to the naive semantics case. For stable semantics to substantiate (as compared with naive semantics) a rule-based argumentation system, attack relations from category ℜ s 1 must be favored. However, pitfalls threaten as options are discarded, and a lot of care must be exercised when designing such a system.

Preferred Semantics

Preferred semantics was initially proposed to overcome the limitation of stable semantics which does not guarantee the existence of extensions. Indeed, any argumentation system has at least one preferred extension which may be empty. We show that in case of rule-based systems the empty set cannot be an extension.

Proposition 9. Let H be an AS built over a theory

T = (F , S, D) s.t. H satisfies strict precedence. Ext p (H) = {∅} iff F = ∅.
Unlike the cases of naive and stable extensions, a preferred extension may capture only a sub-part of the consequences drawn from a maximal option. From the previous result, it follows that the number of preferred extensions does not exceed the number of maximal options of the theory over which the system is built. Theorem 14. Let H = (Arg(T ), R) be a system built over a theory T s.t. R is conflictdependent and H satisfies Postulates 1,[START_REF] Amgoud | Inferring from inconsistency in preference-based argumentation frameworks[END_REF][START_REF] Caminada | On the evaluation of argumentation formalisms[END_REF]and 4. |Ext

p (H)| ≤ |Max(Opt(T ))|.
Regarding the outputs of a rule-based argumentation system under preferred semantics, there are two cases: i) Attack relations of category R s2 lead to coherent systems whose plausible conclusions are characterized by Theorem 5. Thus, naive, stable and preferred semantics coincide. ii) Attack relations of category R s1 lead to pick up some maximal options and to reason about them. The plausible conclusions are given by Theorem 9. Thus the situation about preferred semantics is similar with that for stable semantics: For preferred semantics to offer added value over naive semantics, the attack relation chosen must discard some maximal options but it takes a lot of care to specify such an attack relation in full generality.

Grounded Semantics -Ideal Semantics

This section analyses the outcomes of rule-based systems under grounded and ideal semantics. We show that the ideal extension is exactly the set of arguments built from the free part of a theory. The free part of a theory T = (F , S, D), denoted by Free(T ), is a sub-theory (F , S, D ′ ) where D ′ = ∩D i where (F , S, D i ) ∈ Opt(T ). In other words, D ′ contains all the defeasible rules that are not involved in any conflict.

Proposition 10. Let T be a theory. CN(Free(T )) is consistent.

We show that when the attack relation satisfies a very natural requirement, then Arg(Free(T )) is admissible (i.e., it is conflict-free and defends all its elements). As far as we know, all the attack relations in existing rule-based argumentation systems privilege strict arguments.

Theorem 15. Let H = (Arg(T ), R) be a system built over a theory T s.t. R is conflictdependent and privileges strict arguments. Arg(Free(T )) is admissible.

The set Arg(Free(T )) is part of every preferred extension.

Theorem 16. Let H = (Arg(T ), R) be an AS over a theory T s.t. R is conflictdependent and privileges strict arguments, and H satisfies Postulates 1, 3, 4. Arg(Free(T )) ⊆ E i ∈Ext p (H) E i .

We show next that in case of attack relations of category ℜ s2 , Arg(Free(T )) is equal to the intersection of all preferred extensions. Recall that in this case, preferred extensions coincide with stable extensions and with naive ones.

Theorem 17. Let H = (Arg(T ), R) be an AS over a theory T . If R ∈ ℜ s2 then Arg(Free(T )) = E i ∈Ext x (H) E i .

From the previous result, it follows that when the attack relation is of category ℜ s2 and privileges strict arguments, then Arg(Free(T )) is the ideal extension.

Theorem 18. Let H = (Arg(T ), R) be an AS over a theory T . If R ∈ ℜ s2 and privileges strict arguments, then -Arg(Free(T )) is the ideal extension of H.

-The grounded extension of H is a subset of Arg(Free(T )).

The above result shows that ideal and grounded semantics allow the inference of literals only from the free part of a theory. Note also that grounded extension is more cautious than ideal one and may miss intuitive (free) conclusions.

Conclusion

The paper provides the first investigation on the outputs of rule-based argumentation systems. The study is general in the sense that it keeps the attack relation unspecified. Thus, the system can be instantiated with any of the attack relations that are used in existing systems. The results show that under naive semantics, the systems return the literals that follow from all the options of the theory at hand. Stable and preferred semantics either do not provide an added value wrt naive semantics or the attack relation of a system should be formalized in a very rigorous way in order to avoid arbitrary results. Ideal semantics returns the free part of a theory whereas the grounded semantics returns a sub-part of the free part meaning that it may miss interesting conclusions.

Proposition 3 .

 3 If an argumentation system H satisfies consistency and closure under sub-arguments, then ∀E ∈ Ext x (H), CN(Th(E)) is consistent.

Proposition 4 .

 4 Let H be an AS built over a theory T = (F , S, D). If H satisfies strict precedence, then F ⊆ CN((F , S, ∅)) ⊆ Output(H).

Proposition 5 .

 5 Let H be an argumentation system built over a theory T = (F , S, D). If H satisfies postulates 2, 3, 4, then for all E ∈ Ext x (H), CN(Th(E)) = CN((F , S, (d,x)∈E Def(d))).

Example 4 .

 4 The theory T 4 s.t. F 4 = {p, q}, S 4 = {p → s} and D 4 = {q ⇒ ¬s} has a single option: O = (F 4 , S 4 , ∅).

Theorem 2 .

 2 Let H = (Arg(T ), R) be an AS built over a theory T s.t. R is conflictdependent and H satisfies the postulates 1, 2, 3, and 4. For all E ∈ Ext n (H), there exists a unique O ∈ Max(Opt(T )) such that Th(E) ⊑ O and Concs(E) = CN(O).

Theorem 4 .

 4 Let H = (Arg(T ), R) be an AS built over a theory T s.t. R is conflictdependent and H satisfies the postulates 1, 2, 3, and 4.

Corollary 1 .

 1 Let H = (Arg(T ), R) be an AS built over a theory T s.t. R is conflictdependent and H satisfies the postulates 1, 2, 3, and 4. The equality |Ext n (H)| = |Max(Opt(T ))| holds.

Corollary 2 .

 2 Let H = (Arg(T ), R) be an AS defined over a theory T = (F , S, D) s.t. F = ∅ and R is conflict-dependent and H satisfies Postulates 1,2,3,4. It holds that 1 ≤ |Ext s (H)| ≤ |Max(Opt(T ))|. Theorem 7 does not guarantee that each maximal option of a theory T has a corresponding stable extension. The equality |Ext s (H)| = |Max(Opt(T ))| depends on the attack relation. Let ℜ s be the set of all attack relations that are conflict-dependent and that ensure Postulates 1, 2, 3, 4 under stable semantics. This set contains two disjoints subsets of attack relations, i.e. ℜ s = ℜ s 1 ∪ ℜ s 2 : -ℜ s 1 : the relations s.t. |Ext s (H)| < |Max(Opt(T ))| -ℜ s 2 : the relations s.t. |Ext s (H)| = |Max(Opt(T ))|

Theorem 12 .

 12 Let H = (Arg(T ), R) be an AS built over a theory T s.t. R is conflictdependent and H satisfies the postulates 1 and 3. For all E ∈ Ext p (H), ∃O ∈ Max(Opt(T )) s.t. Th(E) ⊑ O and Concs(E) ⊆ CN(O).

  Two preferred extensions refer to different options. Theorem 13. Let H = (Arg(T ), R) be an argumentation system s.t. R is conflictdependent and H satisfies the postulates 1, 2, 3, and 4. Let E, E ′ ∈ Ext p (H) and O ∈ Max(Opt(T )). If Th(E) ⊑ O and Th(E ′ ) ⊑ O, then E = E ′ .

Definition 13 .

 13 Let H = (Arg(T ), R) be an AS over a theory T . An attack relation R privileges strict arguments iff for all a = (d, x), b = (d ′ , x ′ ) ∈ Arg(T ), if a is strict and Seq(d) ∪ Seq(d ′ ) is inconsistent, then aRb.