Quasi-deterministic finite one-head and two-head automata

Determinism is a central concept of computations. In some computational models, e.g., (traditional one-head) finite automata, deterministic and nondeterministic variants characterize the same language class. Considering other models, e.g., the 2-head finite automata known as sensing 5′ → 3′ Watson–Crick automata, the deterministic variants are weaker than the nondeterministic ones, i.e., the former variants characterize a proper subset of the language class accepted by the latter ones. Watson–Crick finite automata emerged as a model of DNA computing: they work on a Watson–Crick tape, on double stranded DNA molecules, thus they have two heads, one for each strand. The heads of sensing 5′ → 3′ Watson–Crick automata start from the two extremes of the input, read the input in opposite direction and the computation finishes when the heads meet. Variants based on restrictions on the set of states (e.g., stateless) and on the (head movements in) transitions (e.g., 1-limited), as well as, nondeterministic, deterministic and the recently investigated state-deterministic variants have been studied. In this paper a new concept, quasi-determinism is investigated, that is, in each configuration of a computation (if it is not finished yet), the next state is uniquely determined although the next configuration may not be, in case various transitions are enabled at the same time. We prove that this new concept is a generalisation of both of usual determinism and state-determinism both for finite one-head and two-head automata. More precisely, the class of quasi-deterministic sensing 5′ → 3′ Watson–Crick automata is a superclass of both of the mentioned other classes of sensing 5′ → 3′ Watson–Crick automata. The new sublinear class of languages characterized by the new model is not closed under the regular operations, under intersection, nor under complement. Hierarchy of language classes accepted by various subclasses of quasi-deterministic sensing 5′ → 3′ Watson–Crick automata and also some other well-known classes is presented.