本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #855
- 日期：2026-03-18
摘要
我們解決了幾個長期懸而未決的問題，這些問題涉及各種類型的有限狀態自動機識別「圖片語言」（即二維符號數組集）的能力。我們證明，四路交替有限狀態自動機（AFA）識別的語言與所謂的平鋪可識別語言無法相比。具體來說，我們證明非循環有向圖集合是 AFA 可識別的，但不可平鋪識別，而非無環有向圖集合是可平鋪識別的，但不可 AFA 識別的。更一般地，AFA可識別語言的補集是平鋪可識別的，因此AFA可識別語言在補集下不是封閉的。我們還表明，四向 NFA 識別的語言集在補碼下不是封閉的，並且 NFA 比 DFA 更強大，即使對於符號上的語言也是如此。