线性时间逻辑基于表列、自动机、博弈的模型检测理论研究

来源 :南开大学 | 被引量 : 0次 | 上传用户:chenfengling
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
模型检测理论是逻辑学和计算机科学的一个交叉领域,作为模态逻辑的一个重要分支时间逻辑,它的繁荣发展就出现在这一领域。数理逻辑和计算机理论科学中的最高奖图灵奖曾于1996年和2007年两度颁给对模型检测有重要贡献的三位科学家。20世纪90年代后期,模型检测的研究基础才稳固下来,它对逻辑学界的影响以及逻辑学界对它的重视也开始日益明显。  在逻辑、数学和计算机科学的交界处,有着长久的受重视的传统,模型检测思想和这个传统有着相同的起源,著名的Büchi定理、 Church的序列电路乃至图灵机都可以为此佐证。然而,从模态/时间逻辑的角度出发来研究模型检测理论在纯逻辑学界却是一个新课题,笔者第一次站在逻辑学的视角下,勾勒出模型检测和应用于计算机科学的时间逻辑的发展图景。模型检测是关于时间逻辑可满足性判定问题的研究,其研究的两类实体一是关于刻画程序计算性质的逻辑公式,二是用来刻画程序的模型,模型检测的任务就是要校准这两种不同形式的信息——公式和模型——是否相一致。  线性时间逻辑LTL是应用于计算机科学的一种最基础的模态逻辑,而LTL的模型检测理论也是这个领域中最基础的部分。笔者将模型检测理论的研究内容划分为两部分:一是可满足性问题研究,二是模型检测问题研究,前者研究对于某个时间逻辑公式是否存在可满足的模型,后者研究对于给定模型某个时间逻辑公式是否可满足。表列、自动机、博弈通常被认为是用于解决模型检测问题的三种元逻辑技术,笔者分别详细阐述了线性时间逻辑LTL基于表列、自动机、博弈的模型检测理论,并对这三种判定方法进行了比较研究。在考察了三种元逻辑的基础上,对一种新兴的扩展时间逻辑——动态线性时间逻辑DLTL——进行了全面的更为完整的定义,并使用目前流行的博弈方法给出DLTL模型检测问题的一个解决方案。概括说来,笔者的主要工作和创新点包括以下四个方面。  第一,在对模型检测的任务和步骤进行了简单概括之后,从新的思路出发,以模型检测中的核心问题“判定性问题”为线索,系统地回顾了模型检测的萌芽、初步形式、正式提出和广泛应用、各种扩展时间逻辑的提出四个阶段。  第二,在对字逻辑、线性时间逻辑LTL、程序与计算、并发程序等进行概括介绍的基础上,深入探讨了三种元逻辑方法以及它们应用于LTL的模型检测理论,即LTL基于表列的模型检测理论、LTL基于自动机的模型检测理论、LTL基于博弈的模型检测理论,以可满足性问题研究和模型检测问题研究为主要内容,对相应的判定过程分别证明了其可靠性和完全性。  第三,从新的角度将LTL和DLTL同时定义在标号转换系统的路径和字模型的字上,以此建立起LTL、自动机、DLTL之间的内在联系。之后在前人工作的基础上,对DLTL的语义进行了全新的更为完整的定义,尝试使用博弈的判定方法探讨DLTL的模型检测理论。  第四,从哲学和逻辑学的立场出发,对应用于模型检测的表列、自动机和博弈进行了比较研究和哲学分析,在较为宽广的背景下探讨这项研究的理论意义,尝试着展望未来的发展前景并分析了可能进一步探讨的方向。  时间逻辑在模型检测中完成了从理论到应用的一次转变,也将模型检测引入到模态逻辑中为模态逻辑的发展加大了马力。目前,国内逻辑学界对时间逻辑和模型检测的研究还非常薄弱,而国内计算机科学界对模型检测的研究已经兴起。笔者相信,这一项研究会为模型检测在国内逻辑学研究中作出一定的贡献,在不断地从理论到应用交替发展中,也会为国内计算机科学中模型检测的后继研究提供适当养料。
其他文献
当前,物理主义成为了心灵哲学中的主流观点。尽管如此,作为本体论的物理主义依然面临着严峻挑战。这种挑战主要体现在两个方面:一方面是物理主义自身的问题,被称之为"亨佩尔
冯友兰先生是作为现代学科的“中国哲学”的奠基者之一,是20世纪中国最重要的哲学家之一,其理论创获与哲学活动堪称“二十世纪中国哲学的一个缩影”。西方哲学的强烈冲击与刺激
民本思想所论国儒家传统所所化,它根源于殷周之际,所当时还没有民本思想这重均本,但所周本所总本殷本改朝换代所论验教训所基础之上,看到除本民所伟大作用,关心民众所需重除
中国近代是一个大转折、大变革的时代,鸦片战争后,“救亡图存”成了鲜明的时代主题。在外国人“送来的”和中国人“拿来的”种种资产阶级的“西学”中,达尔文的进化论影响最大。
由汉字书写而成的中国传统书法艺术,是中华民族的文化瑰宝,充分体现了汉民族的审美思维及其精神特征,是最具有民族特色的传统艺术之一。书法作为中国传统文化最独特的一种艺术形
"明末清初"不仅是中国近世社会的大变革时代,更是近世中国思想文化界的现代转型期,各种思潮如百花齐放,绚烂多彩。傅山就生活在这样一个时代,他的思想也因染上鲜明的时代特色