Bounded hairpin completion

Although this operation is a purely mathematical one and the biological reality is just a source of inspiration, it seems rather unrealistic to impose no restriction on the length of the prefix or suffix added by the hairpin completion. The restriction considered here concerns the length of all prefixes and suffixes that are added to the current word by hairpin completion. They cannot be longer than a given constant. Closure properties of some classes of formal languages under the non-iterated and iterated bounded hairpin completion are investigated. We consider the bounded hairpin completion distance between two words and generalize this distance to languages and discuss algorithms for computing them. Finally also the inverse operation, namely bounded hairpin reduction, as well as the set of all primitive bounded hairpin roots of a regular language are considered.