聖塔非研究所

摘要為了研究量子計算，將語言和自動機理論的結構推廣到量子情況可能會有所幫助

2022-09-02 · 已發表論文 · 更新 2026/03/19 上午04:22

摘要為了研究量子計算，將語言和自動機理論的結構推廣到量子情況可能會有所幫助。為此，我們提出了有限狀態和下推自動機的量子版本，以及常規和無競爭語法。我們發現了幾個經典定理的類似物，包括泵引理、閉包性質、有理和代數生成函數以及格雷巴赫範式。我們也表明，存在一些並非上下文無關的量子上下文無關語言，因此 QCFL 不等於 CFL。 (C) 2000 Elsevier Science …

SFI 頁面

本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。

原文連結

SFI 頁面

論文資訊

類型：已發表論文
日期：2022-09-02

摘要

為了研究量子計算，將語言和自動機理論的結構推廣到量子情況可能會有所幫助。為此，我們提出了有限狀態和下推自動機的量子版本，以及常規和無競爭語法。我們發現了幾個經典定理的類似物，包括泵引理、閉包性質、有理和代數生成函數以及格雷巴赫範式。我們也表明，存在一些並非上下文無關的量子上下文無關語言，因此 QCFL 不等於 CFL。 (C) 2000 Elsevier Science B.V. 保留所有權利。