[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,
Sandro
On Nov 25, 2013 10:49 PM, "Robert Lubarsky" <Lubarsky.Robert at comcast.net>
wrote:
> 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