Deterministic and Nondeterministic Sensing 5' - 3' Watson-Crick Automata without Sensing Parameter

Watson-Crick (abbreviated as WK) finite automata are working on double stranded DNA molecule that is also called Watson-Crick tape. Subsequently, these automata have two reading heads, one for each strand. While in traditional WK automata both heads read the whole input in the same physical direction, in 5 ′ → 3′ WK automata the heads start from the two extremes (say 5 ′ end of the strands) and read the input in opposite direction. In sensing 5 ′ → 3′ WK automata the process on the input is finished when the heads meet. Since the heads of a WK automaton may read longer strings in a transition, in previous models a so-called sensing parameter took care for the proper meeting of the heads (not allowing to read the same positions of the input in the last step). We have investigated a new model which works without the sensing parameter (it is done by an appropriate change of the concept of the configuration). In this thesis, the nondeterministic and deterministic automata in the new model are studied. Consequently, for the nondeterministic part, the accepted language classes of variants are changed and various hierarchy results are proven. For the deterministic part, it is proven to accept the language class 2detLIN defined by the deterministic variant of the earlier version. However, using some of the restricted variants, e.g., all-final automata, the classes of the accepted languages are changed showing a finer hierarchy inside the class of linear context-free languages, hierarchy. Keywords: nondeterministic Watson-Crick automata, deterministic Watson-Crick automata, 5 ′ → 3′ WK automata, finite automata, deterministic computations, linear context-free languages.