Re: deductive databases
From: Mitch Harris <harrisq_at_tcs.inf.tu-dresden.de>
Date: Fri, 13 May 2005 10:21:22 +0200
Message-ID: <3ej6c2F3e3utU1_at_news.dfncis.de>
> I think there are. It is known that on an ordered domain FO(TC) (first
> order logic plus transitive closure) can express exactly all NSPACE[log
> n] queries and FO(LFP) (first order logic plus a least fixpoint
> operator) exactly all PTIME queries. The latter class is known to be
> strictly greater than the first.
Date: Fri, 13 May 2005 10:21:22 +0200
Message-ID: <3ej6c2F3e3utU1_at_news.dfncis.de>
Jan Hidders wrote:
>
> I think there are. It is known that on an ordered domain FO(TC) (first
> order logic plus transitive closure) can express exactly all NSPACE[log
> n] queries and FO(LFP) (first order logic plus a least fixpoint
> operator) exactly all PTIME queries. The latter class is known to be
> strictly greater than the first.
-- Mitch Harris (remove q to reply)Received on Fri May 13 2005 - 10:21:22 CEST