PURELY HOMOMORPHIC CHARACTERIZATION OF RECURSIVELY ENUMERABLE SETS

被引：43

作者：

CULIK, K

机构：

[1] Department of Computer Science, University of Waterloo, Waterloo

来源：

JOURNAL OF THE ACM | 1979年 / 26卷 / 02期

关键词：

equality sets; formal languages; homomorpMc characterization; recurswely enumerable sets;

D O I：

10.1145/322123.322136

中图分类号：

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

学科分类号：

0812 ;

摘要：

Charactenzattons of recursvely enumerable sets as mappings of equality and mtmmal sets are given An equality (minimal) set is the set of all (minmaal) solutions of an instance of the Post correspondence problem where the solutions are viewed as stnngs The mar result is that every recurstvely enumerable set can be expressed (effecUvely) as a homomorphlc image of a minimal set. From the algebraic pomt of view this seems to be the simplest characterization of recurslvely enumerable languages A corollary of the mare result ts the solution of an open problem formulated by A Salomaa A purely homomorphlc characterization of regular sets is denved How such a characterization can be obtained for various ttrne and space complexRy classes for languages ts outhned. © 1979, ACM. All rights reserved.

引用

页码：345 / 350

页数：6