Complete Axiomatization of the Stutter-Invariant Fragment of the Linear-time mu-calculus
AmÃ©lie Gheerbrant
Abstract:
The logic \mu(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 \mu-calculus
\mu(\diamond). We provide complete axiomatizations of \mu(U) on the
class of finite words and on the class of \omega-words. We introduce
for this end another logic, which we call \mu(\diamond\Gamma), and
which is a variation of \mu(\diamond) where the Next time operator is
replaced by the family of its stutter-invariant counterparts. This
logic has exactly the same expressive power as \mu(U). Using already
known results for \mu(\diamond), we first prove completeness for
\mu(\diamond\Gamma), which finally allows us to obtain completeness
for \mu(U).