Expressivity of quantitative modal logics : categorical foundations via codensity and approximation

Kormorida, Yuichi and Katsumata, Shin-ya and Kupke, Clemens and Rot, Jurriaan and Hasup, Ichiro; (2021) Expressivity of quantitative modal logics : categorical foundations via codensity and approximation. In: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021. Proceedings - Symposium on Logic in Computer Science . IEEE, Piscataway, NJ. ISBN 9781665448956 (https://doi.org/10.1109/LICS52264.2021.9470656)

[thumbnail of Kormorida-etal-LICS2021-Expressivity-of-quantitative-modal-logics]
Preview
Text. Filename: Kormorida_etal_LICS2021_Expressivity_of_quantitative_modal_logics.pdf
Accepted Author Manuscript

Download (1MB)| Preview

Abstract

A modal logic that is strong enough to fully characterize the behavior of a system is called expressive. Recently, with the growing diversity of systems to be reasoned about (probabilistic, cyber-physical, etc.), the focus shifted to quantitative settings which resulted in a number of expressivity results for quantitative logics and behavioral metrics. Each of these quantitative expressivity results uses a tailor-made argument; distilling the essence of these arguments is non-trivial, yet important to support the design of expressive modal logics for new quantitative settings. In this paper, we present the first categorical framework for deriving quantitative expressivity results, based on the new notion of approximating family. A key ingredient is the codensity lifting—a uniform observation-centric construction of various bisimilarity-like notions such as bisimulation metrics. We show that several recent quantitative expressivity results (e.g. by König et al. and by Fijalkow et al.) are accommodated in our framework; a new expressivity result is derived, too, for what we call bisimulation uniformity.