PRIMITIVITY OF ATOM WATSON-CRICK FIBONACCI WORDS

“Fibonacci strings” were first defined by Knuth in his 1968 “The Art of Computer Programming,” as being an infinite sequence of strings obtained from two initial letters f1 = a and f2 = b, by the recursive definition fn+2 = fn+1 · fn, for all posi-tive integers n ≥ 1, where “·” denotes word concatenation. Motivated by theoretical studies of DNA computing, several generalizations of Fibonnaci words have been pro-posed under the umbrella term involutive Fibonacci words. These include φ-Fibonacci words and indexed φ-Fibonacci words, where φ denotes either a morphic or an anti-morphic involution. (In the particular case of the DNA alphabet ∆ = {A, C, G, T }, where φ is the Watson-Crick complementarity (antimorphic) involution on ∆∗ that maps A to T, G to C, and vice versa, the φ-Fibonacci words are termed atom Watson-Crick Fibonacci words.) In this paper, we investigate the properties of atom φ-Fibonacci words over a four-letter alphabet, whereby “atom” indicates that the two initial words are singleton letters. The results are different from the case of the classical Fibonacci words over a two-letter alphabet, which are all primitive, in that for some (anti)morphic involutions, some initial letters, and some indices n, we have that the n-th atom φ-Fibonacci word is primitive, while for some others it is not. In the particular case of the Watson-Crick complementarity antimorphic involution, regardless of the initial two letters in the Fibonacci recursion (different, or the same), for all n > 3, the n-th atom Watson-Crick Fibonacci word is primitive.