Institutional Repository
| 特定类有穷结构上的逻辑的表达能力 | |
| Alternative Title | Expressive Power of Logics on Special Classes of Finite Structures |
| 周翔 | |
| Supervisor | 张文辉 |
| 2009-06-03 | |
| Degree Grantor | 中科院软件所 |
| Degree Level | 硕士 |
| Place of Degree Grantor | 中科院软件所5号楼337 |
| Keyword | 纯算术结构，博弈，平衡图，不动点逻辑，无穷计数逻辑，可比较图，区间图，传递闭包逻辑 |
| English Abstract | 有穷模型论是受数据库理论和计算复杂性理论推动而发展起来的数理逻辑的一个研究领域。有穷模型论的主题之一就是探讨逻辑在有穷结构上的表达能力，本文围绕这一主题取得如下结果： 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)中可定义，从而在“完美图相关的图类的逻辑可定义性”这一问题的研究上取得进展。 |
| Subject | 计算机可靠性理论 |
| Language | 中文 |
| Content Type | 学位论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/169 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | 周翔. 特定类有穷结构上的逻辑的表达能力[D]. 中科院软件所5号楼337. 中科院软件所,2009. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| 周翔的博士论文final.pdf（805KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment