Please wait ... |

Link to record
http://hj.diva-portal.org/smash/person.jsf?pid=authority-person:49740 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt122_recordDirectLink",{id:"formSmash:upper:j_idt122:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt122_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt122_j_idt124",{id:"formSmash:upper:j_idt122:j_idt124",widgetVar:"widget_formSmash_upper_j_idt122_j_idt124",target:"formSmash:upper:j_idt122:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Schmidt, Johannes

Open this publication in new window or tab >>Parameterised Complexity of Abduction in Schaefer’s Framework### Mahmood, Y.

### Meier, A.

### Schmidt, Johannes

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_some",{id:"formSmash:j_idt184:0:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_otherAuthors",{id:"formSmash:j_idt184:0:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_otherAuthors",multiple:true}); 2020 (English)In: Logical Foundations of Computer Science: International Symposium, LFCS 2020, Deerfield Beach, FL, USA, January 4–7, 2020 Proceedings / [ed] Artemov S., Nerode A., Cham: Springer, 2020, p. 195-213Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Cham: Springer, 2020
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 11972
##### Keywords

Abduction, Co-clones, Parameterised complexity, Schaefer’s framework, Algebra, Cloning, Cobalt compounds, Parameterization, Abductive reasoning, Algebraic approaches, Constraint Satisfaction, Fine-grained analysis, Reasoning problems, Constraint satisfaction problems
##### National Category

Computational Mathematics
##### Identifiers

urn:nbn:se:hj:diva-47488 (URN)10.1007/978-3-030-36755-8_13 (DOI)2-s2.0-85077493558 (Scopus ID)9783030367541 (ISBN)978-3-030-36755-8 (ISBN)
##### Conference

International Symposium, LFCS 2020 Deerfield Beach, FL, USA, January 4–7, 2020
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt359",{id:"formSmash:j_idt184:0:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt365",{id:"formSmash:j_idt184:0:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt371",{id:"formSmash:j_idt184:0:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt371",multiple:true});
#####

Available from: 2020-01-22 Created: 2020-01-22 Last updated: 2020-01-23Bibliographically approved

Institut für Theoretische Informatik, Leibniz Universität Hannover, Hanover, Germany.

Institut für Theoretische Informatik, Leibniz Universität Hannover, Hanover, Germany.

Jönköping University, School of Engineering, JTH, Computer Science and Informatics.

Abductive reasoning is a non-monotonic formalism stemming from the work of Peirce. It describes the process of deriving the most plausible explanations of known facts. Considering the positive version asking for sets of variables as explanations, we study, besides asking for existence of the set of explanations, two explanation size limited variants of this reasoning problem (less than or equal to, and equal to). In this paper, we present a thorough two-dimensional classification of these problems. The first dimension is regarding the parameterised complexity under a wealth of different parameterisations. The second dimension spans through all possible Boolean fragments of these problems in Schaefer’s constraint satisfaction framework with co-clones (STOC 1978). Thereby, we almost complete the parameterised picture started by Fellows et al. (AAAI 2012), partially building on results of Nordh and Zanuttini (Artif. Intell. 2008). In this process, we outline a fine-grained analysis of the inherent parameterised intractability of these problems and pinpoint their FPT parts. As the standard algebraic approach is not applicable to our problems, we develop an alternative method that makes the algebraic tools partially available again.

Open this publication in new window or tab >>Paradigms for Parameterized Enumeration### Creignou, Nadia

### Meier, Arne

### Müller, Julian-Steffen

### Schmidt, Johannes

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_some",{id:"formSmash:j_idt184:1:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_some",multiple:true}); ### Vollmer, Heribert

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_otherAuthors",{id:"formSmash:j_idt184:1:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_1_j_idt188_j_idt202",{id:"formSmash:j_idt184:1:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"Show others..."}); 2017 (English)In: Theory of Computing Systems, ISSN 1432-4350, E-ISSN 1433-0490, Vol. 60, no 4, p. 737-758Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2017
##### Keywords

Parameterized complexity, Kernel, Enumeration, Parameterized enumeration, Algorithms, Self-reducibility
##### National Category

Computer and Information Sciences Discrete Mathematics
##### Identifiers

urn:nbn:se:hj:diva-34361 (URN)10.1007/s00224-016-9702-4 (DOI)000399178400007 ()2-s2.0-84987638662 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt359",{id:"formSmash:j_idt184:1:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt365",{id:"formSmash:j_idt184:1:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt371",{id:"formSmash:j_idt184:1:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt371",multiple:true});
#####

##### Note

CNRS, Aix-Marseille Université, France.

Institut für Theoretische Informatik, Gottfried Wilhelm Leibniz Universität, Germany.

Institut für Theoretische Informatik, Gottfried Wilhelm Leibniz Universität, Germany.

Department of Computer and Information Science, Linköping University, Sweden.

Institut für Theoretische Informatik, Gottfried Wilhelm Leibniz Universität, Germany.

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: FPT-enumeration and delayFPT. 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. Furthermore, we study the parameterized complexity of enumerating all models of Boolean formulas having weight at least *k*, where *k* is the parameter, in the famous Schaefer’s framework. We consider propositional formulas that are conjunctions of constraints taken from a fixed finite set Γ. Given such a formula and an integer *k*, we are interested in enumerating all the models of the formula that have weight at least *k*. We obtain a dichotomy classification and prove that, according to the properties of the constraint language Γ, either one can enumerate all such models in delayFPT, or no such delayFPT enumeration algorithm exists under some complexity-theoretic assumptions.

A preliminary version of this paper appeared in the proceedings of MFCS 2013, LNCS 8087, pp. 290–301.

Available from: 2016-12-19 Created: 2016-12-19 Last updated: 2018-01-13Bibliographically approvedOpen this publication in new window or tab >>The Weight in Enumeration### Schmidt, Johannes

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_some",{id:"formSmash:j_idt184:2:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_otherAuthors",{id:"formSmash:j_idt184:2:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_otherAuthors",multiple:true}); 2017 (English)In: Language and Automata Theory and Applications / [ed] Frank DrewesCarlos, Martín-Vide, Bianca Truthe, Springer, 2017, p. 208-219Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer, 2017
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 10168
##### Keywords

Computational complexity, Enumeration, Non-decreasing weight, Polynomial delay, Post’s lattice, MaxOnes
##### National Category

Computer and Information Sciences
##### Identifiers

urn:nbn:se:hj:diva-35525 (URN)10.1007/978-3-319-53733-7_15 (DOI)000418579700015 ()978-3-319-53732-0 (ISBN)978-3-319-53733-7 (ISBN)
##### Conference

LATA 2017, 11th International Conference on Language and Automata Theory and Applications, Umeå, 6-9 March, 2017.
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt359",{id:"formSmash:j_idt184:2:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt365",{id:"formSmash:j_idt184:2:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt371",{id:"formSmash:j_idt184:2:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt371",multiple:true});
#####

Available from: 2017-05-16 Created: 2017-05-16 Last updated: 2018-01-19Bibliographically approved

Jönköping University, Jönköping International Business School, JIBS, Informatics.

In our setting enumeration amounts to generate all solutions of a problem instance without duplicates. We address the problem of enumerating the models of B-formulæ. A B-formula is a propositional formula whose connectives are taken from a fixed set B of Boolean connectives. Without imposing any specific order to output the solutions, this task is solved. We completely classify the complexity of this enumeration task for all possible sets of connectives B imposing the orders of (1) non-decreasing weight, (2) non-increasing weight; the weight of a model being the number of variables assigned to 1. We consider also the weighted variants where a non-negative integer weight is assigned to each variable and show that this add-on leads to more sophisticated enumeration algorithms and even renders previously tractable cases intractable, contrarily to the constraint setting. As a by-product we obtain also complexity classifications for the optimization problems known as MIN-ONESMIN-ONES and MAX-ONESMAX-ONES which are in the B-formula setting two different tasks.

Open this publication in new window or tab >>On the parameterized complexity of non-monotonic logics### Meier, Arne

### Schindler, Irina

### Schmidt, Johannes

### Thomas, Michael

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_some",{id:"formSmash:j_idt184:3:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_some",multiple:true}); ### Vollmer, Heribert

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_otherAuthors",{id:"formSmash:j_idt184:3:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_3_j_idt188_j_idt202",{id:"formSmash:j_idt184:3:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"Show others..."}); 2015 (English)In: Archive for mathematical logic, ISSN 0933-5846, E-ISSN 1432-0665, Vol. 54, no 5-6, p. 685-710Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer Verlag (Germany), 2015
##### Keywords

Abduction; Autoepistemic logic; Default logic; Circumscription; Parameterized complexity; Courcelles theorem; Monadic second order logic
##### National Category

Computer and Information Sciences
##### Identifiers

urn:nbn:se:hj:diva-31614 (URN)10.1007/s00153-015-0435-x (DOI)000358581600013 ()2-s2.0-84938960398 (Scopus ID)
##### External cooperation:

#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt359",{id:"formSmash:j_idt184:3:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt365",{id:"formSmash:j_idt184:3:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt371",{id:"formSmash:j_idt184:3:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt371",multiple:true});
#####

##### Note

Leibniz University of Hannover, Germany.

Leibniz University of Hannover, Germany.

Linköpings universitet, Programvara och system.

Leibniz University of Hannover, Germany.

Leibniz University of Hannover, Germany.

We investigate the application of Courcelles theorem and the logspace version of Elberfeld et al. in the context of non-monotonic reasoning. Here we formalize the implication problem for propositional sets of formulas, the extension existence problem for default logic, the expansion existence problem for autoepistemic logic, the circumscriptive inference problem, as well as the abduction problem in monadic second order logic and thereby obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu, resp., XLnu) under standard complexity assumptions.

Funding Agencies|DFG [VO 630/6-2, ME 4279/1-1]

Available from: 2015-08-24 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approvedOpen this publication in new window or tab >>Complexity Classifications for Logic-Based Argumentation### Creignou, Nadia

### Egly, Uwe

### Schmidt, Johannes

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_some",{id:"formSmash:j_idt184:4:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_otherAuthors",{id:"formSmash:j_idt184:4:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_otherAuthors",multiple:true}); 2014 (English)In: ACM Transactions on Computational Logic, ISSN 1529-3785, E-ISSN 1557-945X, Vol. 15, no 3, article id 19Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Association for Computing Machinery (ACM), 2014
##### Keywords

Theory; Computational complexity; generalized satisfiability; logic-based argumentation; Schaefer
##### National Category

Computer and Information Sciences
##### Identifiers

urn:nbn:se:hj:diva-31616 (URN)10.1145/2629421 (DOI)000343693300002 ()2-s2.0-84907578385 (Scopus ID)
##### External cooperation:

#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt359",{id:"formSmash:j_idt184:4:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt365",{id:"formSmash:j_idt184:4:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt371",{id:"formSmash:j_idt184:4:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt371",multiple:true});
#####

##### Note

Aix Marseille University, France.

Vienna University of Technology, Austria.

Linköpings universitet, Programvara och system.

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.

Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden; Austrian Science Foundation (FWF) [S11409-N23]

Available from: 2014-11-28 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approvedOpen this publication in new window or tab >>Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis### Jonsson, Peter

### Lagerkvist, Victor

### Schmidt, Johannes

### Uppman, Hannes

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_some",{id:"formSmash:j_idt184:5:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_otherAuthors",{id:"formSmash:j_idt184:5:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_otherAuthors",multiple:true}); 2014 (English)In: Proceedings, Part II, Springer Berlin/Heidelberg , 2014, p. 408-419Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer Berlin/Heidelberg, 2014
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 8635
##### National Category

Computer and Information Sciences
##### Identifiers

urn:nbn:se:hj:diva-31615 (URN)10.1007/978-3-662-44465-8_35 (DOI)000358254600035 ()2-s2.0-84906261436 (Scopus ID)978-3-662-44464-1 (ISBN)978-3-662-44465-8 (ISBN)
##### Conference

39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt359",{id:"formSmash:j_idt184:5:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt365",{id:"formSmash:j_idt184:5:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt371",{id:"formSmash:j_idt184:5:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt371",multiple:true});
#####

Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved

Linköpings universitet, Programvara och system.

Linköpings universitet, Programvara och system.

Linköpings universitet, Programvara och system.

Linköpings universitet, Programvara och system.

Obtaining lower bounds for NP-hard problems has for a long time been an active area of research. Recent algebraic techniques introduced by Jonsson et al. (SODA 2013) show that the time complexity of the parameterized SAT(·) problem correlates to the lattice of strong partial clones. With this ordering they isolated a relation R such that SAT(R) can be solved at least as fast as any other NP-hard SAT(·) problem. In this paper we extend this method and show that such languages also exist for the max ones problem (Max-Ones(Γ)) and the Boolean valued constraint satisfaction problem over finite-valued constraint languages (VCSP(Δ)). With the help of these languages we relate Max-Ones and VCSP to the exponential time hypothesis in several different ways.

Open this publication in new window or tab >>Paradigms for Parameterized Enumeration### Creignou, Nadia

### Meier, Arne

### Müller, Julian-Steffen

### Schmidt, Johannes

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_some",{id:"formSmash:j_idt184:6:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_some",multiple:true}); ### Vollmer, Heribert

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_otherAuthors",{id:"formSmash:j_idt184:6:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_6_j_idt188_j_idt202",{id:"formSmash:j_idt184:6:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"Show others..."}); 2013 (English)In: Mathematical Foundations of Computer Science 2013 / [ed] Krishnendu Chatterjee, Jirí Sgall, Springer Berlin/Heidelberg , 2013, p. 290-301Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Springer Berlin/Heidelberg, 2013
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 8087
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:hj:diva-31617 (URN)10.1007/978-3-642-40313-2_27 (DOI)978-3-642-40312-5 (ISBN)978-3-642-40313-2 (ISBN)
##### External cooperation:

##### Conference

38th International Symposium on Mathematical Foundations of Computer Science (MFCS-2013), Klosterneuburg, Austria, August 26-30, 2013
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt359",{id:"formSmash:j_idt184:6:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt365",{id:"formSmash:j_idt184:6:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt371",{id:"formSmash:j_idt184:6:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt371",multiple:true});
#####

Available from: 2013-12-18 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved

Aix-Marseille Université, France.

Leibniz Universität, Hannover, Germany.

Leibniz Universität, Hannover, Germany.

Linköpings universitet, Programvara och system.

Leibniz Universität, Hannover, Germany.

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.

Open this publication in new window or tab >>The Complexity of Abduction for Equality Constraint Languages### Schmidt, Johannes

### Wrona, Michal

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_some",{id:"formSmash:j_idt184:7:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_otherAuthors",{id:"formSmash:j_idt184:7:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_otherAuthors",multiple:true}); 2013 (English)In: Computer Science Logic 2013 / [ed] Simona Ronchi Della Rocca, 2013, p. 615-633Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Series

Leibniz International Proceedings in Informatics, ISSN 1868-8969 ; 23
##### Keywords

Abduction, infinite structures, equality constraint languages, computational complexity, algebraic approach
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:hj:diva-31618 (URN)10.4230/LIPIcs.CSL.2013.615 (DOI)978-3-939897-60-6 (ISBN)
##### External cooperation:

##### Conference

22nd EACSL Annual Conference on Computer Science Logic (CSL-2013) September 2-5, 2013, Torino, Italy
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt359",{id:"formSmash:j_idt184:7:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt365",{id:"formSmash:j_idt184:7:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt371",{id:"formSmash:j_idt184:7:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt371",multiple:true});
#####

Available from: 2013-12-18 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved

Linköpings universitet, Programvara och system.

Linköpings universitet, Programvara och system.

Abduction is a form of nonmonotonic reasoning that looks for an explanation for an observed manifestation according to some knowledge base. One form of the abduction problem studied in the literature is the propositional abduction problem parameterized by a structure \Gamma over the two-element domain. In that case, the knowledge base is a set of constraints over \Gamma, the manifestation and explanation are propositional formulas. In this paper, we follow a similar route. Yet, we consider abduction over infinite domain. We study the equality abduction problem parameterized by a relational first-order structure \Gamma over the natural numbers such that every relation in \Gamma is definable by a Boolean combination of equalities, a manifestation is a literal of the form (x = y) or (x != y), and an explanation is a set of such literals. Our main contribution is a complete complexity characterization of the equality abduction problem. We prove that depending on \Gamma, it is \Sigma^P_2-complete, or NP-complete, or in P.

Open this publication in new window or tab >>Complexity classifications for propositional abduction in Post's framework### Creignou, Nadia

### Schmidt, Johannes

### Thomas, Michael

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_some",{id:"formSmash:j_idt184:8:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_otherAuthors",{id:"formSmash:j_idt184:8:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_otherAuthors",multiple:true}); 2012 (English)In: Journal of logic and computation (Print), ISSN 0955-792X, E-ISSN 1465-363X, Vol. 22, no 5, p. 1145-1170Article in journal (Refereed) Published
##### Abstract [en]

##### Keywords

Abduction, boolean connective, computational complexity, Post's lattice, propositional logic, Boolean connectives, Knowledge base, Non-monotonic reasoning, NP Complete, Polynomial case, Knowledge based systems, Boolean functions
##### National Category

Computer and Information Sciences
##### Identifiers

urn:nbn:se:hj:diva-31620 (URN)10.1093/logcom/exr012 (DOI)000309469900008 ()2-s2.0-84866948930 (Scopus ID)
##### External cooperation:

#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt359",{id:"formSmash:j_idt184:8:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt365",{id:"formSmash:j_idt184:8:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt371",{id:"formSmash:j_idt184:8:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt371",multiple:true});
#####

Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved

Laboratoire d'Informatique Fondamentale, Unité Mixte de Recherche, Aix-Marseille Université, France.

Laboratoire d'Informatique Fondamentale, Unité Mixte de Recherche, Aix-Marseille Université, France.

TWT GmbH, Germany.

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.

Open this publication in new window or tab >>Complexity of logic-based argumentation in Schaefer's framework### Creignou, Nadia

### Schmidt, Johannes

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_some",{id:"formSmash:j_idt184:9:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_otherAuthors",{id:"formSmash:j_idt184:9:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_otherAuthors",multiple:true}); 2012 (English)In: Computational models of argument, IOS Press, 2012, no 1, p. 237-248Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

IOS Press, 2012
##### Series

Frontiers in Artificial Intelligence and Applications ; 245
##### Keywords

Complexity of argumentation, Generalized satisfiability, Logic-based argumentation, Schaefer, Formal logic, Knowledge based systems, Conjunctive normal forms, Finite languages, Logic-based argumentations, Propositional logic, Satisfiability, Verification problems, Computational linguistics
##### National Category

Computer and Information Sciences
##### Identifiers

urn:nbn:se:hj:diva-31621 (URN)10.3233/978-1-61499-111-3-237 (DOI)000349004000024 ()2-s2.0-84876270546 (Scopus ID)9781614991106 (ISBN)9781614991113 (ISBN)
##### External cooperation:

##### Conference

4th Conference on Computational Models of Argument (COMMA), Vienna, Austria, September 10-12, 2012
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt359",{id:"formSmash:j_idt184:9:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt365",{id:"formSmash:j_idt184:9:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt371",{id:"formSmash:j_idt184:9:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt371",multiple:true});
#####

Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved

LIF, Aix-Marseille Université, France.

LIF, Aix-Marseille Université, France.

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.