As already known [14], the mu-calculus [17] is as expressive as the bisimulation invariant fragment of monadic second order Logic (MSO). In this paper, ive relate the expressiveness of levels of the fixpoint alternation depth hierarchy of the mu-calculus (the mu-calculus hierarchy) with the expressiveness of the bisimulation invariant fragment of levels of the monadic quantifiers alternation-depth hierarchy (the monadic hierarchy). From van Benthem's result [3], we know already that the fixpoint free fragment of the mu-calculus (i.e. polymodal Logic) is as expressive as the bisimulation invariant fragment of monadic Sigma (0) (i.e. first order logic). We show here that the v-level (resp. the nu mu -level) of the mu-calculus hierarchy is as expressive cis the bisimulation invariant fragment of monadic Sigma (1) (resp. monadic Sigma (2)) and we show that no other level Sigma (k) for k > 2 of the monadic hierarchy can be related similarly with any other level of the mu-calculus hierarchy. The possible inclusion of all the mu-calculus in some level Sigma (k) of the monadic hierarchy, for some k > 2, is also discussed.

Relating Levels of the Mu--Calculus Hierarchy and Levels of the Monadic Hierarchy

LENZI, Giacomo;
2001-01-01

Abstract

As already known [14], the mu-calculus [17] is as expressive as the bisimulation invariant fragment of monadic second order Logic (MSO). In this paper, ive relate the expressiveness of levels of the fixpoint alternation depth hierarchy of the mu-calculus (the mu-calculus hierarchy) with the expressiveness of the bisimulation invariant fragment of levels of the monadic quantifiers alternation-depth hierarchy (the monadic hierarchy). From van Benthem's result [3], we know already that the fixpoint free fragment of the mu-calculus (i.e. polymodal Logic) is as expressive as the bisimulation invariant fragment of monadic Sigma (0) (i.e. first order logic). We show here that the v-level (resp. the nu mu -level) of the mu-calculus hierarchy is as expressive cis the bisimulation invariant fragment of monadic Sigma (1) (resp. monadic Sigma (2)) and we show that no other level Sigma (k) for k > 2 of the monadic hierarchy can be related similarly with any other level of the mu-calculus hierarchy. The possible inclusion of all the mu-calculus in some level Sigma (k) of the monadic hierarchy, for some k > 2, is also discussed.
2001
0-7695-1281-X
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/1954324
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 9
social impact