101. matematické kolokvium KAM - Achim Jung (University of Birmingham): On a combinatorial problem arising from denotational semantics

Abstrakt

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 N to 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.

CV

Profesor Achim Jung je prominentní osobnost současné teoretické informatiky. Spolu se Samsonem Abramským a Michaelem Mislovem patří k nejvýznamnějším pokračovatelům v algebraickém přístupu k sémantice programovacích jazyků, a v obecné teorii domén, založenými D. Scottem. Achim Jung studoval na univerzitách v Amsterdamu a v Darmstadtu. Je autorem více než 70 prací včetně dnes klasické Domain theory (s S. Abramskym). Katedra teoretické informatiky na Univerzitě v Birminghamu, kam přešel s několika dalšími pracovníky z Imperial College v Londýně, se v uplynulých desetiletích stala významným a prestižním centrem oboru. Profesor Jung je kromě teorie domén a jejich aplikací velmi aktivní též v obecných otázkách logiky topologie, kombinatoriky a algebry souvisejících s informatikou. Věnuje se rovněž problematice výuky informatiky na všech stupních studia.

S Univerzitou Karlovou má prof. Jung dlouhodobé vztahy jako spoluautor prací jejich zaměstnanců i jako školitel společného doktoranda. Jeho přednáška je věnována aktuální problematice oboru ležícího na pomezí logiky, algebry a teoretické informatiky.

Jaroslav Nešetřil a Aleš Pultr