André Hernich

AAAI Conference 2012 Conference Paper

Equality-Friendly Well-Founded Semantics and Applications to Description Logics

• Georg Gottlob
• André Hernich
• Clemens Kupke
• Thomas Lukasiewicz

We tackle the problem of defining a well-founded semantics for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a well-founded semantics (WFS) for the recent Datalog± family of ontology languages, which covers several important description logics (DLs). To do so, we generalize Datalog± by non-stratified nonmonotonic negation in rule bodies, and we define a WFS for this generalization via guarded fixed-point logic. We refer to this approach as equality-friendly WFS, since it has the advantage that it does not make the unique name assumption (UNA); this brings it close to OWL and its profiles as well as typical DLs, which also do not make the UNA. We prove that for guarded Datalog± with negation under the equality-friendly WFS, conjunctive query answering is decidable, and we provide precise complexity results for this problem. From these results, we obtain precise definitions of the standard WFS extensions of EL and of members of the DL-Lite family, as well as corresponding complexity results for query answering.

CSL Conference 2011 Conference Paper

L-Recursion and a new Logic for Logarithmic Space

• Martin Grohe
• Berit Grußien
• André Hernich
• Bastian Laubner

We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic LREC has a data complexity in LOGSPACE, and it defines LOGSPACE-complete problems like deterministic reachability and Boolean formula evaluation. We prove that LREC is strictly more expressive than deterministic transitive closure logic with counting and incomparable in expressive power with symmetric transitive closure logic STC and transitive closure logic (with or without counting). LREC is strictly contained in fixed-point logic with counting FPC. We also study an extension LREC= of LREC that has nicer closure properties and is more expressive than both LREC and STC, but is still contained in FPC and has a data complexity in LOGSPACE. Our main results are that LREC captures LOGSPACE on the class of directed trees and that LREC= captures LOGSPACE on the class of interval graphs.

TCS Journal 2008 Journal Article

Reversal complexity revisited

• André Hernich
• Nicole Schweikardt

MFCS Conference 2005 Conference Paper

Combining Self-reducibility and Partial Information Algorithms

• André Hernich
• Arfst Nickelsen

Abstract A partial information algorithm for a language A computes, for some fixed m, for input words x 1, .. ., x m a set of bitstrings containing χ A ( x 1, .. ., x m ). E. g. , p-selective, approximable, and easily countable languages are defined by the existence of polynomial-time partial information algorithms of specific type. Self-reducible languages, for different types of self-reductions, form subclasses of PSPACE. For a self-reducible language A, the existence of a partial information algorithm sometimes helps to place A into some subclass of PSPACE. The most prominent known result in this respect is: P-selective languages which are self-reducible are in P [9]. Closely related is the fact that the existence of a partial information algorithm for A simplifies the type of reductions or self-reductions to A. The most prominent known result in this respect is: Turing reductions to easily countable languages simplify to truth-table reductions[8]. We prove new results of this type. We show: 1 Self-reducible languages which are easily 2-countable are in P. This partially confirms a conjecture of [8]. 2 Self-reducible languages which are (2 m – 1, m )-verbose are truth-table self-reducible. This generalizes the result of [9] for p-selective languages, which are ( m + 1, m )-verbose. 3 Self-reducible languages, where the language and its complement are strongly 2-membership comparable, are in P. This generalizes the corresponding result for p-selective languages of [9]. 4 Disjunctively truth-table self-reducible languages which are 2-membership comparable are in UP. Topic: Structural complexity.