Archives of: NUS logic seminar

David Belanger: An effective perfect-set theorem

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 9 Nov 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: David Belanger

Title: An effective perfect-set theorem

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract: 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.

Liu Yong: Revisit maximal d.r.e. degrees

Invitation to the Logic Seminar at the National University of Singapore

Date: Friday, 4 November 2016, 13:00 hrs and 14:00 hrs

Room: S17#07-24, Department of Mathematics, NUS

Talk 1 – Speaker: Liu Yong.

Title: Revisit maximal d.r.e. degrees.

Abstract: 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 r.e. sets.

Talk 2 – Speaker: Peng Cheng

Title: A brief introduction to the Ershov hierarchy.

Abstract: Ershov generalized the n-r.e. hierarchy to transfinite levels
based on Kleene’s ordinals. It is a natural measure to study the sets below K.
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.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Wu Huishan: Avoiding degrees of orders on torsion-free abelian groups

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 2 November 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Wu Huishan, Nanyang Technological University

Title: Avoiding degrees of orders on torsion-free abelian groups.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

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
above question.
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.

Sanjay Jain: Deciding parity games in quasipolynomial time

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 26 October 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Sanjay Jain

Title: Deciding parity games in quasipolynomial time

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

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(n^{m/3}) and
O(n^{Sqrt(n)}). The talk will present an improved
quasipolynomial algorithm with runtime O(n^{log(m)+8}).
Furthermore, if m < log(n), one can determine the winner
in time O(n^5); thus the problem is fixed-parameter
tractable, bringing 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 at

http://www.comp.nus.edu.sg/~sanjay/paritygame.pdf

Reese Johnston: Computability of isolated paths in uncountable binary trees

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 05 October 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Reese Johnston

Title: Computability of isolated paths in uncountable binary trees.

Abstract: Alpha-recursion theory has been a target of study for some time;
a defining feature is the exotic behavior that can occur for general
ordinals alpha. In this talk, we consider the particular, and
better-behaved, case in which alpha is omega-1, and approach a class of
problems well-studied in the classical case: Pi-0-1-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.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Dilip Raghavan: Cardinal invariants above the continuum

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 28 September 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Dilip Raghavan.

Title: Cardinal invariants above the continuum.

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract: 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.

Ding Longyun: On generalisation of the Jayne-Rogers Theorem

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 31 August 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Ding Longyun

Title: On generalisation of the Jayne-Rogers Theorem

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Let X,Y be separable metrizable spaces with X analytic, and let
f be function from X to Y. We say f is Sigma-m-n if, for any
Sigma-n subset A of Y, the preimage of A under f is Sigma-m.
A theorem of Jayne-Rogers shows that, a function f is Sigma-2-2 iff
X can be decomposed into countably many Sigma-2 subsets such that
f is continuous on each of these subsets. In this talk, we will
generalize this theorem to Sigma-m-n with n leq m =3 .
We also survey the history of the study on decomposing Borel functions.

Mehrdad Maleki: Introduction to information systems

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 24 August 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Mehrdad Maleki

Title: Introduction to information systems

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
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.

Chong Chitat: 1-generic degrees bounding minimal degrees

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 17 August 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Chong Chitat

Title: 1-generic degrees bounding minimal degrees

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
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.

Frank Stephan: On block pumpable languages

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, Wednesday 10 Aug 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Frank Stephan

Title: On block pumpable languages

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract:
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
destroys decidability.

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 talk had
been presented at the conference “Computability, Randomness and
Applications” in Luminy, France.