State-deterministic 5? ? 3? Watson-Crick automata

Abstract

Watson-Crick (WK) finite automata are working on a Watson-Crick tape, that is, on a DNA molecule. Therefore, they have two reading heads, one for each strand. In traditional WK automata both heads read the whole input in the same physical direction, but in 5' -> 3' WK automata the heads start from the two extremes and read the input in opposite direction. In sensing 5' -> 3' WK automata the process on the input is finished when the heads meet, and the model characterise the linear context-free languages. Deterministic variants are weaker, the class 2detLIN is accepted by them. In this paper a new concept, the state-determinism is investigated, that is in each configuration of a computation (if it is not finished yet) the next state is determined by the actual state of the configuration. There are various usual restrictions on WK automata, e.g., all-final, stateless or 1-limited variants. We place the new class, the state-deterministic 5' -> 3' WK automata, into the hierarchy based on the accepted language classes. Further, various hierarchy results including combined restrictions, e.g., 1-limited all-final state-deterministic 5' -> 3' WK automata are shown.