Re: Expressibility question
Date: Fri, 14 Jun 2002 16:46:46 -0700
Message-ID: <140620021646464884%johnfl_at_cs.uoregon.edu>
[[ This message was both posted and mailed: see
the "To," "Cc," and "Newsgroups" headers for details. ]]
In article <3d0a68d6_at_news.uia.ac.be>, Jan.Hidders <hidders_at_hcoss.uia.ac.be> wrote:
> No, unfortunately I don't, :-), and I'm sitting at home right now so I can't
> look it up. A quick look on-line taught me however that there is a proof by
> Phokion Kolaitis that showed that on unordered finite structures (aka.h
> relational databases :-)) FO(PFP) has greater expressive power then FO(IFP)
> by showing that the first can define game trees (an often used technique in
> finite model theory, Abiteboul et al. explains some of it, Ebbinghaus et al.
> more, see Ehrenfaucht Fraisse games) and the second cannot. Since FO(TC)
> expresses a subset of FO(IFP) this also separates FO(TC) from FO(PFP). The
> reference is:
>
> KOLAITIS, P. 1991. The expressive power of stratified logic programs. Inf.
> Comput. 90, 50 -- 66.
>
> I wasn't able to find an on-line version, unfortunately. Whether there is a
> similar proof that shows that FO(IFP) is strictly stronger than FO(TC) I
> really don't know.
This'll do nicely for now -- certainly enough for recreational curiousity (although there was a slight overlap with professional need: I needed to be sure about an offhand comment in a paper we're writing). I also found some interesting-looking material on descriptive complexity on a web page by Neil Immerman
http://www.cs.umass.edu/~immerman/descriptive_complexity.html
Among other things, he's got a nice diagram which places the different extensions to first order logic within their respective complexity classes. Proof by nice picture isn't usually a good enough technique for peer review, but it'll suffice to satisfy my curiousity for now. It also says you're right.
I'll track down that Kolaitis lead, too. And with that, I'd probably better throw a TooFarAfield exception and get back to the paper I'm writing. It looks like you folks have enough interesting material in this area to keep me from ever graduating :-) I'm only just lately beginning to realize that following interesting leads is a non-terminating process.
Thanks again,
John
John Fiskio-Lasseter CIS Dept., University of Oregon * Phd. Student, Graduate Teaching Fellow, and GTFF Steward * Deschutes 234 x6-1385 johnfl_at_cs.uoregon.edu ----------------------------------------------------------------------Wit, an' it be thy will, put me into good fooling. Those wits who think they have thee do very oft prove fools, while I, who am sure I lack thee, may yet pass for a wise man. For what says Quinapalus: "Better a witty fool than a foolish wit".
_Twelfth Night_
----------------------------------------------------------------------
Received on Sat Jun 15 2002 - 01:46:46 CEST