On Regularity and Roots of Strong Codes (Logic, Algebraic system, Language and Related Areas in Computer Science)

Abstract

Deletion and insertion are interesting and common operations which often appear in text editing. A language L ⊂ A* closed under the both operations forms a free submonoid of A*. Its base C is called a strong code, that is, L = C*. The language L is regular if and only if its base C is regular. Then, we prove in another way that the syntactic monoid of L becomes a finite group. This gives us many examples of regular strong codes. We also investigate the relation between strong codes and groups.