- From: Ian Horrocks <horrocks@cs.man.ac.uk>
- Date: Thu, 19 Apr 2001 11:46:08 +0100 (BST)
- 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 UTC