观察树驱动的确定性时间自动机主动学习

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

作者：滕宇，张苗苗

单位：滕宇，同济大学 计算机科学与技术学院, 上海 20009211,张苗苗，同济大学 计算机科学与技术学院, 上海 20009202

摘要：时间自动机的主动学习是一个重要的研究话题. 多时钟时间自动机的主动学习是其中一个重要的研究方向. 然而, 已有的多时钟时间自动机的学习算法的学习速度较慢. 基于时间观察树提出一种改进的主动学习算法. 定义一种名为时间观察树的数据结构, 用于存储学习过程中获取的信息. 基于时间观察树的特殊结构, 可以利用二分搜索技术来分析反例. 通过使用该反例分析技术, 可以减少成员查询的数量和重置信息查询的数量, 从而提高算法的效率. 实验结果证明了该方法的有效性.

关键词：主动学习|多时钟时间自动机|时间观察树|反例分析|二分搜索

基金资助：国家重点研发计划(2022ZD0120303); 国家自然科学基金(62472316); 上海市2023年度“科技创新行动计划”区块链关键技术攻关专项(23511100800)