基于语言等价关系化简Büchi自动机的算法

• 作者: 张普含 易锦 郭涛 黄永刚
• 来源期刊: 清华大学学报（自然科学版）
• 学科: 工学
• 关键词: 模型检测 自动机 状态空间爆炸
• 年，卷（期）: 2009,（z2）
• 页码范围: 2181-2185
• 页数: 5页
• 分类号: TP311
• 语种: 中文

摘要

为了缓解模型检测中状态空问爆炸问题, 尽可能多的化倚Büchi自动机的状态和迁移.该文定义了基于Büchi自动机语言等价关系的语言等价类概念, 并基于该等价类概念提出了化简自动机状态和迁移的有效算法.由于该算法充分考虑了等价类中状态之间的可达关系, 并通过模拟等价关系来计算语言等价关系, 使得自动机的商和语言等价类相结合, 因而可在多项式时间内尽可能多的化简Büchi自动机的状态空间.通过典型例子分析以及算法的正确性证明显示了该算法比现有算法可获得更好的化简效果.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	郭涛		16	158	7.0	12.0
2	黄永刚		3	56	2.0	3.0
3	易锦		5	5	1.0	2.0
4	张普含		5	1	1.0	1.0