Coding Properties of DNA Languages

            S. Hussini, L. Kari, S. Konstantinidis

The computation language of a DNA-based system consists of all the
words (DNA strands) that can appear in any computation step of the
system. In this work we define properties of languages which ensure 
that the words of such languages will not form undesirable bonds when 
used in DNA computations. We give several characterizations of the 
desired properties and provide methods for obtaining languages with 
such properties. The decidability of these properties is addressed as 
well. As an application we consider splicing systems whose computation 
language is free of certain undesirable bonds and is generated by 
nearly optimal comma-free codes.