MORPHIC EQUIVALENCE-RELATIONS AND UNAVOIDABLE LANGUAGES

被引：0

作者：

HARRISON, J

机构：

[1] Department of Mathematical Sciences, Binghamton University, Vestal

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1994年 / 52卷 / 3-4期

基金：

美国国家科学基金会;

关键词：

MORPHIC EQUIVALENCE; MORPHIC CONGRUENCE; REGULAR LANGUAGE; MORPH; MORPH(CONG); UNAVOIDABLE LANGUAGE;

D O I：

10.1080/00207169408804297

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given a finite alphabet A, the definitions of a morphic equivalence and congruence relation on A* are presented, and the definitions of two related classes of languages Morph and Morph(cong) are given. In [1], it is shown that every regular language is recognized by a morphic congruence of finite index and that this congruence is algorithmically constructable. The following theorem is then proven: a congruence class of a morphic congruence is unavoidable if and only if it is the identity class of a morphic congruence which yields a finite group quotient. A few consequences of this result are discussed.

引用

页码：123 / 127

页数：5