时间自动机与信号自动机的互模拟算法  

Algorithm of Bisimulation Between Timed Automata and Signal Automata

作　　者：朱维军[1] 刘保罗[2] 周清雷[3] 

机构地区：[1]西安电子科技大学计算机学院,陕西西安710071 [2]华南理工大学自动化科学与工程学院,广东广州510640 [3]郑州大学信息工程学院,河南郑州450052

出　　处：《华南理工大学学报（自然科学版）》2008年第5期38-42,共5页Journal of South China University of Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(69873040,60174051,10371112)

摘　　要：信号自动机为一类实时系统建立了比时间自动机更适合的模型.文中针对信号自动机因无验证算法可用而不能用于实际的实时系统模型验证的问题,把信号自动机验证归约到时间自动机验证,证明了两种自动机具有相同的识别语言能力,并具有双向模拟关系.在此基础上提出了线性的互模拟算法,把互模拟算法和已有的时间自动机验证算法结合起来,得到了信号自动机的验证算法,从而解决了对信号自动机模型的验证问题.Although signal automata are more suitable for the modeling of some classes of real-time systems than timed automata,they can not be applied to the practical real-time model verification practical verification of real-time systems due to the lack of verification algorithm.In order to solve this problem,this paper considers the verification of signal automata as that of the timed automata,and reveals the similarity of language recognition as well as the bisimulation relationship between the two types of automata.Moreover,a linear bisimulation algorithm is proposed and is further combined with the existing verification algorithm of timed automata.Thus,a verification algorithm of signal automata is obtained and the verification of signal automata is successfully solved.

关 键 词：时间自动机 信号自动机 离散步长 互模拟 模型验证 自动机理论 

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