| 特定类有穷结构上的逻辑的表达能力 |
| 其他题名 | Expressive Power of Logics on Special Classes of Finite Structures
|
| 周翔
|
| 导师 | 张文辉
|
| 2009-06-03
|
| 学位授予单位 | 中科院软件所
|
| 学位 | 硕士
|
| 学位授予地点 | 中科院软件所5号楼337
|
| 关键词 | 纯算术结构，博弈，平衡图，不动点逻辑，无穷计数逻辑，可比较图，区间图，传递闭包逻辑
|
| 摘要 | 有穷模型论是受数据库理论和计算复杂性理论推动而发展起来的数理逻辑的一个研究领域。有穷模型论的主题之一就是探讨逻辑在有穷结构上的表达能力，本文围绕这一主题取得如下结果：
1. 使用Ehrenfeucht-Fraïssé博弈的方法，我们证明了在有穷纯算术结构类BFR上，Δ0≠Δ1，从而解决了Atserias博士论文中提出的一个开放问题 ；
2．提出一个新的在双射博弈中使用警察和强盗博弈的策略构造，利用这一策略构造，我们给出Dawar和Richerby的文章中的关键定理的正确证明，同时还对Atserias, Bultov和Dawar的文章中的一个关键结果作出改进 ；
3. 使用变型的Cai-Fürer-Immerman构造和Dawar和Richerby的条件，我们证明了在平衡图上，IFP+C不能刻画PTIME ，从而在“有无逻辑在完美图相关的图类上刻画PTIME”这一问题的研究上取得进展 ；
4. 利用所谓的扭结图和变异的扭结图，我们证明了可比较图，区间图以及AT-free图在FO(TC)中可定义，从而在“完美图相关的图类的逻辑可定义性”这一问题的研究上取得进展。 |
| 学科领域 | 计算机可靠性理论
|
| 语种 | 中文
|
| 内容类型 | 学位论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/169
|
| 专题 | 基础软件与系统重点实验室
|
推荐引用方式
GB/T 7714 |
周翔. 特定类有穷结构上的逻辑的表达能力[D]. 中科院软件所5号楼337. 中科院软件所,2009.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论