Fixed-points for quantitative equational logics

Mardare, Radu and Panangaden, Prakash and Plotkin, Gordon; (2021) Fixed-points for quantitative equational logics. In: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021. Proceedings - Symposium on Logic in Computer Science, 1 . IEEE, Piscataway, NJ, pp. 1-13. ISBN 9781665448956

[thumbnail of Mardare-etal-LICS-2021-Fixed-points-for-quantitative-equational-logics]
Text. Filename: Mardare_etal_LICS_2021_Fixed_points_for_quantitative_equational_logics.pdf
Accepted Author Manuscript

Download (191kB)| Preview


    We develop a fixed-point extension of quantitative equational logic and give semantics in one-bounded complete quantitative algebras. Unlike previous related work about fixed-points in metric spaces, we are working with the notion of approximate equality rather than exact equality. The result is a novel theory of fixed points which can not only provide solutions to the traditional fixed-point equations but we can also define the rate of convergence to the fixed point. We show that such a theory is the quantitative analogue of a Conway theory and also of an iteration theory; and it reflects the metric coinduction principle. We study the Bellman equation for a Markov decision process as an illustrative example.