本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：工作論文
- 編號：工作論文 #877
- 日期：2026-03-18
摘要
我們考慮由確定性和非確定性二維有限狀態自動機識別的矩形和正方形集合。我們證明 NFA 比 DFA 更強大，即使對於單符號字母表上的圖片也是如此。在這個過程中，我們證明了 NFA 識別的圖像語言在補碼下並不是封閉的，從而解決了一個長期懸而未決的問題。我們還表明，NFA 只能從外部識別與簡單常規語言相對應的矩形集。最後，我們證明 DFA 識別的正方形集合可以像任何遞歸可枚舉集合一樣稀疏。