Logic Seminar in Semester I AY 2016/2017

• Wednesday 10/08/2016, 17:00 hrs, Week 1, S17#04-05.
  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 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 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, S17#04-05.
  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, S17#04-05.
  Mehrdad Maleki. 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, S17#04-05.
  Ding Longyun. 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 Σ_m. A theorem of Jayne-Rogers shows that, a function f is Σ_2,2 iff X can be decomposed into countably many Δ₂ 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, AS6#05-10 (MR6).
  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, S17#04-05.
  Birzhan Moldagaliyev. Automatic complexity.
  Shallit and Wang (Automatic 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 complexity classes.
  
  
• Wednesday 14/09/2016, 17:00 hrs, Week 6, S17#04-05.
  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 Logic Colloquium 2016 in Leeds.
  
  
• Wednesday 28/09/2016, 17:00 hrs, Week 7, S17#04-05.
  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, S17#04-05.
  Reese Johnston. 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 α=ω₁, and approach a class of problems well-studied in the classical case: Π⁰₁ 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, S17#04-05.
  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 most 1. 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 eighteen spectra.
  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 Steffen Lempp's homepage.
  
  
• Wednesday 19/10/2016, 17:00 hrs, Week 10, S17#04-05.
  Victoria Gitman. 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 assuming 2^ω=ω₂. I will show how a construction of a model for a Scott set of size ω₁ generalizes to Scott sets of size ω₂ with very strong additional properties in models of the Proper Forcing Axiom (there 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, S17#04-05.
  Sanjay Jain. 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(n^m/3) and n^O(Sqrt(n)). The talk will present an improved quasipolynomial algorithm with runtime O(n^log(m)+8) which determines the winner and the winning strategy. Furthermore, if m < log(n), one can determine the winner in time O(n⁵); 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, S17#04-05.
  Wu Huishan. 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 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. 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 r.e. sets.
  
  
• 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 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.
  
  
• Wednesday 09/11/2016, 17:00 hrs, Week 13, S17#04-05.
  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, S17#04-05.
  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.