Complete Axiomatization of the Stutter-Invariant Fragment of the Linear-time mu-calculus
Amélie Gheerbrant
Abstract:
The logic µ(U) is the fixpoint extension of the "Until"-only fragment
of linear-time temporal logic. It also happens to be the
stutter-invariant fragment of linear-time µ-calculus µ(◊). We provide
complete axiomatizations of µ(U) on the class of finite words and on
the class of ω-words. We introduce for this end another logic, which
we call µ(◊_Γ), and which is a variation of µ(◊) where the Next time
operator is replaced by the family of its stutter-invariant
counterparts. This logic has exactly the same expressive power as
µ(U). Using already known results for µ(◊), we first prove
completeness for µ(◊_Γ), which finally allows us to obtain
completeness for µ(U).