Resolution-Based Decision Procedures for Subclasses of First-Order Logic
Universität des Saarlandes, March, 1999
This thesis studies decidable fragments of first-order logic which are
relevant to the field of non-classical logic and knowledge
representation.
We show that refinements of resolution based on suitable liftable
orderings provide decision procedures for the subclasses
$\CE^+$,
$\overline{\mathrm{K}}$,
and $\overline{\mathrm{DK}}$
of first-order logic. By the use of semantics-based translation methods
we can embed the description logic $\mathcal{ALCR}$
and extensions of the basic modal logic $\mathsf{K}$
into fragments of first-order logic.
We describe various decision procedures based on ordering refinements
and selection functions for these fragments and show that a polynomial
simulation
of tableaux-based decision procedures for these logics is
possible. In the final part of the thesis we develop a benchmark suite
and perform an empirical
analysis of various modal theorem provers.
Harald Ganzinger
Hans Jürgen Ohlbach
Harald Ganzinger
Completed
8
November
1999
Max-Planck-Institut für Informatik
Programming Logics Group
experts only
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat
BibTeX Entry:
@PHDTHESIS{Hustadt1999,
AUTHOR = {Hustadt, Ullrich},
TITLE = {Resolution-Based Decision Procedures for Subclasses of First-Order Logic},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {1999},
TYPE = {Doctoral dissertation}
MONTH = {March},
}
Entry last modified by Christine Kiesel, 03/12/2010