Publication: INVOLUTIVE FIBONACCI WORDS
Date
01-01-2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
“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 positive integers n ≥ 1, where “·” denotes word concatenation. In this paper, we first propose a unified terminology that allows readers to identify the different types of Fibonacci words, and corresponding results, that appear under the umbrella term “Fibonacci words” in the extensive literature on the topic. Motivated by ideas stemming from theoretical studies of DNA computing, we then define and explore involutive Fibonacci words (φ-Fibonacci words and indexed φ-Fibonacci words, where φ denotes either a morphic or an antimorphic involution), and study various properties of such words.
Description
Keywords
antimorphic involution, DNA computing, Fibonacci words, involutive Fibonacci words, Watson-Crick complementarity