基于实时逻辑的时间约束检测方法

作     者：刘瑞成 张立臣 LIU Rui-Cheng;ZHANG Li-Chen

作者机构：广东工业大学计算机学院广州510090 

基　　金：国家自然科学基金(No.60474072 No.60174050) 广东省自然科学基金(No.04009465 No.010059) 广东省高校自然科学研究项目(No.Z03024)基金 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2005年第32卷第7期

页      码：197-205页

摘      要：本文针对具有严格时间要求的系统,阐述并分析了三种利用实时逻辑实现时间约束检测的方法。第一种方法通过检测系统规范和安全性断言的一致性来验证约束的满足性,非常适合于系统规范的设计与可满足性检测,算法的时间复杂度是O(n^2)+O(n^2)+O(2~k)。第二种方法利用实时逻辑与约束图的方法实现运行时的时间约束检测,但检测时的系统约束条件不够第三种方法简约,算法时间复杂度为O(n^3),改进之后为O(n^2)。第三种方法通过对约束图的处理,减少运行时系统检测的约束条件,从而减少运行时的时间约束条件的搜索时间,算法的时间复杂度为O(n),在实时性和检测效率明显优于前两种方法。但需要运行前优化约束规则,将会增加额外的时间和空间复杂度。

主 题 词：时间约束 检测方法 算法时间复杂度 约束条件 系统规范 空间复杂度 逻辑实现 通过检测 可满足性 系统检测 搜索时间 检测效率 约束规则 约束图 一致性 安全性 实时性 运行前 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.3969/j.issn.1002-137X.2005.07.062

馆 藏 号：203316384...