Change search
Link to record
Permanent link

Direct link
BETA
Schmidt, Johannes
Publications (10 of 18) Show all publications
Mahmood, Y., Meier, A. & Schmidt, J. (2020). Parameterised Complexity of Abduction in Schaefer’s Framework. In: Artemov S., Nerode A. (Ed.), Logical Foundations of Computer Science: International Symposium, LFCS 2020, Deerfield Beach, FL, USA, January 4–7, 2020 Proceedings. Paper presented at International Symposium, LFCS 2020 Deerfield Beach, FL, USA, January 4–7, 2020 (pp. 195-213). Cham: Springer
Open this publication in new window or tab >>Parameterised Complexity of Abduction in Schaefer’s Framework
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]

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.

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
Available from: 2020-01-22 Created: 2020-01-22 Last updated: 2020-01-23Bibliographically approved
Creignou, N., Meier, A., Müller, J.-S., Schmidt, J. & Vollmer, H. (2017). Paradigms for Parameterized Enumeration. Theory of Computing Systems, 60(4), 737-758
Open this publication in new window or tab >>Paradigms for Parameterized Enumeration
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]

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.

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)
Note

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 approved
Schmidt, J. (2017). The Weight in Enumeration. In: Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik (Ed.), Frank DrewesCarlos, Martín-Vide, Bianca Truthe (Ed.), Language and Automata Theory and Applications: . Paper presented at LATA 2017, 11th International Conference on Language and Automata Theory and Applications, Umeå, 6-9 March, 2017. (pp. 208-219). Springer
Open this publication in new window or tab >>The Weight in Enumeration
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]

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.

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.
Available from: 2017-05-16 Created: 2017-05-16 Last updated: 2018-01-19Bibliographically approved
Meier, A., Schindler, I., Schmidt, J., Thomas, M. & Vollmer, H. (2015). On the parameterized complexity of non-monotonic logics. Archive for mathematical logic, 54(5-6), 685-710
Open this publication in new window or tab >>On the parameterized complexity of non-monotonic logics
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]

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.

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:
Note

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 approved
Creignou, N., Egly, U. & Schmidt, J. (2014). Complexity Classifications for Logic-Based Argumentation. ACM Transactions on Computational Logic, 15(3), Article ID 19.
Open this publication in new window or tab >>Complexity Classifications for Logic-Based Argumentation
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]

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.

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:
Note

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 approved
Jonsson, P., Lagerkvist, V., Schmidt, J. & Uppman, H. (2014). Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis. In: Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, Zoltán Ésik (Ed.), Proceedings, Part II: . Paper presented at 39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014) (pp. 408-419). Springer Berlin/Heidelberg
Open this publication in new window or tab >>Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
2014 (English)In: Proceedings, Part II, Springer Berlin/Heidelberg , 2014, p. 408-419Conference paper, Published paper (Refereed)
Abstract [en]

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.

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)
Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved
Creignou, N., Meier, A., Müller, J.-S., Schmidt, J. & Vollmer, H. (2013). Paradigms for Parameterized Enumeration. In: Krishnendu Chatterjee, Jirí Sgall (Ed.), Mathematical Foundations of Computer Science 2013: . Paper presented at 38th International Symposium on Mathematical Foundations of Computer Science (MFCS-2013), Klosterneuburg, Austria, August 26-30, 2013 (pp. 290-301). Springer Berlin/Heidelberg
Open this publication in new window or tab >>Paradigms for Parameterized Enumeration
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]

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.

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
Available from: 2013-12-18 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved
Schmidt, J. & Wrona, M. (2013). The Complexity of Abduction for Equality Constraint Languages. In: Simona Ronchi Della Rocca (Ed.), Computer Science Logic 2013: . Paper presented at 22nd EACSL Annual Conference on Computer Science Logic (CSL-2013) September 2-5, 2013, Torino, Italy (pp. 615-633).
Open this publication in new window or tab >>The Complexity of Abduction for Equality Constraint Languages
2013 (English)In: Computer Science Logic 2013 / [ed] Simona Ronchi Della Rocca, 2013, p. 615-633Conference paper, Published paper (Refereed)
Abstract [en]

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.

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
Available from: 2013-12-18 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved
Creignou, N., Schmidt, J. & Thomas, M. (2012). Complexity classifications for propositional abduction in Post's framework. Journal of logic and computation (Print), 22(5), 1145-1170
Open this publication in new window or tab >>Complexity classifications for propositional abduction in Post's framework
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]

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.

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:
Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved
Creignou, N. & Schmidt, J. (2012). Complexity of logic-based argumentation in Schaefer's framework. In: Computational models of argument: . Paper presented at 4th Conference on Computational Models of Argument (COMMA), Vienna, Austria, September 10-12, 2012 (pp. 237-248). IOS Press (1)
Open this publication in new window or tab >>Complexity of logic-based argumentation in Schaefer's framework
2012 (English)In: Computational models of argument, IOS Press, 2012, no 1, p. 237-248Conference paper, Published paper (Refereed)
Abstract [en]

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.

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
Available from: 2016-09-01 Created: 2016-09-01 Last updated: 2018-01-10Bibliographically approved
Organisations

Search in DiVA

Show all publications