Logic Seminar in Semester II AY 2014/2015
Talks are Wednesday afternoon in Seminar Room S17#05-11
and start at 17:00 hrs. Here an overview over the topics.
Talks from the
- 14/01/2015, 17:00 hrs, Week 1, S17#05-11.
Recent Progress on Partial Learning and Related Notions.
Inductive inference investigates the learnability of classes
of r.e. sets or classes of recursive functions from presentations
of the data in a natural form. While it is known that the basic
criterion of explanatory learning does not permit to learn the
class of all recursive functions or all r.e. sets, Osherson,
Stob and Weinstein showed that a more general criterion of
partial learning permits to learn these two classes. These
findings motivated the study of combining partial learning with
additional constraints such as confidence, consistency and
conservativeness. The present talk provides additional insights
on this topic based on recent findings.
This is joint work with Gao Ziyuan and Sandra Zilles
- 21/01/2015, 17:00 hrs, Week 2, S17#05-11.
Parallel learning of automatic classes of languages.
We introduce and explore a model for parallel learning of families of
languages computable by finite automata. In this model, an algorithmic or
automatic learner takes on n different input languages and
identifies at least m of them correctly. For finite parallel learning,
for large enough families, we establish a full characterization
of learnability in terms of characteristic samples of languages. Based on
this characterization, we show that it is the difference n-m,
the number of languages which are potentially not identified, which is
crucial. Similar results are obtained also for parallel learning in the
limit. We consider also parallel finite learnability by finite automata
and obtain some partial results.
This is joint work with Efim Kinber
- 28/01/2015, 17:00 hrs, Week 3, S17#05-11.
Computable analysis and some applications in metric model
theory and measure theory.
Computable analysis is a branch of computability theory studying those
real functions and the related sets which can be computed by machines
such as digital computers. The increasing demand for reliable software
in scientific computation and engineering requires a sound foundation
not only of the analytic/numerical but also of the computational
aspects of real number computation. The central subject of this talk
is one of the approch of computable analysis called "Type Two Theory
of Effectivity (TTE)". It is based on definitions of computable real
numbers and functions by A. Turing, A. Grzegorczyk and D. Lacombe.
First, computability on finite and infinite sequences of symbols is
introduced. Then, this kind of computability can be transfered to the
other sets by means of names or codes. After, the framework of
computability is settled down, we can talk about the effectiveness of
some other spaces as metric spaces. At the end, complexity of this
approach and its two applications are discussed. One application is
for effectiveness in metric model theory and the other one is in
- 04/02/2015, 17:00 hrs, Week 4, S17#05-11.
The definability strength of combinatorial principles.
In recent years people have extensively studied the provability
strength of combinatorial principles related to Ramsey's theorem. In many
cases, the provability strength of a combinatorial principle is reflected
by its computability strength in the following sense: if solutions of
related combinatorial problems can serve as oracles to compute certain
complicated sets then the combinatorial principle is of strong provability
strength. In this talk, we introduce a different way to analyze strength
of combinatorial principles, by examing whether solutions of related
problems can help simplify certain definability problems. This approach
turns out to be useful in the reverse mathematics of combinatorics.
- 11/02/2015, 17:00 hrs, Week 5, S17#05-11.
A positive partition relation at the bounding number.
We show the consistency of the partition relation
b → (b,α)2,
for all α < ω1,
relative to the consistency of a measurable cardinal. We indicate how the
hypothesis can be significantly weakened to a smaller large cardinal.
This is joint work with Stevo Todorcevic.
- 18/02/2015, 17:00 hrs, Week 6, S17#05-11.
No talk, Chinese New Year Eve.
- 25/02/2015, 17:00 hrs, Recess Week, S17#05-11.
- 04/03/2015, 17:00 hrs, Week 7, S17#05-11.
- 11/03/2015, 17:00 hrs, Week 8, S17#05-11.
A bound for the weak covering number of the density 0 ideal.
We prove a ZFC bound for cov*(Z0) where
Z0 is the ideal of sets of asymptotic density 0.
This answers a question about diagonalizing Fσδ
ideals without adding unbounded reals.
This is joint work with Saharon Shelah.
- 18/03/2015, 17:00 hrs, Week 9, S17#05-11.
Ng Keng Meng. Degrees of categoricity.
We discuss lowness for isomorphism and degrees of
categoricity, and investigate these concepts in equivalence and
injection structures. We also discuss the intriguing question of
whether every 3-c.e. degree is a degree of categoricity.
- 25/03/2015, 17:00 hrs, Week 10, S17#05-11.
Frank Stephan. Automatic Structures -
recent results and open questions.
Automatic structures are a way to represent algebraic
structures using finite automata; all the algebraic operations
and relations have to be recognised / verified by finite automata
which read the inputs and outputs with the same speed (one symbol
per cycle). The talk gives an overview on what structures can
be represented this way and which questions are left open in
A paper is available.
- 01/04/2015 - 15/04/2015.
No talks, there is a programme at the IMS about
- 10/06/2015, 17:00 hrs, S17#04-04.
Sheung-Hung Poon. On Unfolding Trees of Small Diameters.
Graph reconfiguration problems have wide applications in contexts
including robotics, molecular conformation, animation, wire bending,
rigidity and knot theory. The motivation for reconfiguration problems of
lattice graphs arises in applications in molecular biology and robotics.
We consider the problems of straightening polygonal trees by continuous
motions such that rigid edges can rotate around vertex joints and no edge
crossings are allowed. A tree can be straightened if all its edges can be
aligned along a common straight line such that each edge points "away"
from a designated leaf node. In this talk, we start with presenting
examples of locked trees in 2D and 3D, respectively. Then we present
"minimal" locked trees in 2D, which we discovered recently. Furthermore,
we give algorithms to unfold several special classes of diameter-4 trees
in 2D. Several interesting questions remain open. For instances, is there
a polynomial-time algorithm to determine whether a diameter-4 tree in 2D
can be straightened? Can an equilateral tree of diameter 4 in 3D always