| 1. |
|
|
| 2. |
- Creignou, Nadia, et al.
(författare)
-
Complexité de l’argumentation dans le cadredu treillis de Post
- 2010
-
Konferensbidrag (refereegranskat)abstract
- Dans beaucoup de formalisations logiques de l’argumentation un ar-gument est présenté comme une paire (Φ,α), où le support Φ est un sous-ensemble consistant minimal d’une base de connaissances qui implique l’affirmationα. Dans la plupart des scénarii les arguments sont donnés dans le langage completde la logique propositionnelle. Dans un tel contexte le raisonnement est une tâche algorithmique très difficile. Par exemple, décider s’il existe un support pour une affirmation donnée est Σp2-complet. Afin de comprendre ce qui est à la source dela difficulté de ce problème (et d’identifier des fragments résolubles efficacement) nous nous intéressons aux arguments donnés sous la forme de formules propositionnelles dont les connecteurs logiques font partie d’un ensemble de fonctions booléennes donné. Nous considérons quatre problèmes de décision : existe-t-il unsupport pour un argument ? un argument est-il valide ? une formule donnée est-elle pertinente (resp. superflue) dans les prémisses d’un argument ? Nous classifions la complexité de ces problèmes selon tous les ensembles possibles deconnecteurs autorisés.
|
|
| 3. |
- Creignou, Nadia, et al.
(författare)
-
Complexity Classifications for Logic-Based Argumentation
- 2014
-
Ingår i: ACM Transactions on Computational Logic. - : Association for Computing Machinery (ACM). - 1529-3785 .- 1557-945X. ; 15:3, s. 19-
-
Tidskriftsartikel (refereegranskat)abstract
- We consider logic-based argumentation in which an argument is a pair (Phi, alpha), where the support Phi is a minimal consistent set of formulae taken from a given knowledge base (usually denoted by Delta) that entails the claim alpha (a formula). We study the complexity of three central problems in argumentation: the existence of a support Phi subset of Delta, the verification of a support, and the relevance problem (given psi, is there a support Phi such that psi is an element of Phi?). When arguments are given in the frill language of propositional logic, these problems are computationally costly tasks: the verification problem is DP-complete; the others are Sigma(P)(2)-complete. We study these problems in Schaefers famous framework where the considered propositional formulae are in generalized conjunctive normal form. This means that formulae are conjunctions of constraints built upon a fixed finite set of Boolean relations Gamma (the constraint language). We show that according to the properties of this language Gamma, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete, or Sigma(P)(2)-complete. We present a dichotomous classification, P or DP-complete, for the verification problem and a trichotomous classification for the relevance problem into either polynomial, NP-complete, or Sigma(P)(2)-complete. These last two classifications are obtained by means of algebraic tools.
|
|
| 4. |
- Creignou, Nadia, et al.
(författare)
-
Complexity classifications for propositional abduction in Post's framework
- 2012
-
Ingår i: Journal of logic and computation (Print). - : Oxford University Press (OUP). - 0955-792X .- 1465-363X. ; 22:5, s. 1145-1170
-
Tidskriftsartikel (refereegranskat)abstract
- In this article, we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining the world's behaviour, it aims at finding an explanation for some observed manifestation. In this article, we consider propositional abduction, where the knowledge base and the manifestation are represented by propositional formulæ. The problem of deciding whether there exists an explanation has been shown to be Σ2p-complete in general. We focus on formulæ in which the allowed connectives are taken from certain sets of Boolean functions. We consider different variants of the abduction problem in restricting both the manifestations and the hypotheses. For all these variants, we obtain a complexity classification for all possible sets of Boolean functions. In this way, we identify easier cases, namely NP-complete, coNP-complete and polynomial cases. Thus, we get a detailed picture of the complexity of the propositional abduction problem, hence highlighting the sources of intractability. Further, we address the problem of counting the full explanations and prove a trichotomous classification theorem.
|
|
| 5. |
- Creignou, Nadia, et al.
(författare)
-
Complexity of logic-based argumentation in Post's framework
- 2011
-
Ingår i: Argument and Computation. - : Informa UK Limited. - 1946-2166 .- 1946-2174. ; 2:2-3, s. 107-129
-
Tidskriftsartikel (refereegranskat)abstract
- Many proposals for logic-based formalisations of argumentation consider an argument as a pair (Φ,α), where the support Φ is understood as a minimal consistent subset of a given knowledge base which has to entail the claim α. In case the arguments are given in the full language of classical propositional logic reasoning in such frameworks becomes a computationally costly task. For instance, the problem of deciding whether there exists a support for a given claim has been shown to be Σ 2 p-complete. In order to better understand the sources of complexity (and to identify tractable fragments), we focus on arguments given over formul in which the allowed connectives are taken from certain sets of Boolean functions. We provide a complexity classification for four different decision problems (existence of a support, checking the validity of an argument, relevance and dispensability) with respect to all possible sets of Boolean functions. Moreover, we make use of a general schema to enumerate all arguments to show that certain restricted fragments permit polynomial delay. Finally, we give a classification also in terms of counting complexity.
|
|
| 6. |
- Creignou, Nadia, et al.
(författare)
-
Complexity of logic-based argumentation in Schaefer's framework
- 2012
-
Ingår i: Computational models of argument. - : IOS Press. - 9781614991106 - 9781614991113 ; , s. 237-248
-
Konferensbidrag (refereegranskat)abstract
- We consider logic-based argumentation in which an argument is a pair (Φ, α), where the support Φ is a minimal consistent set of formulæof a given knowledge base that entails the formula α. We study the complexity of two different problems: the existence of a support and the verification of the validity of an argument. When arguments are given in the full language of propositional logic these problems are computationally costly tasks, they are respectively ΣP 2- and DP-complete. We study these problems in Schaefer's famous framework. We consider the case where formulæare taken from a class of formulæin generalized conjunctive normal form. This means that the propositional formulæ considered are conjunctions of constraints taken from a fixed finite language Γ. We show that according to the properties of this language Γ, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete or ΣP 2-complete. We also obtain a dichotomous classification, P or DP-complete, for the verification problem.
|
|
| 7. |
- Creignou, Nadia, et al.
(författare)
-
Complexity of propositional abduction for restricted sets of Boolean functions
- 2010
-
Ingår i: Proceedings of the Twelfth International Conference on the Principles of Knowledge Representation and Reasoning (KR 2010). - : AAAI Press.
-
Konferensbidrag (refereegranskat)abstract
- Abduction is a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we focus on propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to beΣp2-complete in general. We consider variants obtained by restricting the allowed connectives in the formulae to certain sets of Boolean functions. We give a complete classification of the complexity for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete and polynomial cases; and we highlight sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.
|
|
| 8. |
- Creignou, Nadia, et al.
(författare)
-
Enumerating all solutions of a Boolean CSP by non-decreasing weight
- 2011
-
Ingår i: Theory and applications of satisfiability testing - SAT 2011. - Berlin : Springer. - 9783642215803 - 9783642215810 ; , s. 120-133
-
Konferensbidrag (refereegranskat)abstract
- We address the problem of enumerating all models of Boolean formulæ in order of non-decreasing weight in Schaefer's framework. The weight of a model is the number of variables assigned to 1. Tractability in this context amounts to enumerating all models one after the other in sorted order, with polynomial delay between two successive outputs. The question of model-enumeration has already been studied in Schaefer's framework, but without imposing a specific order. The order of non-decreasing weight changes the complexity considerably. We obtain a new dichotomous complexity classification. On the one hand, we develop new polynomial delay algorithms for Horn and 2-XOR-formulæ to enumerate the models by non-decreasing weight. On the other hand, we prove that in all other cases such a polynomial delay algorithm does not exist, unless P=NP.
|
|
| 9. |
|
|
| 10. |
- Creignou, Nadia, et al.
(författare)
-
Paradigms for Parameterized Enumeration
- 2013
-
Ingår i: Mathematical Foundations of Computer Science 2013. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642403125 - 9783642403132 ; , s. 290-301
-
Konferensbidrag (refereegranskat)abstract
- The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First we define formally different notions of efficient enumeration in the context of parameterized complexity. Second we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems.
|
|
