Complete axiomatization of the stutter-invariant fragment of the linear time µ-calculus

Authors
Publication date 2010
Host editors
  • L. Beklemishev
  • V. Goranko
  • V. Shehtman
Book title Advances in Modal Logic
Book subtitle AiML 8
ISBN
  • 9781848900134
Event Advances in Modal Logic 2010 (AiML 2010), Moscow, Russia
Pages (from-to) 140-155
Publisher London: College Publications
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
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).
Document type Conference contribution
Language English
Published at http://www.aiml.net/volumes/volume8/Gheerbrant.pdf
Permalink to this page
Back