Přednášky se konají v 17:00 v posluchárně M2 na Janáčkově nám. 2a v Brně, pokud není explicitně uvedeno jinak.

24. října

Klaus Keimel, (Technische Universität, Darmstadt)
Functional analytic methods in semantics

Abstrakt:

Domain theory has been introduced by D.S. Scott for the purpose of a denotational semantics for programming languages and lambda-calculi. The mathematical theory of domains has order theoretical, topological and category theoretical aspects and is well developed. Recently, also functional analytic tools and methods from convex analysis play a role in constructing domain models combining probabilistic choice and nondeterminism.

Nondeterminism is modelled by powerdomains, i.e., spaces of certain subsets. Probabilistic choice is of a different flavour and has been modelled by the probabilistic powerdomain, a domain theoretical variant of the classical space of probability measures. For dealing with situations where probabilistic choice and nondeterminism both occur, the two types powerdomain constructions have to be combined.

For this purpose, functional analytic tools have to be adapted to the domain theoretical setting. Although the topologies are far from being Hausdorff the necessary Hahn-Banach type separation theorems and a Banach- Alaoglu type theorem due to G. Plotkin are available.

In this talk we will introduce and motivate the domain theoretical setting for which topologies which are far from satisfying the Hausdorff separation property are characteristic. We will show in which way functional analytic methods can be adapted to this setting.

14. listopadu

Alexander Okhotin, (University of Turku)
Equations over sets of natural numbers

Abstrakt:

Systems of equations of the form Xi = 'i(X1, . . . ,Xn), in which variables assume values of sets of nonnegative integers, are considered. The right-hand sides may contain singleton constants, Boolean set-theoretic operations and the operation of pairwise sum of elements of two sets:

Y # Z = {y + z|y 2 Y, z 2 Z}.

If the only allowed Boolean operation is union, these equations constitute a degenerate case of context-free grammars (a model of syntax in computer science) defined over one-letter alphabet, and their least solutions are known to be ultimately periodic. In this talk, the expressive power of equations over sets of numbers with all Boolean operations will be investigated. First, an arithmetization of a class of cellular automata will be used to represent a significant class of sets of integers. Using some known constructions from theoretical computer science, this construction will be extended to a new arithmetization of computable functions, and it will be proved that a set of numbers S is definable by a unique solution of such a system if and only if there exists an algorithm for testing the membership of a given number in S.