二维二方向有限自动机的识别能力研究

摘要：

研究了3种有限自动机,即二维二方向的确定型、非确定型以及Las Vegas有限自动机.证明存在语言能被二维二方向的Las Vegas有限自动机识别,但不能被相应的确定型有限自动机识别；存在语言能被二维二方向的非确定型有限自动机识别,但不能被相应的Las Vegas有限自动机识别.研究结果表明,二维二方向的Las Vegas有限自动机所识别的语言真包含确定型有限自动机所识别的语言；二维二方向的非确定型有限自动机所识别的语言真包含LasVegas有限自动机所识别的语言.

关键词：二维二方向、确定型、非确定型、Las Vegas型

所属期刊栏目：32

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目10971013

在线出版日期：2013-03-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1129-1133