运用时间分类树的确定单时钟时间自动机学习  

Learning Deterministic One-clock Timed Automata Based on Timed Classification Tree

作　　者：米钧日 张苗苗[1] 安杰 杜博闻 MI Jun-Ri;ZHANG Miao-Miao;AN Jie;DU Bo-Wen(School of Software Engineering,Tongji University,Shanghai 201804,China;Max Planck Institute for Software Systems,D-67663 Kaiserslautern,Germany;University of Warwick,Coventry,CV47AL,UK)

机构地区：[1]同济大学软件学院,上海201804 [2]Max Planck Institute for Software Systems,D-67663 Kaiserslautern,Germany [3]University of Warwick,Coventry,CV47AL,UK

出　　处：《软件学报》2022年第8期2797-2814,共18页Journal of Software

基　　金：国家自然科学基金(61972284,62032019)。

摘　　要：时间自动机的模型学习算法旨在通过提供输入和观察输出构建软硬件系统的形式化模型.确定性单时钟时间自动机的学习是其中的一个重要研究方向,但是该算法具有一定的局限性,在状态较多时学习速度较慢,很难应用到复杂的系统中.由此,提出了一种改进的学习算法,使用逻辑时间分类树代替逻辑时间观察表作为学习算法的内部数据结构,有效地减少了成员查询次数,降低了算法的空间复杂度,并能够高效率地构建假设自动机.最后进行了相关实验,实验结果表明,提出的改进算法减少了60%左右的成员查询和5%左右的等价查询.同时在该实验中,改进算法的学习速度最高可提高45倍以上.Model learning of timed automata(TA)aims to build a formal model of software and hardware systems by external inputs and outputs.Learning of deterministic one-clock TA is one of the important research directions,but current algorithm has some limitations and is difficult to be applied to complex systems.Therefore,an improved learning algorithm is proposed,which uses logical-time classification tree instead of logical-time observation table as the internal data structure of the learning algorithm,effectively reducing the number of membership queries and the space complexity of the algorithm.In addition,it can efficiently construct hypothetical automata.Finally,relevant experiments have been carried out,and the experimental results show that the improved algorithm proposed in this study reduces the number of member queries by 60%and the number of equivalent queries by 5%.At the same time,in this experiment,the learning speed of the improved algorithm can be increased by more than 50 times at most.

关 键 词：模型学习 主动学习 确定性单时钟时间自动机 时间语言 逻辑时间分类树 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]