The objective of this `applied algorithm` project is to continue the establishment and study of the interrelationships between formal language theory and the structure and behavior of the informational macromolecules. The formal representation of recombinant behaviors exhibited by double stranded DNA in the presence of specified sets of enzymatic activities is of crucial interest. This project includes the continued investigation of splicing systems and the languages they define. The fact that DNA occurs naturally in both linear and circular forms, which interact through recombination, has motivated the initiation of a unified theory of interacting linear and circular words. This project includes further development of this theory with emphasis on splicing. A treatment of languages of bi-infinite words and semi-infinite words is made, which will initiate the integration of these theories with the theories of languages of circular and finite words. This project directs special attention to the sofic shifts, which are a class of languages of bi-infinite words that play a major role in dynamical systems. This project is significant in that it establishes and clarifies relations between formal language theory and molecular biology. It develops an additional source of suggestive problems and imagery for formal language theory. Also, over a time scale of decades, it is expected to suggest questions and contribute precision to biochemical thought about informational macromolecules and their behavior. Additionally, the project provides new problems and approaches to the study of symbolic dynamics. This project combines theoretical computer science, biology and dynamical systems in a mutually stimulating and reinforcing way.
