[FOM] Least Fixed Point Logic

Sandro Skansi skansi.sandro at gmail.com
Mon Nov 25 21:02:38 EST 2013

First of all, thank you all for your help and suggestions! As for the
mu-calculus, I am not sure how it is related. My idea is this: obviously
the LFPL is strictly stronger than FO and strictly weaker than SO\exists
(at least if we assume P != NP). This means that it should be describable
in a fragment of the \lambda calculus (where does the mu-calculus fit in, I
am not sure), but to see which fragment, one would need to see a proof
system (at least that is the path that came to my mind). This is only a
rough idea, but this is the general direction of my research.
all the best,
On Nov 25, 2013 10:49 PM, "Robert Lubarsky" <Lubarsky.Robert at comcast.net>

> How is LFPL related to the mu-calculus? I have an (unpublished) article
> showing that the set of valid sentences of the mu-calculus is Sigma^1_2
> complete.
> Bob Lubarsky
> *From:* fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] *On Behalf
> Of *Sandro Skansi
> *Sent:* Saturday, November 23, 2013 5:34 PM
> *To:* Foundations of Mathematics
> *Subject:* [FOM] Least Fixed Point Logic
> Dear FOMers,
> Can anyone please give me some pointers on where to find more on the least
> fixed point logic (FO(LFP), LFPL)? I am particularly interested in proof
> systems for LFPL (as well as general articles on LFPL, including
> completness/incompletness proofs (is it complete?)), but I was not able to
> locate any articles dealing with this system, and the description in
> Immerman's Descriptive Complexity is quite brief and a bit informal for my
> needs.
> Thank you all in advance,
> Sandro
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20131126/c6dc4009/attachment.html>

More information about the FOM mailing list