Fixed-points for quantitative equational logics

Radu Mardare, Prakash Panangaden, Gordon Plotkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

2 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publication2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021
Place of PublicationPiscataway, NJ
PublisherIEEE
Pages1-13
Number of pages14
Volume1
ISBN (Electronic)9781665448956
ISBN (Print)9781665448956
DOIs
Publication statusPublished - 7 Jul 2021

Publication series

NameProceedings - Symposium on Logic in Computer Science
Volume2021-June
ISSN (Print)1043-6871

Keywords

  • fixed-points
  • quantitative equational logics
  • semantics
  • algebra
  • Conway theory
  • iteration theory
  • Bellman equation
  • Markov decision process

Fingerprint

Dive into the research topics of 'Fixed-points for quantitative equational logics'. Together they form a unique fingerprint.

Cite this