报告题目: Is there a Fubini-Tonelli-type theorem for continuous valuations on Dcpo?
报 告 人: Jean Goubault-Larrecq, Full Professor at ENS Paris-Saclay
邀 请 人: 贾晓东
时 间: 2022年4月14日15:00--16:00 (GMT+08:00北京时间)
腾讯会议: 277-479-055 (无密码)
摘 要: Continuous valuations are a close cousin of measures which have had some success in denotational semantics. They enjoy a Fubini-Tonelli-type theorem on Top, the category of topological spaces, and this is fine: this allows us to swap the order of integration, and semantically, this means that we can draw two independent random variables in the order we wish.
However, the denotational semantics of programs operates in the smaller (full) subcategory Dcpo of dcpos, and, perhaps surprisingly, such a Fubini-Tonelli theorem is not known in that context—except on continuous dcpos, but that causes other problems.
There are solutions to this conundrum. Instead considering all continuous valuations, we may consider minimal valuations, or Heckmann’s larger class of point-continuous valuations. Rather to the point, there are Fubini-Tonelli theorems for those restricted classes of continuous valuations, which were discovered pretty recently, and they suffice to give semantics of expressive, higher-order probabilistic programming languages.
This raises the following natural question: are all those notions of valuations on dcpos distinct, or are they all the same? Every minimal valuation is point-continuous, and every point-continuous valuation is continuous. We show that the three notions are distinct, by showing that:
1. There is a continuous valuation on the Johnstone dcpo (a famous counterexample in domain theory) which is not minimal, while all of them are point-continuous.
2. There is a continuous valuation on the Smyth powerdomain of the Sorgenfrey line (a famous counterexample in topology) which is not point-continuous.
报告人简介: Jean Goubault-Larrecq is Full Professor of Computer Science at ENS Paris-Saclay, France. He is a world-renowned computer scientist for his active research in several fields of computer science: logic, computer security, semantics, domain theory, probabilistic and non-deterministic systems. He authors the book Non-Hausdorff Topology and Domain Theory, which has been serving as a standard and authoritative reference to domain theory and topology since its publication with Cambridge Press in 2013. He is the recipient of the 2011 CNRS Silver Medal in the field of computer science and its interactions. This is the highest scientific distinction in computer science in France.