On the Iterated Hairpin Completion

Details On the Iterated Hairpin Completion On the Iterated Hairpin Completion

2010-10-18

arxiv.org/abs/1010.3640v3

Computer Science

Formal Languages and Automata Theory

Scientific paper

The (bounded) hairpin completion and its iterated versions are operations on formal lan- guages which have been inspired by the hairpin formation in DNA-biochemistry. The paper answers two questions asked in the literature about the iterated hairpin completion. The first question is whether the class of regular languages is closed under iterated bounded hairpin completion. Here we show that this is true by providing a more general result which applies to all the classes of languages which are closed under finite union, intersection with regular sets, and concatenation with regular sets. In particular, all Chomsky classes and all standard complexity classes are closed under iterated bounded hairpin completion. In the second part of the paper we address the question whether the iterated hairpin completion of a singleton is always regular. In contrast to the first question, this one has a negative answer. We exhibit an example of a singleton language whose iterated hairpin completion is not regular, actually it is not context-free, but context-sensitive.

Affiliated with

Also associated with

No associations

Rating

On the Iterated Hairpin Completion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Iterated Hairpin Completion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Iterated Hairpin Completion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-306327