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

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

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

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 timed automata is one of the important research directions, but current algorithm has some limitations and is difficult to be applied to complex systems. Therefore, we propose an improved learning algorithm, 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, we have carried out relevant experiments, and the experimental results show that the improved algorithm proposed in this paper 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.