An equivalence relation on suffix codes defined by generalized regular languages

Abstract

Let X be a finite alphabet and X ^∗ the free monoid generated by X. S(X) denotes the free monoid of all suffix codes over X under concatenation. For SεS(X) and L⊆X ^∗, the right congruence ∼_s,l over X^∗ is defined by . A language L⊆X ^∗ is S-regular iff ∼_S,L is of finite index. For any .

For define . The relation ≈is an equivalence relation over S(X). In this note, we give a characterization of ≈. Some properties of ≈ are given. In particular, we show that ≈ is a right congruence of infinite index over S(X).

Keywords:

• Free monoid
• suffix code
• maximal suffix code
• regular language
• s-regular language
• equivalence relation
• right (left) congruence

C.R. Categories:

• F.4.3
• E.4