15 citations · 36 across the 5 of their papers we have counts for
5 papers
Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
Andre Hernich, Carsten Lutz, Fabio Papacchini +1
We study the complexity of ontology-mediated querying when ontologies are formulated in the guarded fragment of first-order logic (GF). Our general aim is to classify the data comp…
L-Recursion and a new Logic for Logarithmic Space
Martin Grohe, Berit Grußien, André Hernich +1
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…
Answering Non-Monotonic Queries in Relational Data Exchange
Andre Hernich
Relational data exchange is the problem of translating relational data from a source schema into a target schema, according to a specification of the relationship between the sourc…
Randomized Computations on Large Data Sets: Tight Lower Bounds
Martin Grohe, Andre Hernich, Nicole Schweikardt
We study the randomized version of a computation model (introduced by Grohe, Koch, and Schweikardt (ICALP'05); Grohe and Schweikardt (PODS'05)) that restricts random access to exte…
Reversal Complexity Revisited
Andre Hernich, Nicole Schweikardt
We study a generalized version of reversal bounded Turing machines where, apart from several tapes on which the number of head reversals is bounded by r(n), there are several furth…