Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages

Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
复制标题

DOI：
10.1145/322203.322211
复制
发表时间：
1980-07
期刊：
J. ACM
影响因子：
--
通讯作者：
J. Engelfriet;G. Rozenberg
J. Engelfriet;G. Rozenberg
中科院分区：
其他
文献类型：
--
作者：
J. Engelfriet;G. Rozenberg

文献摘要

被引文献

相似文献

研究了同态映射和dgsm映射的不动点语言和相等语言。证明了这类语言的一些基本性质，并展示了如何使用它们来表示递归可枚举集合。特别是，引入了非常简单的语言，它们在递归可枚举语言类中扮演的角色与Dyck语言在上下文无关语言类中扮演的角色相同。最后，介绍了一种用于定义相等语言的新型受体。关键字和短语：相等语言，可变点语言，递归可枚举语言，确定性顺序机，图灵机，后通信问题，洗牌，AFL生成器，语言表示
Fixed point languages and equality languages of homomorphisms and dgsm mappings are consid- ered. Some basic properties of these classes of languages are proved, and it is shown how to use them to represent recursively enumerable sets. In particular, very simple languages are introduced which play the same role for the class of recursively enumerable languages that the Dyck languages play for the class of context-free languages. Finally, a new type of acceptor for defining equality languages is introduced. KEY WOADS AND PHRASES: equality language, fLxed point language, recursively enumerable language, determin- istic sequential machine, Turing machine, Post correspondence problem, shuffle, AFL generator, representation of languages