David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Studia Logica 60 (2):311-330 (1998)
It has been known since the seventies that the formulas of modal logic are invariant for bisimulations between possible worlds models — while conversely, all bisimulation-invariant first-order formulas are modally definable. In this paper, we extend this semantic style of analysis from modal formulas to dynamic program operations. We show that the usual regular operations are safe for bisimulation, in the sense that the transition relations of their values respect any given bisimulation for their arguments. Our main result is a complete syntactic characterization of all first-order definable program operations that are safe for bisimulation. This is a semantic functional completeness result for programming, which may be contrasted with the more usual analysis in terms of computational power. The 'Safety Theorem' can be modulated in several ways. We conclude with a list of variants, extensions, and further developments.
|Keywords||Philosophy Logic Mathematical Logic and Foundations Computational Linguistics|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Johan van Benthem (1999). Modality, Bisimulation and Interpolation in Infinitary Logic. Annals of Pure and Applied Logic 96 (1-3):29-41.
Similar books and articles
Wim Ruitenburg (1999). Basic Logic, K4, and Persistence. Studia Logica 63 (3):343-352.
Johan Van Benthem (2005). Minimal Predicates. Fixed-Points, and Definability. Journal of Symbolic Logic 70 (3):696 - 712.
Carlos Areces, Patrick Blackburn & Maarten Marx (2001). Hybrid Logics: Characterization, Interpolation and Complexity. Journal of Symbolic Logic 66 (3):977-1010.
Balder ten Cate (2006). Expressivity of Second Order Propositional Modal Logic. Journal of Philosophical Logic 35 (2):209-223.
Balder ten Cate (2006). Expressivity of Second Order Propositional Modal Logic. Journal of Philosophical Logic 35 (2):209 - 223.
Jan van Eijck (2012). Action Emulation. Synthese 185 (1):131-151.
Joohyung Lee & Vladimir Lifschitz, Safe Formulas in the General Theory of Stable Models (Preliminary Report).
Johan Van Benthem (1998). Program Constructions That Are Safe for Bisimulation. Studia Logica 60 (2):311 - 330.
Added to index2009-01-28
Total downloads11 ( #219,154 of 1,726,249 )
Recent downloads (6 months)8 ( #84,767 of 1,726,249 )
How can I increase my downloads?