Re: RDF semantics: applications, formalism and education

On April 18, jos.deroo.jd@belgium.agfa.com writes:
> 
> 
> > It is not only decidable but also has the finite model property and a
> > Nexptime-complete satisfiability problem. Take a look at:
> >
> > E. Gradel, P. Kolaitis, and M. Vardi. On the decision problem for
> > two-variable first order logics. Bulletin of Symbolic Logic, 3:53-69,
> >1997.
> 
> Thanks!
> We found it on the web at http://www.math.ucla.edu/~asl/bsl/0301/0301-003.ps

Glad to be of service. If you are interested in this stuff it might be
worth mentioning that, from the point of view of DAML+OIL, the guarded
fragment is probably a more interesting/relevant decidable subset of
FOL: it stems from efforts to understand the (relatively) robust
decidability of modal/description logics and is closely related to
them. The idea was first proposed in:

H. Andreka, J. van Benthem, and I. Nemeti, Modal languages and
bounded fragments of predicate logic, Journal of Philosophical Logic,
27 (1998), pp. 217-274.

Since then Erich Graedel has also done a lot of interesting work in
this area and has several relevant papers available electronically -
take a look at:

http://www-mgi.informatik.rwth-aachen.de/Publications/Graedel/

and in particular:

http://www-mgi.informatik.rwth-aachen.de/Publications/pub/graedel/Gr-jsl99.ps

Regards, Ian

Received on Thursday, 19 April 2001 06:40:26 UTC