previous day
all days

View: session overviewtalk overview

09:10-10:50 Session 31: LC+CSL joint session
Location: G-salen
Normal Numbers, Logic and Automata

ABSTRACT. Emile Borel defined normality more than one hundred years ago to formalize a basic form of randomness for real numbers Many of his questions are still open, such as whether pi, e or square roo of 2 are normal to some base, as well as his conjecture that the irrational algebraic numbers are absolutely normal. In this talk I will highlight some theorems on normal numbers proved with tools from computability theory, automata theory and descriptive set theory, and I will point out some open questions.

Determinacy of Infinite Games: Perspectives of the Algorithmic Approach

ABSTRACT. Determinacy of infinite two-player games is a topic of descriptive set theory that has triggered intensive research in theoretical computer science since 1957 when A. Church formulated his „synthesis problem“ (regarding the construction of circuits with infinite behavior from logical specifications). In the first part of the lecture we review the fascinating development of the algorithmic theory of infinite games that was started by Church’s problem, that enriched automata theory and related fields, and that led to interesting applications in verification and program synthesis. In the second part we turn to the question how to lift this theory from the case of the Cantor space (where a play is a sequence of bits) to the case of the Baire space (where a play is a sequence of natural numbers). While this step does not involve difficulties in classical descriptive set theory, the algorithmic approach raises non-trivial questions since it requires to consider automata that work over infinite alphabets. We present recent results (joint work with B. Br\"utsch) that provide a solution of Church’s synthesis problem in this context, and we point to numerous questions that are still open.

11:20-13:00 Session 32: LC+CSL joint session
Location: G-salen
Recent directions in model theory
SPEAKER: Pierre Simon

ABSTRACT. Model theory studies combinatorial tameness properties of mathematical structures. As such it has an ever growing ambition to offer new tools and new approaches to many different areas of mathematics. In the last few decades, its range of applications has greatly expanded, at times in unexpected directions. So much so that the subject looks nothing like what it was 30 or 40 years ago.

In this talk---meant to be accessible to a wide audience---I will present a couple of themes of present research in model theory and try to give a feel for the area, what has been achieved and what might lie ahead.

Schema mappings: structural properties and limits

ABSTRACT. A schema mapping is a high-level specification of the relationship between two database schemas. For the past fifteen years, schema mappings have played an essential role in the modeling and analysis of important data inter-operability tasks,such as data exchange and data integration. Syntactically, schema mappings are expressed in some schema-mapping language, which, typically, is a fragment of first-order logic or second-order logic. In the first part of the talk, we will introduce the main schema-mapping languages, will discuss the fundamental structural properties of these languages, and will then use these structural properties to obtain characterizations of various schema-mapping languages in the spirit of abstract model theory. In the second part of the talk, we will examine schema mappings from a dynamic viewpoint by considering sequences of schema mappings and studying the convergence properties of such sequences. To this effect, we will introduce a metric space that is based on a natural notion of distance between sets of database instances and will investigate pointwise limits and uniform limits of sequences of schema mappings. Among other findings, it will turn out that the completion of this metric space can be described in terms of graph limits arising from converging sequences of homomorphism densities.