| 摘要: |
| 时间自动机的主动学习是一个重要的研究话题. 多时钟时间自动机的主动学习是其中一个重要的研究方向. 然而, 已有的多时钟时间自动机的学习算法的学习速度较慢. 基于时间观察树提出一种改进的主动学习算法. 定义一种名为时间观察树的数据结构, 用于存储学习过程中获取的信息. 基于时间观察树的特殊结构, 可以利用二分搜索技术来分析反例. 通过使用该反例分析技术, 可以减少成员查询的数量和重置信息查询的数量, 从而提高算法的效率. 实验结果证明了该方法的有效性. |
| 关键词: 主动学习 多时钟时间自动机 时间观察树 反例分析 二分搜索 |
| DOI：10.13328/j.cnki.jos.007607 |
| 分类号:TP311 |
| 基金项目:国家重点研发计划(2022ZD0120303); 国家自然科学基金(62472316); 上海市2023年度“科技创新行动计划”区块链关键技术攻关专项(23511100800) |
|
| Observation-tree-driven Active Learning of Deterministic Timed Automata |
|
TENG Yu, ZHANG Miao-Miao
|
|
School of Computer Science and Technology, Tongji University, Shanghai 200092, China
|
| Abstract: |
| Active learning of timed automata is an important research topic. Active learning of multi-clock timed automata is one of the important research directions. However, the existing learning algorithms for multi-clock timed automata have relatively slow learning speed. This study proposes an improved active learning algorithm based on a timed observation tree. A data structure called the timed observation tree is defined to store the information obtained during the learning process. Based on the special structure of the timed observation tree, binary search techniques can be used to analyze counterexamples. By using this counterexample analysis technique, the number of membership queries and reset information queries can be reduced, thereby improving the efficiency of the proposed algorithm. Experimental results demonstrate the effectiveness of the method. |
| Key words: active learning multi-clock timed automata timed observation tree counterexample analysis binary search |
