Morphic refinements of nonregular languages

Abstract

In [Harr, ′94], it was shown that every regular language and its complement is refined by a congruence of finite index which is preserved by every endomorphism of a given finitely-generated free monoid. Moreover, this refinement can be algorithmically constructed. In section one of this paper, it will be shown that there exists a linear language and an endomorphism of the free monoid on two generators in which there does not exist any finite morphic refinement of the language and its complement.

The aforementioned example motivates a weakening of the above hypotheses in which only the language itself has an algorithmically-constructable refinement which is preserved by a given endomorphism. In section two of this paper, it shall be shown that this class of languages (which will be denoted EndPres) is closed under intersection and disjoint union and not closed under complementation in many instances. Also, some decidable properties of this class of languages shall be given.

Finally, in section three of this paper, some nonregular members of this class of languages will be examined. It shall be shown that standard extensions of subword-counting congruences of finite index induce morphic equivalence relations of infinite index and so finite unions of these congruence classes yield nonregular languages in the class discussed in section two of this work. Finally, we'll show that some well-known nonregular languages (some of which are context-sensitive) are in this class of languages.

Keywords:

• Endomorphism-preserving refinement
• subword-counting equivalence
• Morph
• EndPres

C.R.Categories:

• D3.1
• F4.3