DNA Languages Favourable for Computation: Involutive Factor-Free Languages

Abstract

Formal languages play a central role in many branches of study, including DNA computing. A DNA strand, the basic unit of every living cell, is a sequence of nucleotides Adenine, Guanine, Cytosine, Thymine denoted by the symbols A, G, C, and T with the nucleotides A binding to T and C binding to G. A DNA strand can thus be viewed as a word over the four-letter DNA alphabet
{A, T, C, G} and the relation between the nucleotides can be expressed in terms of an involution mapping, also known as the Watson Crick involution[1]. Generalizing the notion of Watson-Crick complementary which is central in DNA computing, involutively bordered words and involutively unbordered words were introduced and investigated[3].  Also, the combinatorial properties of words have been investigated over DNA computing. Let θ be a morphic or antimorphic involution of ^∗.

A word w ∈ ∗ is a θ- factor free or involutive factor free if none of its factors is a θ- factor of the word w[2].  In this paper, we propose to study the involutive factor-free languages over the Watson-Crick alphabet and their properties.