近日，中国科学院公布了2022年度中国科学院优秀博士学位论文评审结果，软件所2020届博士毕业生李勇的博士学位论文《Bü chi 自动机学习与取补的新算法的研究》入选，其指导教师张立军研究员荣获2022年度中国科学院优秀导师称号。 

　　李勇，2015级硕博连读生，其博士学位论文关注的正是形式化方法中重要的 Bü chi 自动机学习和取补技术，这两个技术被广泛用于系统模型的抽象提取以及系统是否满足规范的检查。论文提出了基于确定性有穷自动机族和分类树的方法来学习非确定性 Bü chi 自动机。提出的算法相较之前具有线性更优的空间复杂度。此外，在一类系统模型上，论文提出的算法相对于现有算法具有指数更优的复杂度。此外，提出的算法成功应用于 Bü chi 自动机自动机取补中。由于是对补语言的学习，学习到的补自动机比当前基于自动机结构的算法明显更小。为了能够有可能将算法应用于概率系统验证，论文提出了第一个对极限确定Büchi 自动机的学习算法。最后，论文还优化了现有的一个针对极限确定Büchi 自动机的取补算法，使其能够更有效利用极限确定这个结构信息，使实际算法效率大幅提升。 

　　中国科学院优秀博士学位论文评选始于2004年，每年评选一次。2022年，共有100篇论文入选。 

　　再次恭喜李勇同学获得优秀博士学位论文奖，同时也对其指导教师张立军研究员在指导学生方面的付出表示感谢！