Morphic equivalence relations and unavoidable languages

Abstract

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.

Keywords:

• Morphic equivalence
• morphic congruence
• regular language
• Morph
• Morph^cong unavoidable language

C.R Categories:

• F.4.3
• D.3.1
• J.3