DocumentCode :
3223595
Title :
Relating levels of the mu-calculus hierarchy and levels of the monadic hierarchy
Author :
Janin, David ; Lenzi, Giacomo
Author_Institution :
ENSERB, Bordeaux I Univ., Talence, France
fYear :
2001
fDate :
2001
Firstpage :
347
Lastpage :
356
Abstract :
As is already known from the work of D. Janin & I. Walukiewicz (1996), the mu-calculus is as expressive as the bisimulation-invariant fragment of monadic second-order logic. In this paper, we 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 J. van Benthem´s (1976) results, 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 Σ0 (i.e. first-order logic). We show that the ν-level of the mu-calculus hierarchy is as expressive as the bisimulation-invariant fragment of monadic Σ1 and that the νμ-level of the mu-calculus hierarchy is as expressive as the bisimulation-invariant fragment of monadic Σ2, and we show that no other level Σ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 Σk of the monadic hierarchy, for some k>2, is also discussed
Keywords :
bisimulation equivalence; process algebra; νμ-level; ν-level; 1st-order logic; bisimulation-invariant fragment; expressiveness; fixpoint alternation depth hierarchy; fixpoint free fragment; monadic Σ0; monadic Σ1; monadic Σ2; monadic 2nd-order logic; monadic hierarchy; monadic quantifiers alternation-depth hierarchy; mu-calculus hierarchy; polymodal logic; Calculus; Computational Intelligence Society; Electronic switching systems; Logic; Polynomials; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Logic in Computer Science, 2001. Proceedings. 16th Annual IEEE Symposium on
Conference_Location :
Boston, MA
ISSN :
1043-6871
Print_ISBN :
0-7695-1281-X
Type :
conf
DOI :
10.1109/LICS.2001.932510
Filename :
932510
Link To Document :
بازگشت