Bases of extractable closures of languages (Algebraic System, Logic, Language and Related Areas in Computer Science)

Abstract

Deletion and insertion are interesting and common operations which often appear in string rewriting systems. Extractable and Insertable submonoids in free monoids generated by finete alphabets allow to perform Deletion and Insertion operations, respectively. A submonoid N ⊂ A* is called extractable (or insertable) if x, uxv ∈ N implies uv ∈ N(or x, uv ∈ N implies uxv ∈ N). The code C is called extractable (or insertable) if the submonoid C* is extractable (or insertable)[7]. Both extractable and insertable codes are identical to wellknown strong codes, which is deeply related to syntactic monoids of languages. This paper deals with insertability and mainly extractablity of codes. After the preliminaries in the first section, we summarize the fundamental properties of these codes. In the second section, we show that a finite insertable code is a full uniform code, on the other hand, there are many finite extractable codes which are not full uniform codes. The infinite part of these codes is still unknown for us. So in the remaining sections we mainly investigate extractability codes in limited classes of codes. In the last section, we deal with the smallest ex血ctablesubmonoid D(L*) containing a ginven language L, where Dis the del-clusure[5]. Since the base of D(L*) is abi fix code, denoted by L→. So we give the definition of the language operation which convert a language L to L→ and investigate this operation.