近日，中國科學院公布了2022年度中國科學院優秀博士學位論文評審結果，軟件所2020屆博士畢業生李勇的博士學位論文《Bü chi 自動機學習與取補的新算法的研究》入選，其指導教師張立軍研究員榮獲2022年度中國科學院優秀導師稱號。 

　　李勇，2015級碩博連讀生，其博士學位論文關注的正是形式化方法中重要的 Bü chi 自動機學習和取補技術，這兩個技術被廣泛用于系統模型的抽象提取以及系統是否滿足規范的檢查。論文提出了基于確定性有窮自動機族和分類樹的方法來學習非確定性 Bü chi 自動機。提出的算法相較之前具有線性更優的空間復雜度。此外，在一類系統模型上，論文提出的算法相對于現有算法具有指數更優的復雜度。此外，提出的算法成功應用于 Bü chi 自動機自動機取補中。由于是對補語言的學習，學習到的補自動機比當前基于自動機結構的算法明顯更小。為了能夠有可能將算法應用于概率系統驗證，論文提出了第一個對極限確定Büchi 自動機的學習算法。最后，論文還優化了現有的一個針對極限確定Büchi 自動機的取補算法，使其能夠更有效利用極限確定這個結構信息，使實際算法效率大幅提升。 

　　中國科學院優秀博士學位論文評選始于2004年，每年評選一次。2022年，共有100篇論文入選。 

　　再次恭喜李勇同學獲得優秀博士學位論文獎，同時也對其指導教師張立軍研究員在指導學生方面的付出表示感謝！