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

作者简介:

米钧日(1995-),男,硕士生,主要研究领域为组合验证,时间自动机理论,模型学习;
安杰(1990-),男,博士,主要研究领域为形式化方法,机器学习,模型学习,系统识别;
张苗苗(1971-),女,博士,研究员,博士生导师,主要研究领域为智能系统学习,人工智能的形式化验证,模型学习和验证;
杜博闻(1991-),男,博士生,主要研究领域为人工智能,智能系统,移动计算与软件工程.

通讯作者:

张苗苗,E-mail:miaomiao@tongji.edu.cn

中图分类号:

TP311

基金项目:

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


Learning Deterministic One-clock Timed Automata Based on Timed Classification Tree
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

米钧日,张苗苗,安杰,杜博闻.运用时间分类树的确定单时钟时间自动机学习.软件学报,2022,33(8):2797-2814

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-09-26
  • 最后修改日期:2021-10-14
  • 录用日期:
  • 在线发布日期: 2022-01-28
  • 出版日期: 2022-08-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号