Abstract | ||
---|---|---|
We consider a restricted variant of the hairpin completion called bounded hairpin completion. The hairpin completion is a
formal operation inspired from biochemistry. Applied to a word encoding a single stranded molecule x such that either a suffix or a prefix of x is complementary to a subword of x, hairpin completion produces a new word z, which is a prolongation of x to the right or to the left by annealing.
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 also define the inverse operation, namely bounded
hairpin reduction, and consider the set of all primitive bounded hairpin roots of a regular language.
|
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-642-00982-2_37 | Information & Computation |
Keywords | Field | DocType |
bounded hairpin reduction,closure property,current word,inverse operation,hairpin completion,formal operation,bounded hairpin completion,new word,formal language,iterated bounded hairpin completion,primitive bounded hairpin root,formal languages,dna computing,regular language | Discrete mathematics,Combinatorics,Formal language,Suffix,Closure (mathematics),Prefix,Regular language,Iterated function,Mathematics,Bounded function,DNA computing | Conference |
Volume | ISSN | Citations |
5457 | 0302-9743 | 7 |
PageRank | References | Authors |
0.57 | 11 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Masami Ito | 1 | 299 | 66.19 |
peter leupold | 2 | 11 | 2.41 |
florin manea | 3 | 7 | 0.57 |
Victor Mitrana | 4 | 950 | 119.63 |