[FOM] Least Fixed Point Logic

Tero TULENHEIMO tero.tulenheimo at univ-lille3.fr
Thu Nov 28 01:45:40 EST 2013

By looking at the definitions of mu-calculus and least fixpoint logic, it
is absolutely trivial that semantically, mu-calculus is a fragment of
least fixpoint logic (in the same way in which basic modal logic is a
fragment of first-order logic, i.e., the former can be translated into the

Best regards,
  Tero Tulenheimo

Le Mar 26 novembre 2013 03:02, Sandro Skansi a écrit :
> 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.

More information about the FOM mailing list