Hauptseminar Mathematische Logik und Theoretische Informatik

Die Vorträge sind üblicherweise dienstags um 16 Uhr c.t. in Raum 134 des Gebäudes INF 294.
(The talks are usually on Tuesday at 4 p.m. in Room 134 of building INF 294.)


 

Vorträge im
SS 2015

14. April 2015
14:15h, Raum -101
Liang Yu, Nanjing University
Definability in the computably enumerable degrees


21. April 2015
Xizhong Zheng, Arcadia University, Pennsylvania, USA
Computable Curves


19. Mai 2015
Rupert Hölzl, Universität Heidelberg
The reverse mathematics of inductive inference


28. Mai 2015
Laurent Bienvenu, University of Paris 7
Probabilistic algorithms in computability theory


2. Juni 2015
Alexander Shen, LIRMM Montpellier
Forbidden strings, complexity arguments and tetris


7. Juli 2015
14:15h, INF 368 (IWR), SR 432
Bora I. Kumova, Izmir Insititute of Technology
The Ancient Syllogistic System and Its Properties


7. Juli 2015
Yizheng Zhu, Universität Münster
The Higher Sharp


8. Juli 2015
16:15h, INF 248 (IfI), SR 015
Bora I. Kumova, Izmir Insititute of Technology
Fuzzy-Syllogistic Systems and Their Applications for Approximate Reasoning


14. Juli 2015
Xishun Zhao, University at Guangzhou
Recent Results on Minimal Unsatisfiability


15. Juli 2015
11:15h
Victor Selivanov, Institute of Informatics Systems, Novosibirsk
On Weihrauch degrees of k-partitions of the Baire space


 



19. Mai

The reverse mathematics of inductive inference

 
(Joint work with F. Stephan and S. Jain.) It is a widespread intuition among mathematicians to think of certain theorems as stronger or weaker versions of other theorems. Of course, strictly speaking, all true theorems are logically equivalent, so at first sight it might not be obvious how one would go about formalizing this intuition. In the 1970’s, Friedman proposed a way of making this formalization and thereby inspired a new way to look at mathematics. He suggested to study classical mathematical theorems and their relations by analysing how they mutually imply each other over weak logical systems. Over such systems it then becomes meaningful to discuss whether theorems are equivalent, imply each other, and so on. This approach has been used to study and classify theorems from many areas of mathematics. In this talk, we will discuss recent work that applies the reverse mathematics method to the field of Inductive Inference. This field deals with the ability of machines or algorithms to learn objects when provided with partial information about these objects. We will look at a number of classical results in this area, in particular results by Angluin, and analyse them using the methodology of reverse mathematics. In particular we will identify three different weak logical systems and study in what situations, depending on the different learning environments, they are sufficient to permit learning, and in what situations they are not.


28. Mai

Probabilistic algorithms in computability theory

 
Since the Friedberg-Muchnik solution of Post's problem via injury argument, computability theory has seen the development of very intricate techniques, known as 'priority constructions'. These are effective constructions, therefore they can been seen as algorithms. All these algorithms are deterministic, and there are indeed very few examples of probabilistic algorithms in computability theory. Nevertheless, there is a notable family of such algorithms, discovered by Kautz (reformulated as an explicit probabilistic algorithm is due to Gacs and Shen), which we call 'fireworks arguments'. I will present the basic algorithm to prove Kautz's theorem that every 2-random real computes a 1-generic real. If time permits, I will discuss the improvement of this theorem by Barmpalias, Day and Lewis, and the further still improvement by Bienvenu and Porter.


2. Juni

Forbidden strings, complexity arguments and tetris

 
Assume that for every $k$ some $F_k$ strings of length $k$ are declared "forbidden". If the numbers $F_k$ are small enough, one can guarantee the existence of an infinite sequence that does not contain forbidden factors. Some specific sufficient condition (when $F_k$ are small enough) was suggested by Joe Miller:

$\sum_{k\ge 2}^\infty F_k c^k < 2c - 1$ for some $c\in (1/2,1)$.

This result can be then used to show the existence of everywhere complex strings ("Levin's lemma") instead of complexity arguments or Lovasz local lemma. Recently P.Ochem, D.Goncalvez and others found a nice proof of Miller's results that uses complexity argument: imagine that bits are added one my one and forbidden strings are canceled (like in tetris game). One can show that if the resulting sequence does not grow, then the string of bits used for the construction is compressible. We present a simplified version of their argument based on amortized analysis.


7. Juli

The Ancient Syllogistic System and Its Properties

 
Traditional categorical syllogism consist of 256 moods in total, 64 moods per figure. Out of them only 24 moods, 6 per figure, are well known to be the only true ones, whereas the remaining 232 are assumed to be false. A systematic analysis of the syllogisms with modern mathematics, like set-theory, algorithms and fuzzy logic, allows us not only to confirm the truth of the 24 moods, but reveals the truth of a 25th mood in the 4th figure to be true too. Furthermore, with two new concepts, the syllogistic cases and the truth ratio, we can calculate a unique truth ratio for every mood, which is in the range [0,1]. It is actually these novel concepts that help revealing the most significant properties of the syllogistic system S, like point symmetric truth of moods, partial overlapping value ranges, equivalence of moods, almost or more true/false moods. The objective of this talk is, to introduce to this modern approach of analysing syllogisms.


7. Juli

The Higher Sharp

 
Assuming Projective Determinacy, the Turing jump and hyperjump operators have their higher level analog, known as the sharp operator and the M_n^\# operator. They are transcendental objects of L or canonical inner models with Woodin cardinals. We give a characterization of these operators in terms of descriptive set theory. This alternative characterization has the advantage of directly generalizing the form the Turing jump and hyperjump operators. It is the cornerstone of generalizing results from descriptive set theory and higher recursion theory up to the projective levels.


8. Juli

Fuzzy-Syllogistic Systems and Their Applications for Approximate Reasoning

 
Using the concepts syllogistic case, truth ratio and fuzzy quantifiers, we generalise the traditional syllogistic system S with two affirmative and two negative quantifiers, of which the existential quantifiers are inclusive, to n fuzzy-syllogistic systems nS with 1<n affirmative and 1<n negative fuzzy quantifiers, of which all (n-1) existential quantifiers are exclusive. The objective of this talk is to introduce to this approach of generalisation of syllogisms and to experimentally show their application in approximate reasoning. For this purpose we discuss the design of a fuzzy-syllogistic ontology reasoner that is based on nS.


14. Juli

Recent Results on Minimal Unsatisfiability

 
This talk will give an introduction to the recent progress of the project "Structure and Classification of Minimal Unsatifiability". The speaker will introduce new classes of formulas such as prime formulas, 2-prime formulas. In addition, some connections between minimal unsatisfiability and elementary number theory will be established. Some open questions and conjectures will be proposed.


15. Juli

On Weihrauch degrees of k-partitions of the Baire space

 
In the 1990s Peter Hertling found useful "combinatorial" characterizations of initial segments of the degree structures under Weihrauch reducibilities on k-partitions (for any integer k>1) of the Baire space whose components are finite boolean combinations of open sets. In this talk we discuss extensions of these characterizations to as large initial segments of the Weihrauch degree structures as possible.