Logic

Studies

From 1993 to 2002 I studied Computer Science at the RWTH Aachen. There is a mirror of the personal homepage I had as research assistant at the Chair for Computer Science VII and Research Group on Mathematical Foundations of Computer Science.

Diploma Thesis

The Reliability of Queries

Completed 1998 - Abstract:

The reliability of database queries on databases with uncertain information is studied, on the basis of a probabilistic model for unreliable databases.

While it was already known that the reliability of quantifier-free queries is computable in polynomial time, we show here that already for conjunctive queries, the reliability may become highly intractable. We exhibit a conjunctive query whose reliability problem is complete for FP^#P. We further show, that FP^#P is the typical complexity level for the reliability problems of a very large class of queries, including all second-order queries.

We study approximation algorithms and prove that the reliabilities of all polynomial-time evaluable queries can be efficiently approximated by randomized algorithms.

Finally we discuss the extension of our approach to the more general metafinite database model where finite relational structures are endowed with functions into an infinite interpreted domain; in addition queries may use aggregate functions like in SQL. Our result that reliability problems of first-order queries have complexity FP^#P also holds on this extended model.

The German "Diplom" is about equivalent to an M.Sc.
Download Full Text

Dissertation

Guarded Logics: Algorithms and Bisimulation

Completed 2002 - Abstract:

For many practical applications of logic-based methods there is a requirement to balance expressive power against computational tractability. Both identifying decidable sub-classes of first-order logic, and extending modal logic to larger, but nevertheless efficiently solvable languages has been a preeminent goal of research.

The guarded fragment of first-order logic was a successful attempt to transfer key tractability properties of modal, temporal, and description logics to a larger fragment of predicate logic. Besides decidability, guarded logics inherit the finite model property, invariance under an appropriate variant of bisimulation, and other nice model theoretic properties including a decidable fixed-point extension.

The goal of this this work is to gain greater insight into the correspondence between the modal world and the guarded world. In this process, several gaps concerning basic, typically modal, features of guarded logics are closed. Guarded second order logic and guarded relational algebra are developed. A recurring key technique consists of encoding structures and formulae used in the guarded world as their modal counterparts. This enables the transfer of various results, as well as giving greater insight into the nature of guarded logics. Touched subjects include tableau-based decision procedures, mapping action guarded logics, canonisation of structures and model-theoretic characterisation theorems.

Download Full Text