Search

Hairpin completion is a formal operation inspired from DNA biochemistry. It is known that the (one step) hairpin completion of a regular language is linear context-free, but not regular in general. Further, it is decidable whether the (one step) hairpin completion of a regular language is regular. However, it is an open question whether the iterated hairpin completion of a regular language is regular, even if it is a singleton. If the word is a non-crossing α-word, there are results, but for crossing words there are no results. In this paper, we give necessary and sufficient conditions that the iterated hairpin completion of a given crossing (2, 2)-α-word in is regular. [ABSTRACT FROM AUTHOR]

This paper deals with insertability and mainly extractablity of codes. A code C is called insertable (or extractable) if the free submonoid C* generated by C satisfies if z, implies (or z, implies ). 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. We cannot still characterize the structures of infinite extractable codes. Here we give some results on the class of infix extractable codes. First, we consider a necessary and sufficient condition whether a given infix code C is extractable or not by using the syntactic graph of the code. Secondly, we investigate the extractability for the families of other related bifix codes. We newly define the bifix codes, called e(m)-codes and -codes, and refer to the extractability of them. [ABSTRACT FROM AUTHOR]