科研之友
微信
新浪微博
Facebook
分享链接
摘要
The concepts of pseudo-bordered and pseudo-unbordered words are in large part motivated by research in theoretical DNA computing, wherein the Watson-Crick complementarity of DNA strands is modelled as an antimorphic involution, that is, a function which is an antimorphism, , and an involution, , for all words u, v over the DNA alphabet. In particular, a word w is said to be -bordered (or pseudo-bordered) if there exists a word that is a proper prefix of w, while is a proper suffix of w. A word which is not -bordered is -unbordered. This paper continues the exploration of properties (for the case where is a morphic involution) of the set of -unbordered words, , and the sets of words that have exactly i -borders, , . We prove that, under some conditions, the set is disjunctive for all , and that the set is disjunctive for all , where D(i) denotes the set of words with exactly i borders. We also discuss conditions for catenations of languages of -unbordered words to remain -unbordered, and anticipate further generalizations by showing that the set of all -bordered words is not context-free for all morphisms over an alphabet with such that for all and equals the identity function on .
- 出版日期2017-6
