论文部分内容阅读
有穷模型论是受数据库理论和计算复杂性理论推动而发展起来的数理逻辑的一个研究领域。有穷模型论的主题之一就是研究逻辑在有穷结构上的表达能力，围绕这一主题本文取得如下结果：
(i)使用博弈的方法证明了在有穷纯算术结构类BFR上，△0≠△1，从而解决了Atserias博士论文中提出的一个开放问题；
(ii)提出一个新的在双射博弈中使用警察和强盗博弈的策略构造，并利用这一策略构造给出Dawar和Richerby的文章中的关键定理的正确证明，同时还对Atserias，Bultov和Dawar的文章中的一个关键结果作出改进；
(iii)使用变型的Cai-Furer-Immerman构造和来自于Dawar和Richerby的条件，证明了在平衡图上，IFP+C不能刻画PTIME，从而加深对“有无逻辑在完美图相关的图类上刻画PTIME”这一问题的认识；
(iv)利用所谓的扭结图和变异的扭结图，证明了可比较图，区间图以及AT-free图在FO(TC)中可定义，从而在“完美图相关的图类的逻辑可定义性”这一问题的研究上取得进展。