101 KAM Mathematical Colloquium

Achim Jung

University of Birmingham

ON A COMBINATORIAL PROBLEM ARISING FROM DENOTATIONAL SEMANTICS


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