一种测试语言包含的算法  

A ALGORITHM FOR TESTING LANGUAGE CONTAINMENT

作　　者：刘建元[1] 杜慧敏[1] 

机构地区：[1]西安邮电学院计算机系,陕西西安710061

出　　处：《小型微型计算机系统》2001年第10期1241-1244,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金 (69473 0 17)资助

摘　　要：在积自动机基础上 ,利用互模拟关系引出了商自动机 ,用以解决积自动机的状态组合爆炸问题 .进而提出一个自然的测试语言包含的算法 ,这种算法的空间复杂度与规范自动机的状态数目呈指数关系即 O(2 k ) ,其中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.

关 键 词：语言包含 互模拟 有限自动机 计算机 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构]