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: Wed, 18 Apr 2001 18:36:59 +0100 (BST)
Message-ID: <15069.53435.302104.55082@galahad.cs.man.ac.uk>
To: jos.deroo.jd@belgium.agfa.com
Cc: der@hplb.hpl.hp.com, GK@Ninebynine.org, phayes@ai.uwf.edu, www-rdf-logic@w3.org
On April 18, jos.deroo.jd@belgium.agfa.com writes:
> 
> 
> > > If anyone else can suggest some good intro reading on description
> > > logics for logical beginners, by the way, please speak up. Deborah,
> > > Peter, Ian?
> >
> > Having decided to study up on this fairly recently I found Enrico Franconi's
> > course slides plus references useful. They are at
> > http://www.cs.man.ac.uk/~franconi/dl/course/ which in turn is indexed from
> > the "Description Logics Homepage" at http://dl.kr.org/ which has other
> > useful pointers.
> 
> in http://www.cs.man.ac.uk/~franconi/dl/course/slides/comp-logic.ps.gz
> on page 36 we find
> [[[...
>    Logical implication is decidable if we
>    restrict to FOL using only at most two
>    variable names; such language is called L2.
> ]]]
> I'm fascinated by that but I couldn't find more details...

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.

Ian

p.s. You can also find an excellent overview of DLs, and in particular
of tableaux algorithms, at:

ftp://www-lti.informatik.rwth-aachen.de/pub/papers/2000/BaaderSattler-Tableaux-2000.ps.gz
Received on Wednesday, 18 April 2001 13:32:45 GMT

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