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

来源：软件学报杂志2022年第8期北京时间：

作者：米钧日，张苗苗，安杰，杜博闻

单位：米钧日，同济大学 软件学院, 上海 20180411,张苗苗，同济大学 软件学院, 上海 20180402,安杰，Max Planck Institute for Software Systems, D-67663 Kaiserslautern, Germany03,杜博闻，University of Warwick, Coventry, CV4 7AL, UK04

摘要：时间自动机的模型学习算法旨在通过提供输入和观察输出构建软硬件系统的形式化模型.确定性单时钟时间自动机的学习是其中的一个重要研究方向,但是该算法具有一定的局限性,在状态较多时学习速度较慢,很难应用到复杂的系统中.由此,提出了一种改进的学习算法,使用逻辑时间分类树代替逻辑时间观察表作为学习算法的内部数据结构,有效地减少了成员查询次数,降低了算法的空间复杂度,并能够高效率地构建假设自动机.最后进行了相关实验,实验结果表明,提出的改进算法减少了60%左右的成员查询和5%左右的等价查询.同时在该实验中,改进算法的学习速度最高可提高45倍以上.

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

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