W3C home > Mailing lists > Public > www-rdf-logic@w3.org > April 2001

Re: RDF semantics: applications, formalism and education

From: Ian Horrocks <horrocks@cs.man.ac.uk>
Date: Thu, 19 Apr 2001 11:46:08 +0100 (BST)
Message-ID: <15070.49648.500366.351983@galahad.cs.man.ac.uk>
To: jos.deroo.jd@belgium.agfa.com
Cc: www-rdf-logic@w3.org, phayes@ai.uwf.edu, GK@Ninebynine.org, der@hplb.hpl.hp.com
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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:52:38 GMT