时序逻辑博弈问题的必胜策略检测

来源 :中国科学院研究生院 中国科学院大学 | 被引量 : 0次 | 上传用户:sunxunjun2008
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着数字系统设计日益复杂化,对于系统设计和实现正确性的要求越来越高。如何在整个系统设计代码空间中定位到满足给定性质的模块,从而验证设计模块满足设计者的要求;如何在发现错误时,通过自动化方式定位到问题代码片段,这些都是在保证系统设计正确性的过程中涉及到的问题,且存在于数字系统设计流程中的各个阶段。执行验证技术的算法对所采用规范语言的类型十分敏感,由于时序逻辑具有表达能力强、直观、兼容性好等特点,能够很好地表达程序的安全性、活性和事件优先性等性质。因此,时序逻辑己广泛应用于程序的规约、验证和形式化开发,以及程序自动综合和模块化规范合成等并发程序设计的各个方面。   本文就在整个系统设计空间中定位满足给定规范的模块的问题,提出了一种关于时序逻辑的静态性质验证技术。通过研究规范的可实现性问题,将规范和系统转化成相应的状态机,并通过搜索能够精化规范的必胜策略的Mealy机,来实现在整个设计中搜索满足规范的模型。与模型检测不同的是,本问题严格区分输入、输出命题变量,并要求规范是可实现的;无需指明待验证的系统模块,特别是在错误定位时,本身就不知道要验证的是哪个系统模块,而不像模型检测需给定系统模型。   本文侧重在时序逻辑框架下研究规范的可实现性问题:由LTL公式描述的规范可得到等价的Büchi自动机,在对应自动机基础上可将该问题规约为运行环境和系统的二人博弈,定义了在博弈中系统的必胜策略。采用Mealy型有限状态机描述必胜策略,并由此延伸出Mealy状态机之间的精化关系,给出了精化检验算法以及系统设计空间的必胜策略检测的搜索框架。通过检测算法可在整个设计中搜索满足给定规范的模型。该技术可应用于定位电路设计中满足给定功能规范的信号。若结合不应该出现的规范性质,也可用于定位系统设计中的问题代码片段,实现错误定位。
其他文献
图像处理主要包括图像压缩、图像增强、图像复原、图像分割和图像分析等,其在许多应用领域受到广泛重视并取得了重大成就,如航空航天、生物医学工程、工业检测、气象、公安司法
随着GPS定位系统和无线网络技术的不断完善以及移动终端的大量普及,用户可以在需要时使用由移动终端提供的位置信息服务。例如滴滴打车之类的移动终端应用软件在发送位置需求
语音驱动人脸动画是使用语音作为数据源,合成与语音匹配的人脸表情动画技术。本方向的研究主要探究人们日常生活中最直观的面对面对话交流,因此其研究成果具有广泛的应用价值
社会网络是对现实世界中人或组织的社会关系的抽象表示。社会网络上的传播行为对人类生活的很多方面产生了重要影响。社会网络上的信息传播活动是人们获取信息与增进了解的重
在计算机图形学中,不同自然场景间的交互作用模拟成为近年来研究的热点问题之一。树木作为自然界最常见也是最重要的组成元素之一,其与周围环境之间的交互作用模拟在电影、游戏
云计算是一种面向下一代互联网的计算模式。在该模式下,应用、数据和IT资源以服务的方式通过网络提供给用户使用。经过几年的发展,云计算逐渐成熟,得到工业界和学术界的普遍认可
BSRF生物大分子光束线站为我国从事生命科学领域研究的用户开展生物大分子三维结构研究提供了重要的实验平台。为了保障线站的运行安全、提高实验效率与机时利用率,利用LabVIE
随着移动互联网的快速发展,越来越多的用户开始选择以移动应用(App)而非浏览器作为访问互联网的方式。为了顺应这种趋势,大型门户网站和服务提供商开始提供移动App用于访问各种
当今的超级计算机系统都具有显著的层次性:节点间的网络互连拓扑结构如胖树有不同交换机跨度的延迟,节点内一般是多个NUMA结构的多核处理器。计算机的体系结构的发展已明显加
信息技术深刻影响了社会个人、组织的交流方式和相互关系,对人类社会不同文化群体和社会结构产生巨大冲击,造成了社会复杂程度的迅速提高和新兴社会现象及问题的涌现。传统的