Logic Seminar in Semester I AY 2011/2012

1. 17/08/2011, 17:00 hrs, Week 2.
   Liang Yu. Cofinal maximal chains in the Turing degrees.
   Assuming ZFC , we prove that CH holds if and only if there exists a cofinal maximal chain of order type ω₁ in the Turing degrees. However it is consistent that ZF+(not CH)+``there exists a cofinal chain in the Turing degrees of order type ω₁''.
   This is a joint work with Wei Wang and Liuzhen Wu.
   
   
2. 24/08/2011, 17:00 hrs, Week 3.
   Frank Stephan. Closed left-r.e. sets
   A set is called r-closed left-r.e. iff every set r-reducible to it is also a left-r.e. set. It is shown that some but not all left-r.e. cohesive sets are many-one closed left-r.e. sets. Ascending reductions are many-one reductions via an ascending function; left-r.e. cohesive sets are also ascening closed left-r.e. sets. Furthermore, it is shown that there is a weakly 1-generic many-one closed left-r.e. set.
   
   
3. 31/08/2011, 17:00 hrs, Week 4.
   Keng Meng Ng. Strongly jump traceable and beyond.
   The relationship between Martin-Loef randomness and computational power has been studied extensively in recent years. We look at notions of anti-randomness, and ask what relationship these notions have with computational complexity. We will talk about various aspects of K-triviality, strong jump traceability and some partial relativizations of strong jump traceability.
   
   
4. 07/09/2011, 17:00 hrs, Week 5.
   Eric Martin. Disjunctive logic programs, answer sets and the cut rule.
   In a 1990 paper, Minker has proposed a semantics for negation-free disjunctive logic programs that offers a natural generalization of the fixed point semantics for definite logic programs. We show that this semantics can be further generalized for disjunctive logic programs with classical negation, in a constructive modal-theoretic framework where rules are built from assertions and hypotheses, namely, formulas of the form ☐ φ and ◊ ☐ φ where φ is a literal, respectively, yielding a "base semantics" for general disjunctive logic programs. Model-theoretically, this base semantics is expressed in terms of a classical notion of logical consequence. It has a complete proof procedure based on a general form of the cut rule. Usually, alternative semantics of logic programs amount to a particular interpretation of nonclassical negation as "failure to derive." The counterpart in our framework is to complement the original program with a set of hypotheses required to satisfy specific conditions, and apply the base semantics to the resulting set. We demonstrate the approach for the answer-set semantics. The proposed framework is purely classical in mainly three ways. First, it uses classical negation as unique form of negation. Second, it advocates the computation of logical consequences rather than of particular models. Third, it makes no reference to a notion of preferred or minimal interpretation.
   
   
5. 28/09/2011, 17:00 hrs, Week 7.
   Peng Yinhe. Characterization and transformation of Countryman lines and R-embeddable coherent trees in ZFC.
   Countryman line is an interesting linear order and coherent tree is an interesting tree order. There is a transformation between them under MA_ω1 (S. Todorcevic). The aim of this talk is to find whether this is true in ZFC by adding R-embeddable property and the relations between them.
   
   
6. 12/10/2011, 17:00 hrs, Week 9.
   Frank Stephan. Robust learning of automatic classes of languages.
   This talk adapts and investigates the paradigm of robust learning, originally defined in the inductive inference literature for classes of recursive functions, to learning languages from positive data. Robustness is a very desirable property, as it captures a form of invariance of learnability under admissible transformations on the object of study. The classes of languages of interest are automatic - a formal concept that captures the notion of being recognisable by a finite automaton. A class of first-order definable operators - called translators - is introduced as natural transformations that preserve automaticity of languages in a given class and the inclusion relations between languages in the class. For many learning criteria, we characterise the classes of languages all of whose translations are learnable under that criterion. The learning criteria have been chosen from the literature on both explanatory learning from positive data and query learning, and include consistent and conservative learning, strong-monotonic learning, strong-monotonic consistent learning, finite learning, learning from subset queries, learning from superset queries, and learning from membership queries.
   This is joint work with Sanjay Jain and Eric Martin; the talk was presented at the Conference on Algorithmic Learning Theory 2011 in Helsinki in October 2011.
   
   
7. 19/10/2011, 17:00 hrs, Week 10.
   Shao Dongxu. On the Ramsey property in the context of determinacy.
   In this talk, I will give a partial proof to the statement that AD implies every set of reals is Ramsey.
   
   
8. Week 11.
   Deepavali.
   
   
9. 02/11/2011, 17:00hrs, Week 12.
   Li Wei. Σ₁ Induction and d-r.e. degrees.
   The existence of proper d-r.e. degrees was shown by Cooper using finite injury method. A classical result of Reverse Recursion Theory claims Σ₁ induction is enough for a finite injury construction, thus for the existence of proper d-r.e. degrees. Here we consider the case when Sigma₁ induction fails. We will show, in that case, there is a proper d-r.e. degree; furthermore, such a degree could be the degree of a bounded d-r.e. set. Nevertheless, without Σ₁ induction, no proper d-r.e. degree could be below 0'. That is, the existence of proper d-r.e. degrees below 0' is equivalent to Σ₁ induction. Moreover, we will show that all degrees below 0' are r.e degrees, for some models not satisfying Σ₁induction but having enough saturation. Thus, it is necessary to have Σ₁ induction for the existence of non-r.e. degrees below 0'.
   
   
10. 09/11/2011, 17:00hrs, Week 13.
    Seah Cheng En Samuel. Automatic functions and linear time bounds.
    The major result presented in the talk is that a function from strings to strings is automatic iff it is computed in linear time by a one-tape Turing machine which places the start of the output into the same cell where the original input started. Here the one-tape Turing machine can be either deterministic or non-deterministic.