Journal of Logic and Computation

Journal of Logic and Computation Advance Access published online on December 21, 2007
Journal of Logic and Computation, doi:10.1093/logcom/exm085

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by D'Agostino, G. Articles by Lenzi, G. Social Bookmarking          What's this?

© The Author 2007. Published by Oxford University Press on behalf of the Association of Physicians. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original papers

A Note on Bisimulation Quantifiers and Fixed Points over Transitive Frames

Giovanna D'Agostino

University of Udine, Department of Mathematics and Computer Science, Viale delle Scienze 206, 33100 Udine, Italy E-mail: dagostin{at}dimi.uniud.it

Giacomo Lenzi

University of Pisa, Department of Mathematics, Via Buonarroti 2, 56127 Pisa, Italy E-mail: lenzi{at}mail.dm.unipi.it

Received 28 November 2005.

We consider three basic questions regarding the extension of modal logic with a special kind of propositional quantifiers, known as bisimulation quantifiers, over arbitrary classes of frames: bisimulation invariance, uniform interpolation, and expressive power. In particular:

– we discuss the relation between bisimulation invariance of bisimulation quantifiers and the semantical notion of amalgamation of the class of frames;

– we consider a strong form of interpolation, uniform interpolation, and its relation with the closure under bisimulation quantifiers;

– we compare bisimulation quantifiers logic with the better known extension of modal logic with extremal fixed points.

In this article we show that the answers to these questions that are valid for the class of all frames do not generalize to arbitrary classes, but they do generalize if we restrict to classes of (finite) transitive or (finite) transitive and reflexive frames.

Keywords: Fixed points; bisimulation quantifiers; Mu-calculus; transitive frames; uniform interpolation

References

1. D'Agostino G, Hollenberg M. Logical questions concerning the µ-calculus. Journal of Symbolic Logic (2000) 65:310–332.[CrossRef][ISI]
2. Blackburn P, de Rijke M, Venema Y. Modal Logic. Vol. 53 of Cambridge Tracts in TCS (2001) Cambridge: Cambridge University Press.
3. French T. Bisimulation Quantifiers for Modal Logics. In: PhD Thesis (2006) University of Western Australia.
4. Ghilardi S, Zawadowski M. Sheaves, Games and Model Completions (a categorical approach to non classical propositional logics). In: Trends in Logic Series (2002) Dordrecht: Kluwer.
5. Ghilardi S, Zawadowski M. Undefinability of propositional quantifiers in the Modal System S4. Studia Logica (1995) 55:259–271.
6. Janin D, Walukiewicz I. On the expressive completeness of the propositional µ-calculus w.r.t. monadic second-order logic. In: In Proceedings of CONCUR '96. Vol. 1119 of LNCS (1996) 263–277.
7. Pitts A. On an interpretation of second-order quantification in first-order intuitionistic propositional logic. Journal of Symbolic Logic (1992) 57:33–52.[CrossRef][ISI]
8. Visser A. Uniform interpolation and layered bisimulation. In: Gödel '96 (Brno, 1996) Lecture Notes Logic (1996) Vol. 6. Berlin: Springer. 139–164.

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by D'Agostino, G. Articles by Lenzi, G. Social Bookmarking          What's this?