不动点逻辑中的模型构造与推演系统的完备性

来源 :中国科学院研究生院 中国科学院大学 | 被引量 : 0次 | 上传用户:liuleismx
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
与LTL、CTL以及PDL等较简单的时序与模态逻辑相比,μ-演算由于含有不动点算子,拥有非常强大的表达能力,因而付出的代价是其可满足性的判定、模型的构造以及对应公理系统的完备性都较为复杂。本文主要利用两种不同的方法,来研究μ-演算的这些问题。   首先,本文使用基于正规模型(canonicmodel)的方法尝试证明D.Kozen提出的μ-演算上的一个公理系统Kμ的完备性。这一方法的基本思想,是利用称之为极大协调集的公式集合作为状态来构造模型。其中极大协调集是指在某个公式的Fisher-Ladner闭包上极大的且无法由Kμ推导出矛盾的公式集合。这一方法的要点在于证明极大协调集作为正规模型的状态,满足其中的每一个公式。因此不可满足的公式一定不能存在于任何极大协调集中,因而可以被Kμ证明等价于假。本文指出直接使用这一方法对于μ-演算中的公式全体是不能奏效的,但是可以在其满足连续性的公式上奏效。   其次,本文使用基于tableau的方法来构造μ-演算公式的模型。Tableau方法作为一种非常强大的技术,已经广泛地用于逻辑系统的可满足性判定与模型构造之中。本文基于[33,34]的工作,提出了一种较为简单的Tableau系统。在这一系统中,可满足公式可以构造出成功的tableau,而不可满足的公式不存在成功的tableau。根据一个公式的成功tableau,可以直接地提取出这个公式的模型,并且模型的规模被tableau的规模约束。本文给出了μ-演算公式的最小模型相对于公式规模函数的一个上界与一个下界。   本文还附带了一个对于CCS的推广。这一推广与CCS最根本的区别在于其允许一对多的树状迁移。本文给出了树进程的语法定义、操作语义及其上的互模拟关系,并给出了一个可靠且完备的推理系统来证明其上的互模拟关系。
其他文献
学位
攻击者可通过渗透网络中的某台主机并以其为跳板,逐步渗透,最终实现损害网络中重要资产的目的。到达攻击目标的所有可能的攻击路径形成了攻击图。研究攻击图对网络防护具有重要
随着计算系统资源的不断增加和规模的不断扩展,虚拟化技术作为一种新型的计算模式已成为了行业内的研究热点。虚拟技术是云计算研究中的一项关键技术,与传统操作系统一样,出现的
Web系统已成为当前主流的互联网应用模式,其性能能否满足服务质量约束(ServiceLevelAgreement,SLA)的需求至关重要,否则将导致客户流失,收益受损等严重后果。基于性能模型的保障
随着信息技术的快速发展,软件应用范围越来越广。但同时软件开发也面临着越来越多新的挑战。如何面对快速变化的需求、如何用更短的时间和更少的成本开发软件和如何面对同行业
随着社会、经济和移动互联网的迅速发展,商业、家庭、公共安全等领域的无线业务对频谱资源的需求越来越迫切。频谱紧缺的问题已经成为制约无线通信发展的瓶颈。认知无线电网
当今社会机器人技术正逐步渗透到了人类生产和生活的各个领域,并已经成为21世纪最热门的研究领域之一。目标检测、定位与跟踪是机器人实现更高一级的智能行为必须具备的基本能
数据管理技术是利用计算机硬件和软件技术对数据进行有效的收集、存储、处理和应用的过程。随着数据形式的多样化以及应用需求的多元化,数据管理技术面临了新的困难和挑战。近
多智能体系统(Multi-Agent System,简称MAS)作为分布式人工智能的重要研究领域,从20世纪90年代起得到了快速的发展,并在诸多行业有着重要的应用。同时,越来越多的多智能体系统提出
大量的大规模密集型数据需要存储在多个服务器中,而应用越来越广泛的云计算环境很好地解决了大规模密集型数据在分配过程中遇到的规模性问题。随着云计算技术的发展,云环境下的