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)|
References found in this work BETA
No references found.
Citations of this work BETA
Modality, Bisimulation and Interpolation in Infinitary Logic.Johan van Benthem - 1999 - Annals of Pure and Applied Logic 96 (1-3):29-41.
Similar books and articles
Minimal Predicates. Fixed-Points, and Definability.Johan Van Benthem - 2005 - Journal of Symbolic Logic 70 (3):696 - 712.
Hybrid Logics: Characterization, Interpolation and Complexity.Carlos Areces, Patrick Blackburn & Maarten Marx - 2001 - Journal of Symbolic Logic 66 (3):977-1010.
Expressivity of Second Order Propositional Modal Logic.ten Cate Balder - 2006 - Journal of Philosophical Logic 35 (2):209-223.
Safe Formulas in the General Theory of Stable Models (Preliminary Report).Joohyung Lee & Vladimir Lifschitz - unknown
Safe Formulas in the General Theory of Stable Models (Preliminary Report).Vladimir Lifschitz - unknown
Added to index2009-01-28
Total downloads23 ( #221,085 of 2,177,988 )
Recent downloads (6 months)1 ( #317,698 of 2,177,988 )
How can I increase my downloads?