Logic Seminar in Semester I AY 2016/2017
Talks are Wednesday afternoon in Seminar Room S17#04-05
and start at 17:00 hrs. Here an overview over the topics.
Talks from the
- Wednesday 10/08/2016, 17:00 hrs, Week 1,
Frank Stephan. On block pumpable languages.
Call a language L block pumpable iff there is a constant p>1 such
that for every splitting of a word in the language L into p+1 blocks,
one can find a subword consisting of an interval of the interior blocks
such that each modified word obtained by repeating or omitting this
subword is also in the language L. Such subwords are called pump.
Ehrenfeucht, Parikh and Rozenberg showed that a language is regular
iff the language and its complement are both block pumpable. The aim
of this paper is to provide some evidence that beyond this
characterisation, block pumpable languages are a notion which is
interesting in its own right. It will be shown that block pumpable
languages satisfy natural closure properties: The intersection of
two block pumpable languages is block pumpable, the union of two
block pumpable languages is block pumpable and the image of block
pumpable languages under a transduced mapping is block
pumpable. However, block pumpable languages are not closed under
complement and Kleene star. Furthermore, block pumpable languages
satisfy the condition that one can pump them several times, that
is, for each k and each sufficiently large number p(k) and
every splitting of a word into p(k) parts, one can find k disjoint
pumps in the word which can be pumped independently. The growth-rate
(number of words up to given length) of every non-regular pumpable
language is exponential. One can define block pumpable relations
and structures and show that the existential theory of such a
structure is decidable and that an alternation of quantifiers
The talk follows the paper On block pumpable
languages by Christopher Chak, Rusins Freivalds, Frank Stephan
and Henrietta Tan, which contains contains results from the FYP
of Christopher Chak and Henrietta Tan; the paper appeared in
Theoretical Computer Science 609:272-285, 2016. Furthermore, the talk
also presents results from the FYP of Jonathan Sung. The slides are available
as ps-file and
pdf-file; this talk was also presented at
the conference "Computability, Randomness and Applications 2016" in Luminy.
- Wednesday 17/08/2016, 17:00 hrs, Week 2,
Chong Chitat. 1-generic degrees bounding minimal degrees.
1-generic sets are constructed using Cohen forcing while
sets of minimal degree are obtained via perfect set forcing. These are
two incompatible techniques ensuring that the class of 1-generic
degrees is disjoint from the class of minimal degrees. The ordering
relation between members of these two classes is a problem that has
been investigated since the late 1970's. In this talk we discuss it
from the reverse mathematics point of view.
- Wednesday 24/08/2016, 17:00 hrs, Week 3,
Introduction to information systems.
Information systems are another approach to domain theory which was
introduced by Dana Scott in 1982. Information systems give
information about possible elements of domains by means of some kind
of logical systems. Although Scott shows that information systems and
algebraic domains are equivalent, so it seems information systems give
no new information about domains, however, the former approach is more
constructive. In this talk, we will introduce information systems and
show information systems are a kind of observable properties of
domains. At the end application of information systems in Computer
Science will be introduced.
- Wednesday 31/08/2016, 17:00 hrs, Week 4,
On generalization of the Jayne-Rogers theorem.
Let X,Y be separable metrizable spaces with X analytic,
and let f:X → Y. We say f is
Σm,n if, for any Σn
subset A of Y, the preimage f-1(A) is
A theorem of Jayne-Rogers shows that, a function f
is Σ2,2 iff X can be decomposed into
countably many Δ2 subsets such that
f is continuous on each of these subsets.
In this talk, we will generalize this theorem to
Σn,m with n≤ m=3. We also
survey the history of the study on decomposing Borel functions.
- Thursday 01/09/2016, 16:00 hrs, Week 4,
Georg Zetzsche. Monoids as storage mechanisms.
The investigation of models extending finite automata by some
storage mechanism is a central theme in theoretical computer
science. Choosing an appropriate storage mechanism can yield a
model that is expressive enough to capture a given behavioral
aspect while admitting desired means of analysis.
It is therefore a central concern to understand which storage
mechanisms have which properties regarding expressiveness and
(algorithmic) analysis. This talk presents a line of research
that aims for general insights in this direction. In other words:
How does the structure of the storage mechanism influence
expressiveness and analysis of the resulting model?
In order to study this question, one needs a model in which the
storage mechanism appears as a parameter. Such a model is
available in valence automata, where the storage mechanism is
given by a (typically infinite) monoid. Choosing a suitable
monoid then yields models such as Turing machines, pushdown
automata, vector addition systems, or combinations thereof.
This talk surveys a selection of results that characterize
storage mechanisms with certain desirable properties, such as
decidability of reachability, semilinearity of Parikh images, and
decidability of logics.
- Wednesday 07/09/2016, 17:00 hrs, Week 5,
Birzhan Moldagaliyev. Automatic complexity.
Shallit and Wang
complexity of strings) defined a measure of complexity for finite
strings, called automatic complexity and denoted A(x). Although the
complexity is similar to the notions of Kolmogorov and Chaitin,
it has an advantage of being more effective and it can be computed within
exponential time, even within polynomial space. Shallit and Wang gave
upper and lower bounds for A(x) and Kjos-Hanssen
(The complexity of
automatic complexity) undertook some follow-up work with respect
to the position of A and related notions in the world of
- Wednesday 14/09/2016, 17:00 hrs, Week 6,
Yang Yue. λ-definable functions over real numbers.
In the past two years, I talked about the computation models on
real numbers in NUS logic seminars. In particular, the class of master-slave
computable functions and the class of partial recursive functions over
reals are introduced; and the two classes are shown to be the same,
moreover, we have a Normal Form Theorem in the style of Kleene.
In this talk, I will give another characterization of this class of functions
using λ-calculus. This is a joint work with Duccio Pianigiani and
Andrea Sorbi from University of Siena, Italy and Jiangjie Qiu from
Renming University, China. It was based on a recent talk I gave at the
2016 in Leeds.
- Wednesday 28/09/2016, 17:00 hrs, Week 7,
Dilip Raghavan. Cardinal invariants above the continuum.
I will summarize some recent joint work with Saharon Shelah on
cardinal invariants at uncountable regular cardinals. There are some new
consistency results as well as new theorems in ZFC. The consistency
results rely on the use Boolean ultrapowers of forcing notions. I will try
to sketch the proof of some ZFC results involving the bounding and almost
disjointness at a regular uncountable cardinal.
- Wednesday 05/10/2016, 17:00 hrs, Week 8,
Computability of isolated paths in uncountable binary trees.
α-recursion theory has been a target of study for some
time; a defining feature is the exotic behavior that can occur for general
ordinals α. In this talk, we consider the particular, and
better-behaved, case in which α=ω1, and approach a
class of problems well-studied in the classical case:
Π01 classes in Cantor space. Of particular
interest, for reasons that will become apparent, are the degrees available
as isolated paths through computable binary trees that are restricted to
countable width only. In this talk, I will show that the degrees of these
paths can - unlike the classical case - be noncomputable and may in fact
have very high Turing degree.
- Wednesday 12/10/2016, 17:00 hrs, Week 9,
Steffen Lempp. Spectra of computable models of strongly
minimal disintegrated theories.
In this talk, we consider the spectra of computable (or
recursive) models of strongly minimal disintegrated theories. We examine
the class of strongly minimal disintegrated theories in relational
languages where each relation symbol defines a set of Morley rank at
We characterize the spectra of computable models of such theories
(exactly, with the exception of one single set) both under the assumption
of bounded arity on the language, and without that assumption. We also
determine the exactly seven spectra possible for binary languages and show
that for ternary languages, there are at least nine but no more than
We conjecture that for any m, there are only finitely many spectra
of computable models of strongly minimal disintegrated L-theories
T in computable (but possibly infinite) relational languages
L of arity at most m.
This is joint work with Uri Andrews and a paper is available from
- Wednesday 19/10/2016, 17:00 hrs, Week 10,
A set-theoretic approach to Scott's Problem.
Abstract: Every nonstandard model of Peano Arithmetic (PA) has a
Boolean algebra of subsets of the natural numbers associated to it,
called its standard system. The standard system of a model M
of PA, denoted SSy(M), consists of the the intersections of the
definable subsets of M with the natural numbers. Standard systems play
a very important role in the study of models of PA. For
instance, they can be used to determine when two models are isomorphic
or when there is an embedding between them. Standard systems are closed
under relative recursion and they have the tree property (if a set in a
standard system codes an infinite binary tree, then it has another set
coding an infinite branch through that tree). A nonempty Boolean algebra
of subsets of N with these two properties is called a Scott
set. Scott showed in 1962 that every countable Scott set is the
standard system of some model of PA. Scott's Problem, one
of the most famous and long-standing open problems in the field, asks
whether every Scott set is the standard system of some model of PA.
Knight and Nadel showed in 1982 that every Scott set of size
is the standard system of some model of PA, providing
a positive answer to Scott's Problem assuming the Continuum Hypothesis.
I will discuss some set-theoretic approaches to studying Scott's Problem
I will show how a construction of a model
for a Scott set of size ω1
generalizes to Scott sets of size ω2
with very strong additional properties in models of the
Proper Forcing Axiom (there 2ω=ω2).
We can associate
certain natural partial orders to a Scott set. If a Scott set is
additionally closed under the Turing jump, a filter on such a partial
order meeting enough dense sets yields an ultrafilter on the Scott set,
which allows us to construct the model with that Scott set as the
standard system as an elementary chain of ultrapowers. Given that the
associated partial order is proper we can use the Proper Forcing Axiom
to find these ultrafilters in our model.
An extended abstract of this talk can be found on
Victoria Gitman's homepage.
- Wednesday 26/10/2016, 17:00 hrs, Week 11,
Deciding parity games in quasipolynomial time.
Parity games are games on finite graphs where each
node has a value. Two players, Anke and Boris,
move alternately a marker through the graph
and plays between the two players have infinite
duration. One determines the winner of such an infinite
play by taking the largest value of a node which is visited
infinite often; if this value is even then the first player
Anke wins else the second player Boris wins.
An important question is to determine the player who
has a winning strategy in such games. One evaluates such
algorithms in terms of the number n of nodes and number
m of colours and other possible parameters. Prior work
has given algorithms with runtime O(nm/3) and
nO(Sqrt(n)). The talk will present an improved
quasipolynomial algorithm with runtime O(nlog(m)+8)
which determines the winner and the winning strategy.
Furthermore, if m < log(n), one can determine the winner
in time O(n5); thus the problem is fixed-parameter
tractable and the algorithm brings it from the prior known complexity
class XP into FPT.
This is joint work with Cristian Calude, Bakhadyr Khoussainov, Li Wei
and Frank Stephan.
The paper is available as a manuscript
and the main result is also available as part of
teaching material at end of Chapter 20.
- Wednesday 02/11/2016, 17:00 hrs, Week 12,
Avoiding degrees of orders on torsion-free abelian groups.
An abelian group admits an order iff it is torsion-free,
we consider degrees of orders on computable torsion-free abelian groups.
For a computable torsionfree abelian group G, Solomon (2003) showed
that if G has rank 1, then it has exactly two computable orders;
if G has finite rank 2 or more, then it has orders of all Turing
degrees; and if G has infinite rank, then it has orders of
all degrees greater equal 0'.
Motivated by the question whether the set of all degrees of orders
on a computable torsion-free abelian group is closed upwards,
Kach, Lange and Solomon (2013) constructed a computable
torsion-free abelian group G of infinite rank with exactly
two computable orders and a noncomputable, computably enumerable
set C such that every C-computable order on G
is computable, so this G has no orders in deg(C) > 0,
but has orders in 0, a negative answer is provided for
One proposed research topic is to study the computational complexity
of above computably enumerable set C from the standpoint of
classical computability theory, we will present a recent work on
this topic from the viewpoint of high/low hierarchy.
This is a joint work with my supervisor Wu Guohua. This abstract is
also available as pdf-file.
- Friday 04/11/2016, 13:00 hrs, Week 12,
S17#07-24 (discussion room).
Liu Yong. Revisit maximal d.r.e. degrees.
We will begin with a brief review of maximal d.r.e. construction, and
show that for any cappable r.e. set A, there is a maximal
d.r.e. set D, which computes A. We also show how to build
a maximal d.r.e. set D, avoiding upper cone of two nonrecursive
- Friday 04/11/2016, 14:00 hrs, Week 12,
S17#07-24 (discussion room).
Peng Cheng. A brief introduction to the Ershov hierarchy.
Ershov generalized the n-r.e. hierarchy to transfinite levels
based on Kleene's ordinals. It is a natural measure to study the sets
We will survey some early work by Ershov and others on the Ershov
hierarchy and present the most fundamental results. We will also provide
some questions we are thinking now.
- Wednesday 09/11/2016, 17:00 hrs, Week 13,
David Belanger. An effective perfect-set theorem.
We gauge the difficulty of finding a perfect subtree in a tree of a given
Cantor-Bendixson rank. To simplify the analysis we introduce
half-derivative, and extend the definition of rank to include values of
the form n-and-a-half; each increase of one-half in the rank
corresponds to one added jump in the perfect-subtree problem.
This is joint work with Ng Keng Meng.
- Wednesday 16/11/2016, 17:00 hrs, Reading Week,
Jonathan Verner. A Ramsey Theorem for metric spaces.
The talk is about Ramsey's Theorem considered for cardinals in general
with respect to metric spaces, for more details, please read
this pdf-file. This is joint work
with Saharon Shelah.