| 一种测试语言包含的算法 |
| |
| 引用本文： | 刘建元,杜慧敏.一种测试语言包含的算法[J].小型微型计算机系统,2001,22(10):1241-1244. |
| |
| 作者姓名： | 刘建元 杜慧敏 |
| |
| 作者单位： | 西安邮电学院计算机系 |
| |
| 基金项目： | 受国家自然科学基金(69473017)资?种 |
| |
| 摘 要： | 在积自动机基础上，利用互模拟关系引出商自动机，用以解决积自动机的状态组合爆炸问题。进而提出一个自然的测试语言包含的算法，这种算法的空间复杂度与规范自动机的状态目呈指数关系即O（2^k)，其中K是规范自动机的状态数目。
|
| 关 键 词： | 语言包含 互模拟 有限自动机 计算机 |
| 文章编号： | 1000-1220(2001)10-1241-04 |
A ALGORITHM FOR TESTING LANGUAGE CONTAINMENT |
| |
| LIU,Jian-yuan,DU,Hui,min.A ALGORITHM FOR TESTING LANGUAGE CONTAINMENT[J].Mini-micro Systems,2001,22(10):1241-1244. |
| |
| Authors: | LIU Jian-yuan DU Hui min |
| |
| Abstract: | In order to solve the state combination explosion, a method based on the bisimulation relation for testing the containment of implementation automaton and specification automaton is presented. A quotient automaton with less states can be induced by the bisimulation relation. We prove that the language accepted by the original automata equals to the language accepted by the quotient automaton. An algorithm for test containment of automata based on the relation is discussed. If implementation automaton is deterministic, the time complexity is polynomial with specification automaton size and space complexity is exponential with it. |
| |
| Keywords: | Automata Containment of automata Bisimulation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
