As I have already announced in previous post, the 12th International Conference on Automata and Formal Languages (AFL) will take place at the end of May 2008 in Balatonfured, Hungary. I was glad to see that the paper I wrote for this conference, with Victor Mitrana and Takashi Yokomori, was accepted. If everything works as planned I will attend the conference, and present the paper; of course I will write some blog posts about the conference and the work presented there. The complete list of accepted papers can be found here (and I must say that the names on that list, as well as the names of the invited speakers, make me belive that AFL 2008 is going to be a good conference, similar to its past editions).
The title of our paper is Some Remarks on the Hairpin Completion, and below you can find its abstract. The complete version of the paper is available upon request.
Abstract: We consider some problems regarding the iterated or non-iterated hairpin completion of some subclasses of regular languages. Thus we obtain a characterization of the class of regular languages as the weak-code images of the k-hairpin completion of center-disjoint k-locally testable languages in the strict sense. This result completes two results from D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: hairpin completion, in Proc. Transgressive Computing, 216-228, 2006, and F. Manea, V. Mitrana, T. Yokomori, Two complementary operations inspired by the DNA hairpin formation: completion and reduction, to appear in Theoretical Computer Science. Then we investigate some decision problems and closure properties of the family of the iterated hairpin completion of singleton languages. Finally, we discuss some algorithms regarding the possibility of computing the values of k such that the non-iterated or iterated k-hairpin completion of a given regular language does not produce new words.
