UNSOLVABILITY OF EQUIVALENCE PROBLEM FOR LAMBDA-FREE NONDETERMINISTIC GENERALIZED MACHINES

被引：85

作者：

GRIFFITHS, TV

机构：

[1] Air force Cambridge Research Laboratories, Bedford, Massachusetts

来源：

JOURNAL OF THE ACM | 1968年 / 15卷 / 03期

关键词：

D O I：

10.1145/321466.321473

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

It is shown that the equivalence problem for A-free nondeterministic generalized machines is unsolvable, and it is observed that this result implies the unsolvability of the equality problem for finite languages. © 1968, ACM. All rights reserved.

引用

页码：409 / +

页数：1