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

Clc Number:

TP311

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 26,2021
  • Revised:October 14,2021
  • Adopted:
  • Online: January 28,2022
  • Published: August 06,2022
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063