101 KAM Mathematical Colloquium
Achim Jung
University of Birmingham
ON A COMBINATORIAL PROBLEM ARISING FROM DENOTATIONAL SEMANTICS
Video and slides.
utery 9. kvetna 2017 ve 14:00, poslucharna S5, druhe patro
KAM MFF UK
Malostranske nam. 25
118 00 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.
O přednášejícím
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.
Jaroslav Nesetril a Ales Pultr