Paolo Pistone (LIP, ÉNS Lyon): Tropical Mathematics and The Lambda Calculus
2024-10-10 11:00 - 12:30 (Europe/Paris)
Paolo Pistone: We explore the interpretation of the lambda-calculus in a framework
based on tropical mathematics, and we show that it provides a unifying
framework for two well-developed quantitative approaches to program semantics:
on the one hand program metrics, based on the analysis of program sensitivity
via Lipschitz conditions, on the other hand resource analysis, based on linear
logic and higher-order program differentiation. To do that, we focus on the
semantics arising from the relational model weighted over the tropical
semiring, and we discuss its application to the study of “best case” program
behavior for languages with probabilistic and non-deterministic effects.
Finally, we show that a general foundation for this approach is provided by an
abstract correspondence between tropical algebra and Lawvere’s theory of
generalized metric spaces.
