Re: deductive databases

alex goldman <hello_at_spamm.er> writes:

> You wrote: "FOL can get rid of function symbols and be as expressive as
> with them"
>
> Abiteboul & Vianu write: "[FOL without function symbols] has limited
> expressive power. For instance, it cannot compute the transitive closure of
> a graph"

It muddies the waters a bit to talk about what a logic can "compute"; bit still I don't see why these statements are contradictory, as you seem to believe.

In fact the notion of transitive closure is not expressible in FOL, even with function symbols --

see eg

ttic.uchicago.edu/~dmcallester/notes/fol.ps

-- 
Alan Smaill