中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 学位论文
学科主题: 计算机科学技术基础学科::计算机可靠性理论
题名:
特定类有穷结构上的逻辑的表达能力
作者: 周翔
答辩日期: 2009-06-03
导师: 张文辉
授予单位: 中科院软件所
授予地点: 中科院软件所5号楼337
学位: 硕士
关键词: 纯算术结构,博弈,平衡图,不动点逻辑,无穷计数逻辑,可比较图,区间图,传递闭包逻辑
其他题名: Expressive Power of Logics on Special Classes of Finite Structures
摘要: 有穷模型论是受数据库理论和计算复杂性理论推动而发展起来的数理逻辑的一个研究领域。有穷模型论的主题之一就是探讨逻辑在有穷结构上的表达能力,本文围绕这一主题取得如下结果: 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
Appears in Collections:计算机科学国家重点实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
周翔的博士论文final.pdf(805KB)----限制开放 联系获取全文

Recommended Citation:
周翔. 特定类有穷结构上的逻辑的表达能力[D]. 中科院软件所5号楼337. 中科院软件所. 2009-06-03.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[周翔]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[周翔]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace