Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-01-24T00:30:47.946Z Has data issue: false hasContentIssue false
  • English
  • Français

Coalgebraic logic over general measurable spaces – a survey

Published online by Cambridge University Press:  25 March 2011

ERNST-ERICH DOBERKAT  and
CHRISTOPH SCHUBERT
ERNST-ERICH DOBERKAT
Affiliation:
Chair for Software Technology, Technische Universität Dortmund Email: [email protected]; [email protected]
CHRISTOPH SCHUBERT
Affiliation:
Chair for Software Technology, Technische Universität Dortmund Email: [email protected]; [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this survey we discuss the generalisation of stochastic Kripke models for general modal logics through predicate liftings for functors over general measurable spaces. We derive results on expressivity and show that selection arguments allow us to incorporate the discussion of bisimilarity, provided the underlying spaces are assumed to be standard Borel.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 21 , Special Issue 2: Coalgebraic Logic , April 2011 , pp. 175 - 234
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baier, C., Haverkort, B., Hermanns, H. and Katoen, J.-P. (2003) Model-checking algorithms for continuous time Markov chains. IEEE Trans. Softw. Eng. 29 (6)524–541.CrossRefGoogle Scholar
Billingsley, P. (1968) Convergence of Probability Measures, first edition, John Wiley and Sons.Google Scholar
Billingsley, P. (1995) Probability and Measure, John Wiley and Sons.Google Scholar
Blackburn, P., de Rijke, M. and Venema, Y. (2001) Modal Logic, Cambridge Tracts in Theoretical Computer Science 53, Cambridge University Press.CrossRefGoogle Scholar
Cîrstea, C. (2004) On logics for coalgebraic simulation. Electronic Notes in Theoretical Computer Science 106 63–90.CrossRefGoogle Scholar
Cîrstea, C. (2006) Modularity in coalgebra. Electronic Notes in Theoretical Computer Science 164 3–26.CrossRefGoogle Scholar
Cîrstea, C. and Pattinson, D. (2004) Modular construction of modal logics. In: Proceedings CONCUR 2004. Springer-Verlag Lecture Notes in Computer Science 2170 258–275.CrossRefGoogle Scholar
Clarke, E. M., Grumberg, O. and Peled, D. A. (1999) Model Checking, The MIT Press.Google Scholar
Danos, V., Desharnais, J., Laviolette, F. and Panangaden, P. (2006) Bisimulation and cocongruence for probabilistic systems. Information and Computation 204 503–523.CrossRefGoogle Scholar
Dedecker, J., Prieur, C. and deFitte, P. Fitte, P. (2004) Parametrized Kantorovich–Rubinštein theorem and application to the coupling of random variables. arXiv:math/0410052v2 [math PR].Google Scholar
Desharnais, J., Edalat, A. and Panangaden, P. (2002) Bisimulation of labelled Markov-processes. Information and Computation 179 (2)163–193.CrossRefGoogle Scholar
Desharnais, J., Laviolette, F. and Turgeon, A. (2009) A demonic approach to information in probabilistic systems. In: Bravetti, M. and Zavattaro, G. (eds.) CONCUR 2009 – Concurrency Theory. Springer-Verlag Lecture Notes in Computer Science 5710 289–304.CrossRefGoogle Scholar
Doberkat, E.-E. (2005) Semi-pullbacks for stochastic relations over analytic spaces. Mathematical Structures in Computer Science 15 647–670.CrossRefGoogle Scholar
Doberkat, E.-E. (2006) Stochastic relations: congruences, bisimulations and the Hennessy–Milner theorem. SIAM J. Computing 35 (3)590–626.CrossRefGoogle Scholar
Doberkat, E.-E. (2007a) The Hennessy–Milner equivalence for continuous-times stochastic logic with mu-operator. J. Appl. Logic 35 519–544.CrossRefGoogle Scholar
Doberkat, E.-E. (2007b) Stochastic Relations. Foundations for Markov Transition Systems, Chapman and Hall.CrossRefGoogle Scholar
Doberkat, E.-E. (2008) Stochastic coalgebraic logic: Bisimilarity and behavioral equivalence. Ann. Pure Appl. Logic 155 46–68.CrossRefGoogle Scholar
Doberkat, E.-E. (2009a) Behavioral and logical equivalence of stochastic Kripke models in general measurable spaces. In: Chen, J. and Cooper, S. (eds.) TAMC 2009. Springer-Verlag Lecture Notes in Computer Science 5532 192–200.CrossRefGoogle Scholar
Doberkat, E.-E. (2009b) Stochastic Coalgebraic Logic, EATCS Monographs in Theoretical Computer Science, Springer-Verlag.CrossRefGoogle Scholar
Doberkat, E.-E. (2010a) Lattice properties of congruences for stochastic relations. Ann. Pure Appl. Logic (in press).Google Scholar
Doberkat, E.-E. (2010b) Quotients for the Kleisli category over the Giry monad. Technical Report 182, Chair for Software Technology, Technische Universität Dortmund.Google Scholar
Doberkat, E.-E. and Schubert, C. (2009) Coalgebraic logic for stochastic right coalgebras. Annals of Pure and Applied logic 159 268–284.CrossRefGoogle Scholar
Dunford, N. and Schwartz, J. T. (1957) Linear Operators, Volume I, Interscience.Google Scholar
Edalat, A. (1999) Semi-pullbacks and bisimulation in categories of Markov processes. Mathematical Structures in Computer Science 9 (5)523–543.CrossRefGoogle Scholar
Edgar, G. A. (1998) Integral, Probability and Fractal Measures, Springer-Verlag.CrossRefGoogle Scholar
Elstrodt, J. (1999) Maß- und Integrationstheorie, second edition, Springer-Verlag.CrossRefGoogle Scholar
Goldblatt, R. (2010) Deduction systems for coalgebras over measurable spaces. Journal of Logic and Computation 20 (5)1069–1100.CrossRefGoogle Scholar
Halmos, P. R. (1950) Measure Theory, Van Nostrand Reinhold.CrossRefGoogle Scholar
Jacobs, B. and Sokolova, A. (2010) Exemplaric expressivity of modal logics. Journal of Logic and Computation 20 (5)1041–1068.CrossRefGoogle Scholar
Jones, C. (1989) Probabilistic Non-determinism, Ph.D. thesis, University of Edinburgh.Google Scholar
Kechris, A. S. (1994) Classical Descriptive Set Theory, Graduate Texts in Mathematics, Springer-Verlag.Google Scholar
Klin, B. (2007) Coalgebraic modal logic beyond sets. Electronic Notes in Theoretical Computer Science 173 177–201.CrossRefGoogle Scholar
Kuratowski, K. (1966) Topology, Volume I, PWN – Polish Scientific Publishers and Academic Press.Google Scholar
Larsen, K. G. and Skou, A. (1991) Bisimulation through probabilistic testing. Information and Computation 94 1–28.CrossRefGoogle Scholar
Mac Lane, S. (1997) Categories for the Working Mathematician, Graduate Texts in Mathematics, Springer-Verlag.Google Scholar
Moss, L. and Viglizzo, I. (2006) Final coalgebras for functors on measurable spaces. Information and Computation 204 610–636.CrossRefGoogle Scholar
Moss, L. M. (1999) Coalgebraic logic. Ann. Pure Appl. Logic 96 277–317.CrossRefGoogle Scholar
Parthasarathy, K. R. (1967) Probability Measures on Metric Spaces, Academic Press.CrossRefGoogle Scholar
Pattinson, D. (2004) Expressive logics for coalgebras via terminal sequence induction. Notre Dame J. Formal Logic 45 (1)19–33.CrossRefGoogle Scholar
Rudin, W. (1974) Real and Complex Analysis, second edition, Tata McGraw-Hill.Google Scholar
Rutten, J. J. M. M. (2000) Universal coalgebra: a theory of systems. Theoretical Computer Science 249 (1)3–80. (Special issue on modern algebra and its applications.)CrossRefGoogle Scholar
Schröder, L. (2008) Expressivity of coalgebraic modal logic: the limits and beyond. Theoretical Computer Science 390 230–247.CrossRefGoogle Scholar
Schröder, L. and Pattinson, D. (2007) Modular algorithms for heterogeneous modal logics. In: Arge, L., Cachin, C., Jurdzinski, T. and Tarlecki, A. (eds.) Proceedings ICALP. Springer-Verlag Lecture Notes in Computer Science 4596 459–471.CrossRefGoogle Scholar
Schubert, C. (2007) Coalgebraic logic over analytic spaces. Technical Report 170, Chair for Software Technology, Technische Universität Dortmund.Google Scholar
Schubert, C. (2009a) Coalgebraic logic over measurable spaces: behavioral and logical equivalence. In: Chen, Y., Doberkat, E.-E. and Jung, A. (eds.) Proceedings of the Fifth International Symposium on Domain Theory (ISDT 2009). Electronic Notes in Theoretical Computer Science 257 71–85.CrossRefGoogle Scholar
Schubert, C. (2009b) Coalgebraic modal logic over measurable spaces: behavioral versus logical equivalence. Technical Report 179, Chair for Software Technology, Technische Universität Dortmund.CrossRefGoogle Scholar
Schubert, C. (2009c) Final coalgebras for measure-polynomial functors. In Chen, J. and Cooper, B. (eds.) TAMC 2009. Springer-Verlag Lecture Notes in Computer Science 5532 325–334.CrossRefGoogle Scholar
Srivastava, S. M. (1998) A Course on Borel Sets, Graduate Texts in Mathematics, Springer-Verlag.CrossRefGoogle Scholar
Viglizzo, I. D. (2005a) Coalgebras over measurable spaces, Ph.D. thesis, Indiana University.Google Scholar
Viglizzo, I. D. (2005b) Final sequences and final coalgebras for measurable spaces. In: Fiadeiro, J., Harman, N., Roggenbach, M., and Rutten, J. (eds.) Algebra and Coalgebra in Computer Science – Proceedings First International Conference, CALCO 2005. Springer-Verlag Lecture Notes in Computer Science 3629 395–407.CrossRefGoogle Scholar
Yamasaki, Y. (1985) Measures on infinite dimensional spaces, World Scientific.CrossRefGoogle Scholar
Zhou, C. (2009) A complete deductive system for probability logic. J. Logic Comp. 19 (6)1427–1454.CrossRefGoogle Scholar
Zhou, C. (2010) Probability logics for finitely additive beliefs. J. Logic, Language and Information 19 (3)247–282.CrossRefGoogle Scholar