On the Languages Accepted by Watson-Crick Finite Automata with Delays

Abstract

In this work, we analyze the computational power of Watson-Crick finite automata (WKFA) if some restrictions over the transition function in the model are imposed. We consider that the restrictions imposed refer to the maximum length difference between the two input strands which is called the delay. We prove that the language class accepted by WKFA with such restrictions is a proper subclass of the languages accepted by arbitrary WKFA in general. In addition, we initiate the study of the language classes characterized by WKFAs with bounded delays. We prove some of the results by means of various relationships between WKFA and sticker systems.

Keywords

• Watson-Crick finite automata
• sticker systems
• DNA computing
• formal languages