Fudan Logic Seminar 2020

November 29

Lu Liu 刘路，Central South University

Time: 10:00 - 11:30 (to be confirmed). Location: HGW2403

可计算性理论的组合数学推论

我们介绍 Joe Miller 与 Solomon 提出的问题“是否任何有穷0-1序列的2-染色 $c$ 都存在 $c$-可计算的 variable word infinite 解”（目前尚未解决）。我们证明该问题与一个 Ramsian 型组合数学问题等价。Slides

November 6

Yinhe Peng 彭银河, Chinese Academy of Sciences

Time: 14:00 - 16:00. Location: HGW2403.

Structures of Aronszajn / coherent trees

An Aronszajn line is an uncountable linear order that contains no uncountable subset of reals or $\omega_1$, $\omega_1^*$. Equivalently, an Aronszajn tree is a partition tree of an Aronszajn line. And coherent trees are Aronszajn trees with the additional coherent property -- two sequences are the same except for a finite set. We will introduce a new forcing axiom $PFA(\mathcal{T})$. Then we analyze the structures of Aronszajn/coherent trees under the forcing axiom. Slides

October 16

Huimin Dong 董惠敏, Zhejiang University

Time: 14:00 - 16:00. Location: Tencent Meeting: 782 272 699.

The Modal Logic of Permission and Normality

This work follows van Benthem's account to study the logic of strong permission within normality. What is (strongly) permitted, as argued, is something always sufficient for being good. Yet, to avoid some deontic paradoxes, normal or defeasible permission shall be considered. We first argue that the notion of normality pinpoints a natural interplay with permission in games or in natural language. Second, we present a sound and complete dynamic logic of permission and normality. Third, I argue this logic can be viewed as a logic of rational recommendations for equilibrium selection. Slides (updated after the talk)

September 29

Yijia Chen 陈翌佳, Fudan University

Time: 14:00 - 16:00. Location: HGW2403.

Algorithmic Meta-theorems, where Logic Meets Algorithms

Many NP-hard problems can be solved efficiently on tree-like graphs. In fact, these results can be unified by a single theorem, i.e., Courcelle's Theorem. It states that every property definable in monadic second-order logic is decidable in linear time on graphs of bounded tree-width. Theorems of this form are known as algorithmic meta-theorems. The last 20 years have seen many algorithmic-meta theorems which are built on deep structural graph theory and finite model theory. In this talk I will explain those results and also our recent line of work on algorithmic meta-theorems for small circuit complexity classes. Central to our results are combinatorial characterizations of certain graph classes that are definable in first-order logic, or equivalently, by circuits of small depth.