BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Arne Meier

Arne Meier appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityLogic in Computer ScienceArtificial IntelligenceData Structures and Algorithmsmath.LO

Catalog footprint

What is connected

19works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

19 published item(s)

preprint2021arXiv

Parameterised Counting in Logspace

In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). They defined the operators paraW and paraBeta for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators paraW and paraBeta by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[1] and paraBeta-Tail. Then, we consider counting versions of all four operators applied to logspace and obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0,1)-matrices is #paraBeta-Tail-L-hard and can be written as the difference of two functions in #paraBetaTail-L. For example, we show that the closure of #paraBetaTail-L under parameterised logspace parsimonious reductions coincides with #paraBeta-L, that is, modulo parameterised reductions, tail-nondeterminism with read-once access is the same as read-once nondeterminism. We show that all introduced classes are closed under addition and multiplication, and those without tail-nondeterminism are closed under parameterised logspace parsimonious reductions. Finally, we underline the significance of this topic by providing a promising outlook showing several open problems and options for further directions of research.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Parameterized Complexity of Logic-Based Argumentation in Schaefer's Framework

Logic-based argumentation is a well-established formalism modelling nonmonotonic reasoning. It has been playing a major role in AI for decades, now. Informally, a set of formulas is the support for a given claim if it is consistent, subset-minimal, and implies the claim. In such a case, the pair of the support and the claim together is called an argument. In this paper, we study the propositional variants of the following three computational tasks studied in argumentation: ARG (exists a support for a given claim with respect to a given set of formulas), ARG-Check (is a given set a support for a given claim), and ARG-Rel (similarly as ARG plus requiring an additionally given formula to be contained in the support). ARG-Check is complete for the complexity class DP, and the other two problems are known to be complete for the second level of the polynomial hierarchy (Parson et al., J. Log. Comput., 2003) and, accordingly, are highly intractable. Analyzing the reason for this intractability, we perform a two-dimensional classification: first, we consider all possible propositional fragments of the problem within Schaefer's framework (STOC 1978), and then study different parameterizations for each of the fragment. We identify a list of reasonable structural parameters (size of the claim, support, knowledge-base) that are connected to the aforementioned decision problems. Eventually, we thoroughly draw a fine border of parameterized intractability for each of the problems showing where the problems are fixed-parameter tractable and when this exactly stops. Surprisingly, several cases are of very high intractability (paraNP and beyond).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Enumerating Teams in First-Order Team Logics

We start the study of the enumeration complexity of different satisfiability problems in first-order team logics. Since many of our problems go beyond DelP, we use a framework for hard enumeration analogous to the polynomial hierarchy, which was recently introduced by Creignou et al. (Discret. Appl. Math. 2019). We show that the problem to enumerate all satisfying teams of a fixed formula in a given first-order structure is DelNP-complete for certain formulas of dependence logic and independence logic. For inclusion logic formulas, this problem is even in DelP. Furthermore, we study the variants of this problems where only maximal, minimal, maximum and minimum solutions, respectively, are considered. For the most part these share the same complexity as the original problem. An exception is the minimum-variant for inclusion logic, which is DelNP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Parametrised Complexity of Model Checking and Satisfiability in Propositional Dependence Logic

In this paper, we initiate a systematic study of the parametrised complexity in the field of Dependence Logics which finds its origin in the Dependence Logic of Väänänen from 2007. We study a propositional variant of this logic (PDL) and investigate a variety of parametrisations with respect to the central decision problems. The model checking problem (MC) of PDL is NP-complete. The subject of this research is to identify a list of parametrisations (formula-size, treewidth, treedepth, team-size, number of variables) under which MC becomes fixed-parameter tractable. Furthermore, we show that the number of disjunctions or the arity of dependence atoms (dep-arity) as a parameter both yield a paraNP-completeness result. Then, we consider the satisfiability problem (SAT) showing a different picture: under team-size, or dep-arity SAT is paraNP-complete whereas under all other mentioned parameters the problem is in FPT. Finally, we introduce a variant of the satisfiability problem, asking for teams of a given size, and show for this problem an almost complete picture.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Strong Backdoors for Default Logic

In this paper, we introduce a notion of backdoors to Reiter's propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor), for various kinds of target classes (cnf, horn, krom, monotone, identity). We show that backdoor detection is fixed-parameter tractable for the considered target classes, and backdoor evaluation is either fixed-parameter tractable, in para-DP2 , or in para-NP, depending on the target class.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Strong Backdoors for Linear Temporal Logic

In the present paper we introduce the notion of strong backdoors into the field of temporal logic for the CNF-fragment of linear temporal logic introduced by Fisher. We study the parameterised complexity of the satisfiability problem parameterised by the size of the backdoor. We distinguish between backdoor detection and evaluation of backdoors into the fragments of horn and krom formulas. Here we classify the operator fragments of globally-operators for past or future, and the combination of both. Detection is shown to be in FPT whereas the complexity of evaluation behaves different. We show that for krom formulas the problem is paraNP-complete. For horn formulas the complexity is shown to be either fixed parameter tractable or paraNP-complete depending on the considered operator fragment.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Team Based Variant of CTL

We introduce two variants of computation tree logic CTL based on team semantics: an asynchronous one and a synchronous one. For both variants we investigate the computational complexity of the satisfiability as well as the model checking problem. The satisfiability problem is shown to be EXPTIME-complete. Here it does not matter which of the two semantics are considered. For model checking we prove a PSPACE-completeness for the synchronous case, and show P-completeness for the asynchronous case. Furthermore we prove several interesting fundamental properties of both semantics.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parameterized Complexity of CTL: A Generalization of Courcelle's Theorem

We present an almost complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is the sum of temporal depth and structural pathwidth. The classification shows a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The only real operator fragment which is confirmed to be in FPT is the fragment containing solely AX. Also we prove a generalization of Courcelle's theorem to infinite signatures which will be used to proof the FPT-membership case.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The model checking fingerprints of CTL operators

The aim of this study is to understand the inherent expressive power of CTL operators. We investigate the complexity of model checking for all CTL fragments with one CTL operator and arbitrary Boolean operators. This gives us a fingerprint of each CTL operator. The comparison between the fingerprints yields a hierarchy of the operators that mirrors their strength with respect to model checking.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Paradigms for Parameterized Enumeration

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.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Parameterized Enumeration with Ordering

The classes Delay-FPT and Total-FPT recently have been introduced into parameterized complexity in order to capture the notion of efficiently solvable parameterized enumeration problems. In this paper we focus on ordered enumeration and will show how to obtain Delay-FPT and Total-FPT enumeration algorithms for several important problems. We propose a generic algorithmic strategy, combining well-known principles stemming from both parameterized algorithmics and enumeration, which shows that, under certain preconditions, the existence of a so-called neighbourhood function among the solutions implies the existence of a Delay-FPT algorithm which outputs all ordered solutions. In many cases, the cornerstone to obtain such a neighbourhood function is a Total-FPT algorithm that outputs all minimal solutions. This strategy is formalized in the context of graph modification problems, and shown to be applicable to numerous other kinds of problems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Generalized Complexity of ALC Subsumption

The subsumption problem with respect to terminologies in the description logic ALC is EXPTIME-complete. We investigate the computational complexity of fragments of this problem by means of allowed Boolean operators. Hereto we make use of the notion of clones in the context of Post's lattice. Furthermore we consider all four possible quantifier combinations for each fragment parameterized by a clone. We will see that depending on what quantifiers are available the classification will be either tripartite or a quartering.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Model Checking CTL is Almost Always Inherently Sequential

The model checking problem for CTL is known to be P-complete (Clarke, Emerson, and Sistla (1986), see Schnoebelen (2002)). We consider fragments of CTL obtained by restricting the use of temporal modalities or the use of negations---restrictions already studied for LTL by Sistla and Clarke (1985) and Markey (2004). For all these fragments, except for the trivial case without any temporal operator, we systematically prove model checking to be either inherently sequential (P-complete) or very efficiently parallelizable (LOGCFL-complete). For most fragments, however, model checking for CTL is already P-complete. Hence our results indicate that, in cases where the combined complexity is of relevance, approaching CTL model checking by parallelism cannot be expected to result in any significant speedup. We also completely determine the complexity of the model checking problem for all fragments of the extensions ECTL, CTL+, and ECTL+.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Parameterized Complexity of Default Logic and Autoepistemic Logic

We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld etal. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default logic, as well as the expansion existence problem for autoepistemic logic and 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), unless P=NP.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Complexity of Reasoning for Fragments of Default Logic

Default logic was introduced by Reiter in 1980. In 1992, Gottlob classified the complexity of the extension existence problem for propositional default logic as $\SigmaPtwo$-complete, and the complexity of the credulous and skeptical reasoning problem as SigmaP2-complete, resp. PiP2-complete. Additionally, he investigated restrictions on the default rules, i.e., semi-normal default rules. Selman made in 1992 a similar approach with disjunction-free and unary default rules. In this paper we systematically restrict the set of allowed propositional connectives. We give a complete complexity classification for all sets of Boolean functions in the meaning of Post's lattice for all three common decision problems for propositional default logic. We show that the complexity is a hexachotomy (SigmaP2-, DeltaP2-, NP-, P-, NL-complete, trivial) for the extension existence problem, while for the credulous and skeptical reasoning problem we obtain similar classifications without trivial cases.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Complexity of Satisfiability for Sub-Boolean Fragments of ALC

The standard reasoning problem, concept satisfiability, in the basic description logic ALC is PSPACE-complete, and it is EXPTIME-complete in the presence of unrestricted axioms. Several fragments of ALC, notably logics in the FL, EL, and DL-Lite family, have an easier satisfiability problem; sometimes it is even tractable. All these fragments restrict the use of Boolean operators in one way or another. We look at systematic and more general restrictions of the Boolean operators and establish the complexity of the concept satisfiability problem in the presence of axioms. We separate tractable from intractable cases.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

The Complexity of Satisfiability for Fragments of Hybrid Logic -- Part I

The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments. In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of modal and hybrid operators. We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators.

0 citations0 reviewsNo code linkedOpen access