基于SCC空性检测中状态空间的缩减方法

• 作者: 唐稚松 张文亮 晏荣杰
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 空性检测 基于迁移的扩展Büchi自动机 可接受条件
• 年，卷（期）: 2008,（6）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 979-988
• 页数: 10页
• 分类号: TP301
• 字数: 8305字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2008.06.011

摘要

对Couvreur提出的基于强连通图的空性检测算法进行改进,使基于嵌套的深度优先搜索与基于强连通图搜索算法的优势结合起来,在对基于迁移的扩展(具有多个可接受条件)Büchi自动机进行空性检测过程中,使用一个布尔变量标识一个状态,不仅节省了内存消耗,而且一般情况下的性能明显优于已有的算法,最坏情况等同于Couvreur的算法.同时反例寻找过程等同于基于强连通图的检测算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐稚松	中国科学院软件研究所计算机科学国家重点实验室	8	175	4.0	8.0
2	张文亮	中国科学院软件研究所计算机科学国家重点实验室	3	25	2.0	3.0
6	晏荣杰	中国科学院软件研究所计算机科学国家重点实验室	6	21	3.0	4.0