September 25: Yuri Gurevich: The logic of infons
16.30--15.30
Abstract:
Infon logic was discovered and developed as part of our work on policy and trust management. Infons are pieces of information communicated, as declarative sentences, between principals (or agents) in a distributed system.
Infons naturally form a semilattice preordered by relation "y is at least as informative as x" (in short "y covers x"), with the operation of union (or conjunction) and with known-to-all infons on one extreme and unknowable infons on the other extreme. On the semilattice live unary operations "p said" where p ranges over the principals. The resulting logic, called primal infon logic, has an interesting balance of expressivity (common policy scenarios are expessible) and efficiency (the propositional fragment is decidable in linear time).
In primal infon logic, an implication a-->b is a solution of inequalities "(a and x) covers b" and "b covers x". The existence of a least solution (presumably that is what a principal means saying that a implies b), results in a conservative extension of intuitionistic logic.
To main page

November 29: Silvio Ghilardi: TBA
16.00--17.00
Abstract:
Interpolation and combined interpolation received a lot of attention in recent times because of applications to software verification. We illustrate the use of such techniques within abstraction/refinement cycles and at the same time we show how to exploit old style algebraic characterizations in order to improve and extend available interpolation algorithms for first order theories at quantifier-free level.
To main page

March 19: Kazuyuki Tanaka: Reverse Mathematics and Nonstandard Proof Methods
17.30--18.30
Abstract:
Reverse mathematics is a research program in foundations of mathematics, initiated by H. Friedman in 1970's and most notably advanced by S. Simpson. Already in 70's, J. Steel proved the determinacy of open games by an ingenious method of psuedohierarchies in ATR. During these two decades, our group in Sendai has developed nonstandard analysis for weak subsystems of second order arithmetic. In this talk, the speaker will highlight the importance of nonstandard proof methods in reverse mathematics.
To main page

March 21: Klaus Meer: Some Aspects of Real and Complex Number Computability Theory
14.00--15.00
Abstract:
In this talk we give an introduction into computability and complexity theory over real and complex numbers along the lines of Blum, Shub, and Smale. They defined a uniform computation model over general structures about 20 years ago.
Centered around some own results we deal with polynomial system solving, general recursion theoretic questions as well as the structure of real and complex number analogues of the classical complexity class NP.
To main page

March 29: Jiamou Liu: A Polychromatic Ramsey Theory on Ordinals
16.00--17.00
Abstract:
The Ramsey degree of an ordinal is the least number n such that any colouring of the edges of the complete graph on the ordinal using finitely many colours contains an n-chromatic clique of the same order type. Ramsey's theorem states that the Ramsey degree of \omega is 1 and Erdos and Rado showed that no other countably infinite ordinal has Ramsey degree 1. We show that the Ramsey degree of every ordinal \alpha<\omega^\omega exists and provide a formula to compute it from \alpha. We further establish a version of this result for automatic structures. In this version the ordinal and the colouring are presentable by finite automata and the clique is additionally required to be regular. The corresponding automatic Ramsey degree turns out to be greater than the set theoretic Ramsey degree. Finally, we demonstrate that a version for computable structures fails.
To main page

April 4: Marek Zawadowski: Monads for Combinatorics
15.30--16.30
Abstract:
One of the ways to introduce algebraic structures over a category is by defining monads on that category. In that sense monads can be thought of as some kind of algebraic theories and give rise to the categories of Eilenberg-Moore (all) algebras and Kleisli (free) algebras. Interestingly, monads can be also used for combinatorics.

In my talk, I will discuss monads and their relation to equational theories and operads. Then I will describe two more specific classes of analytic and polynomial monads and give examples how they can be used to describe some combinatorial structures.
To main page