ON DETERMINISTIC 1-LIMITED 5′→ 3′ SENSING WATSON{CRICK FINITE-STATE TRANSDUCERS

摘要

Finite automata and finite state transducers belong to the bases of (theoretical) computer science with many applications. On the other hand, DNA computing and related bio-inspired paradigms are relatively new fields of computing. Watson-Crick automata are in the intersection of the above fields. These finite automata have two reading heads as they read the upper and lower strands of the input DNA molecule, respectively. In 5' - 3' Watson-Crick automata the two reading heads move in the same biochemical direction, that is, from the 5' end of the strand to the direction of the 3' end. However, in the double-stranded DNA, the DNA strands are directed in opposite way to each other, therefore 5' - 3' Watson-Crick automata read the input from the two extremes. In sensing 5' - 3' automata the automata sense if the two heads are at the same position, moreover, the computing process is finished at that time. Based on this class of automata, we define WK transducers such that, at each transition, exactly one input letter is being processed, and exactly one output letter is written on a normal output tape. Some special cases are defined and analyzed, e.g., when only one of the reading heads is being used and when the transducer has only one state. We also show that the minimal transducer is uniquely defined if the transducer is deterministic and it has marked output, i.e., the output letter written in a step identifies the reading head that is used in that transition. We have also used the functions 'processing order' and 'reading heads' to analyze these transducers.