- From: Ian Horrocks <horrocks@cs.man.ac.uk>
- Date: Wed, 18 Apr 2001 18:36:59 +0100 (BST)
- 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 UTC