| 题名: | 基于SCC空性检测中状态空间的缩减方法 |
| 其他题名: | truly bitstate-hashing for scc-based emptiness checking algorithms
|
| 作者: | 晏荣杰
; 张文亮
; 唐稚松
|
| 关键词: | 空性检测
; 基于迁移的扩展Büchi自动机
; 可接受条件
; 检测算法
; 状态空间
; 强连通图
; 深度优先搜索
; 最坏情况
; 优势结合
; 搜索算法
; 接受条件
; 检测过程
; 布尔变量
; 自动机
; 性能
; 迁移
; 内存
; 扩展
; 标识Cellular radio systems
; Ketones
|
| 刊名: | 计算机学报
|
| 发表日期: | 2008
|
| 卷: | 31, 期:6, 页:979-988 | | 部门归属: | 中国科学院软件研究所计算机科学国家重点实验室,北京,100190;中国科学院研究生院,北京,100039;中国科学院软件研究所计算机科学国家重点实验室,北京,100190;中国科学院研究生院,北京,100039;中国科学院软件研究所计算机科学国家重点实验室,北京,100190
|
| 摘要: | 对Couvreur提出的基于强连通图的空性检测算法进行改进,使基于嵌套的深度优先搜索与基于强连通图搜索算法的优势结合起来,在对基于迁移的扩展(具有多个可接受条件)Büchi自动机进行空性检测过程中,使用一个布尔变量标识一个状态,不仅节省了内存消耗,而且一般情况下的性能明显优于已有的算法,最坏情况等同于Couvreur的算法.同时反例寻找过程等同于基于强连通图的检测算法. |
| 语种: | 中文
|
| 内容类型: | 期刊论文
|
| URI标识: | http://ir.iscas.ac.cn/handle/311060/10419
|
| Appears in Collections: | 计算机科学国家重点实验室 _期刊论文
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| 基于SCC空性检测中状态空间的缩减方法.pdf（713KB） | -- | -- | 限制开放 | -- | 联系获取全文 |
|
| Recommended Citation: | |
晏荣杰,张文亮,唐稚松. 基于SCC空性检测中状态空间的缩减方法[J]. 计算机学报,2008-01-01,31(6):979-988.
|
|
|
