[DL] Horn clauses and DLs

[Enrico Franconi]

On 1 Oct 2004, at 17:15, Rodrigo de Salvo Braz wrote:

> On Fri, 1 Oct 2004, Alex Borgida wrote:
>
>> shows that the two techniques are incomparable. (Prolog cannot encode
>> disjunction, which is easily encoded in DLs. While DL's cannot encode
>>  p:- e(x1,x2),e(x1,x3),... with all permutations of x_i and x_j
>> combinations.
>
> Thanks. I didn't mean to say that there was a containment relationship
> between some DL language and Horn clauses. But there isn't such a
> relationship between many pairs of different DLs also.

Horn clauses encode only polynomial problems. Standard DL's (from ALC 
up, including the DL's implementted in systems such as iFaCT and Racer) 
encode up to EXPTIME problems (and coNP in data complexity).

> The reason I am asking this is because I get the feeling from many 
> people
> that if you have some practical application in which you want a 
> tractable
> language, then you should immediately restrict yourself to choosing 
> from
> DL languages.

Where do you get this feeling from?

> I question this, and think that Horn should also be included
> as one of the options. Sure, it has its own tradeoffs that have to be
> considered, but I don't see a *a priori* reason to rule it out. That's 
> why
> I am writing, to check if people in this list can give me such a 
> reason.

There is a wide variety of decidable (and poly) fragments of FOL - not 
only Horn clauses. One reason for not considering them in KR is that 
they do not offer a "structured" way to represent knowledge, which I 
believe is a crucial feature of KR languages. Other than that, I am in 
favour of any well-founded logic-based formalism :-)

cheers
--e.