量子Büchi自動機的等價刻畫

《量子Büchi自動機的等價刻畫》是依託陝西師範大學，由韓召偉擔任項目負責人的數學天元基金項目。

基本介紹

• 中文名：量子Büchi自動機的等價刻畫
• 項目類別：數學天元基金項目
• 項目負責人：韓召偉
• 依託單位：陝西師範大學

項目摘要

量子計算是當代計算機科學領域重要的研究方向，而量子計算模型是其關鍵科學問題之一。本項目旨在採用語義分析方法，將Büchi自動機理論以及ω-正則語言相關研究結果推廣到量子邏輯框架下。首先，通過細化和改造廣義子集構造技術，給出量子邏輯意義下Büchi自動機的相關代數描述，建立對應的ω-Kleene定理，給出Büchi自動機的等價代數刻畫。其次，通過引入單體二階量子邏輯的概念，利用“層次化”處理技巧，給出Büchi自動機的等價單體二階量子邏輯描述。再次，詳細研究了量子ω-正則語言對於ω-正則運算的封閉性，並通過引入ω-星自由和ω-非周期量子ω-語言，建立ω-正則語言的一階邏輯描述，得到了量子邏輯意義下的分類定理，對量子ω-正則語言給出了一種分類方法。基於此，最終完善基於量子邏輯的計算理論，為基於Büchi自動機的量子模型檢測做理論基礎準備。

結題摘要

量子計算是當代計算機科學領域重要的研究方向，而量子計算模型是其關鍵科學問題之一。本項目利用語義分析方法，針對量子邏輯框架下Büchi自動機和ω -正則語言理論進行了深入研究。首先，通過量子狀態構造技術，建立量子邏輯意義下Büchi自動機識別語言的相關代數刻畫、層次刻畫和Büchi刻畫，即給出Büchi自動機的等價代數刻畫。其次，通過引入單體二階量子邏輯的概念，利用“層次化”處理技巧，給出Büchi自動機識別語言的等價單體二階量子邏輯刻畫，推廣了量子邏輯意義下的Büchi基本定理。再次，通過引入量子有限步可識別語言和量子狀態構造方法,建立量子Müller自動機識別語言的代數刻畫和層次刻畫，同時給出Müller自動機識別語言的等價單體二階量子邏輯刻畫，深化了量子邏輯意義下的Büchi基本定理。最後，分別詳細研究了Büchi自動機和Müller自動機識別的量子ω -正則語言對於ω -正則運算的封閉性。另外，通過引入ω -星自由和ω -非周期量子ω -語言，研究了量子ω -正則語言的一階邏輯描述，得到了量子邏輯意義下的分類定理，對量子ω -正則語言給出了一種分類方法。通過上述工作，我們得到了一些結論，目前已在國內權威學術期刊上發表論文3篇，還有部分工作即將投稿於國內國內及國際學術期刊。