101. Mathematical Colloquium
Achim Jung
University of Birmingham
ON A COMBINATORIAL PROBLEM ARISING FROM DENOTATIONAL SEMANTICS
Video and slides.Tuesday May 9, 2017, 14:00
room S5
MFF UK, Malostranske nam. 25, Praha 1
Abstract
The first premise of denotational semantics is that programs may be viewed as names for mathematical objects. Because recursion is an essential feature of programming, some care needs to be taken in defining the structures within which one may find denotations. As an example, it is well-known that ordinary recursion theory deals with partial functions from $\mathbf{N}$ to $\mathbf{N}$, rather than total ones. The second premise is that the semantics should be compositional, that is, the denotation of a program should be built from the denotations of its parts. From this one derives the requirements that denotational spaces, the ``domains'' of Dana Scott's mathematical theory of computation, should be amenable to the constructions of programming languages.
In this talk we will first review these requirements in some detail and then focus on one construction in particular, known as the probabilistic powerdomain. Although the object of intense investigation over the last 25 years, it is not known whether the probabilistic powerdomain construction fits within Scott's denotational semantics. As we will explain, the problem can be reduced to the existence of certain functions on weighted finite posets.
About the speaker
Profesor Achim Jung je prominentni osobnost soucasne teoreticke informatiky. Spolu se Samsonem Abramskym a Michaelem Mislovem patri k nejvyznamnejsim pokracovatelum v algebraickem pristupu k semantice programovacich jazyku, a v obecne teorii domen, zalozenymi D. Scottem. Achim Jung studoval na univerzitach v Amsterdamu a v Darmstadtu. Je autorem vice nez 70 praci vcetne dnes klasicke Domain theory (s S. Abramskym). Katedra teoreticke informatiky na Univerzite v Birminghamu, kam presel s nekolika dalsimi pracovniky z Imperial College v Londyne, se v uplynulych desetiletich stala vyznamnym a prestiznim centrem oboru. Profesor Jung je krome teorie domen a jejich aplikaci velmi aktivni tez v obecnych otazkach logiky topologie, kombinatoriky a algebry souvisejicich s informatikou. Venuje se rovnez problematice vyuky informatiky na vsech stupnich studia.
S Univerzitou Karlovou ma prof. Jung dlouhodobe vztahy jako spoluautor praci jejich zamestnancu i jako skolitel spolecneho doktoranda. Jeho prednaska je venovana aktualni problematice oboru leziciho na pomezi logiky, algebry a teoreticke informatiky.
