ABSTRACT

Watson Crick automata are finite automata working on double strands. Extensive research work has already been done on non deterministic Watson Crick automata and on deterministic Watson Crick automata. Parallel Communicating Watson Crick automata systems have been introduced by E. Czeziler et al. In this paper we discuss about a variant of Watson Crick automata known as the two-way Watson Crick automata which are more powerful than non-deterministic Watson Crick automata. We also establish the equivalence of different subclasses of two-way Watson crick automata. We further show that recursively enumerable (RE) languages can be realized by an image of generalized sequential machine (gsm) mapping of two-way Watson-Crick automata.

1. Introduction

The tremendous progress in biotechnology has resulted in decoding of DNA sequences, synthesizing and manipulating DNA, which lead to its usage in computation by computer scientists. As a result sticker systems, splicing systems and carving systems came into existence [1]. Many of the NP-complete problems were solved efficiently using DNA computing. The first, the Adleman experiment was done in 1994 [2]. As the interest in using DNA in computation increased so did the need for automata which exploit the properties of DNA. The first such automata which exploited the DNA property were the Watson-Crick automata [3] which are the automata counterpart of the Sticker Systems. Essentially Watson-Crick automata are finite automata having two independent heads working on double strands where the characters on the corresponding positions of the two strands are connected by a complementarity relation similar to the Watson-Crick complementarity relation.

The movement of the heads although independent of each other is controlled by a single state.

Details of several variants of non-deterministic Watson-Crick automata have been explored in [4].

Deterministic Watson-Crick automata and their variants have been explicitly handled in [5,6]. Parallel Communicating Watson-Crick automata were introduced in [7] and further investigated in [8]. A survey of WatsonCrick automata can be found in [9]. The effect of the complementarity relation on the computing power of Watson Crick automata is discussed in [10].

Two-way finite automaton (FA) is an abstract machine, a generalized version of the finite automaton which can revisit characters already processed. As in FA, in twoway FA there are finite number of states with transitions between them based on the current character; but each transition is also labeled with a value indicating whether the machine will move its reading head to the left, right, or stay at the same position. Equivalently, 2FAs can be seen as read-only Turing machines with no work tape; only a read-only input tape. The accepting condition is that when the reading head falls off the right end of the tape and the state in which the machine is at that time is final state then the input word is accepted. A twoway Watson Crick automaton (2AWK) is similar in concept to a two-way finite automaton. The only difference between them is that in two-way Watson Crick automata the input tape is double stranded. The idea of two-way Watson Crick automata were introduced in [4] but no comparison of its power with respect to AWK was discussed. The importance of 2AWK is that unlike two-way FA which is equal in power to a FA, 2AWK are more powerful than AWK which we establish in this paper.

In this paper, we give a general description of non-deterministic Watson Crick automata and its different subclasses in Sections 2 and 3. In Section 4 we describe the twin shuffle language and state the relation of twin shuffle language with RE languages. In the following section we state the rules governing two-way non-deterministic Watson Crick automata. In Section 6 we give the definition of the different classes (variants) of 2AWK and investigate the relationship between classes of 2AWK automata. We show that 2AWK = 2SWK = 21WK = 2FWK = 2FSWK = 2F1WK similar to the case of Watson Crick automata. We further show the family of languages accepted by 2AWK is context sensitive. In Section 7 we show that two-way non-deterministic Watson Crick automata are more powerful than non-deterministic Watson Crick automata. In Section 9 we further show that recursively enumerable (RE) languages can be realized by an image of generalized sequential machine (gsm) mapping of two-way Watson-Crick automata.

2. Basic Terminology for Watson-Crick Automata

V is a finite alphabet. V^* denotes the set of all finite words over V, including the empty wordFor denotes the length of w. Let and be two words and if there is some word, such that, then u is the prefix of v, denoted by. Two words, u and v are prefix comparable denoted by u~_pv if u is a prefix of v or vice versa.

Given two alphabets V and U a mapping h:

extended to s: by and for is called a morphism. If for each, then h is a λ free morphism.

A morphism h: is called a coding iffor each and a weak coding iffor each If is the morphism defined by for, and otherwise, then we say that h is a projection (associated with) and we denote it by pr_V1.

For we define their shuffle by

A generalized sequential machine (gsm) is a sequential transducer. Such a device is a systemwhere Q is the set of states, are the alphabets(input and output alphabets) of the automaton, is the initial state, is the set of final states and is the transition mapping.

The definitions of morphism, gsm and shuffle are stated in [1].

A Watson-Crick automaton is a 6-tuple of the form where is an alphabet set, is a set of states, is the complementarity relation similar to Watson Crick complementarity relation and q₀ is the initial state and is the set of final states. The function contains a finite number of transition rules of the form, which denotes that the machine in state q parses w₁ in upper strand and w₂ in lower strand and goes to state where. is different from. is just a pair of strings written in that form instead ofwhereas in the two strands are of same length i.e. and the corresponding symbols in two strands are complementarity in the sense of relation ρ.

and

.

A transition in a Watson-Crick finite automaton can be defined as follows:

For, such that

and

iff there is transition rule in.

denotes the transitive and reflexive closure of.The language accepted by Watson-Crick Automata is

For a Watson-Crick Automaton M, with inputwhere w₁ is any string in V^* and where q₀ is the initial state and q_f is a final state. Then is a computation in M denoted by.

Another important language associated with WatsonCrick automaton is defined taking into consideration the transitions and not the language recognised.

For a Watson-Crick Automaton consider a labelingof rules in with elements in a set Lab. For computationdenoted by the control word of, that is the sequence of labels of transition rules used in. In this way the language is obtained.

The definition of is stated in [4].

3. Subclasses of Non-Deterministic Watson-Crick Automata (AWK)

Depending on the type of states and transition rules there are four types or subclasses of Watson-Crick Automata. Watson-Crick Automaton is

1) stateless (NWK): If it has only one state, i.e.

2) all-final (FWK): If all the states are final, i.e.

3) simple (SWK): If at each step the automaton reads either from the upper strand or from the lower strand, i.e. for any transition rule

4) 1-limlited (1WK): If for any transition rule q

, we have.

Theorem 1: Simple and 1 limited Watson-Crick automata accept the same family of languages as the family of languages accepted by Watson-Crick automata with arbitrary transition rules.

The proof of Theorem 1 is in [4].

Theorem 2: Non-deterministic Watson-Crick automata are equivalent with non-deterministic simple Watson-Crick automata.

Corollary 1: Non-deterministic Watson-Crick automata are equivalent with non-deterministic 1-limited Watson-Crick automata.

The proof of Theorem 2 and Corollary 1 are given in [4].

4. Twin-Shuffle Language

Consider an alphabet V and its barred variant,. The language

is called the twin-shuffle language over. (For a string denotes the string obtained by replacing each symbol in x with its barred variant).

For the morphism h: defined by

Clearly the equality is

Theorem 3: Each recursively enumerable language can be written in the form , where is an alphabet and R is a regular language.

In this representation, the language TS_V depends on the language L. This can be avoided in the following way:

Let a coding be for instance,, where is the symbol of in a specified ordering. The language is regular. A generalized sequential machine can simulate the intersection with a regular language, the projection as well as the decoding of elements in Thus we obtain:

Corollary 2: For each recursively enumerable language there is a gsm gL such that

Therefore, by using a sequential transducer which can be a deterministic one, we can obtain all recursively enumerable language, starting from the unique language Proofs of Theorem 3 and Corollary 2 are in [1].

5. Two-Way Non-Deterministic Watson Crick Automata (2AWK)

Two-way non-deterministic Watson Crick automata system is a 6 tuple, where is a set of alphabet, are the beginning and the end marker respectively; that is the word w to be recognized is provided as an input to the automaton in the form is a set of states, and and is the complementarity relation and is the initial state and is the set of final states. is the finite number of transition rules;

1) either of the form, which denotes that the machine in state q parses in upper strand in dir₁ direction and in lower strand in dir₂ direction and goes to state wherewhere L signifies that the head is reading the word in the left direction, R signifies that the head is reading the word in right direction and if a head reads the empty word it remains in its current position denoted by 0.

2) or of the forms, whereand with restrictions that when the correspondingand when the corresponding. Moreover, there cannot be transition rules having the form wherewhere and or where and or both. These rules ensure that the reading heads do not go past the input word on the left side or the heads do not move when it reads empty word. Moreover once a head goes past the right end of the tape it cannot comeback.

Accepting conditions

is accepted by if, starting in state (initial state) with and on the double stranded input tape and the two heads at the left end of and respectively, eventually enters a final state at the same time both the heads fall off the right hand side of the double stranded input tape.

The word is rejected if one of the following 3 conditions occurs:

1) The two-way WK automaton goes into a loop which is identified in a similar way as loops in two-way FAs are identified.

2) When both the heads fall off the right hand side of the input tape and the machine is in a non final state.

3) If the machine comes to a halt (i.e. there are no transition rules that can be applied for that particular state in which the machine is) before the heads fall off the right hand side of the input tape.

i.e. mathematically

6. Subclasses of Two-Way Non-Deterministic Watson-Crick Automata (2AWK)

Depending on the type of states and transition rules there are four types or subclasses of two-way Watson-Crick Automata similar to Watson Crick automata.

2-way Watson-Crick Automaton

is

1) stateless (2NWK): If it has only one state, i.e.

2) all-final (2FWK): If all the states are final, i.e.

3) simple (2SWK): If at each step the automaton reads either from the upper strand or from the lower strand, i.e.for any transition rule either

4) 1-limlited (21WK): If for any transition rule, we have

Many combinations of these classes can also be obtained such as all-final simple two-way WK automata (2FSWK), all final 1 limited two-way WK automata (21FWK), stateless 1 limited two-way WK automata (21NWK) etc.

Theorem 4: Simple and 1 limited two-way Watson Crick automata accept the same family of languages as the family of languages accepted by two-way Watson Crick automata with arbitrary transition rules.

The proof of theorem is similar to the proof done in [4] for Theorem 1.

Let be a non-deterministic two-way Watson Crick automaton. We introduce a 1 limited two-way Watson Crick automatonFor each transition rule t of the form in where where and where and the condition is imposed because rules with is already in the 1-limited form and no further modification is required for them. We introduce new rules in of the form

.

All the new states are introduced in Q’ along with states in Q. From the construction of M’ which is obtained from M it is obvious that both M’ and M recognize the same language. So 2AWK are subset of 21WK and from the definition of 21WK and AWK we know that 21WK are subset of 2AWK. So 2AWK and 21WK are equivalent i.e. they accept the same family of languages. A similar proof can also be established for 2SWK. Therefore we can say, 2AWK = 2SWK = 21WK.

Theorem 5: All final two-way Watson Crick automata accept the same family of languages as the family of languages accepted by two-way Watson Crick automata with arbitrary transition rules.

Let be a two-way non-deterministic Watson Crick automaton. We introduce an all final two-way Watson Crick automatonEach transition rule t of the form in δ where whereand where falls under one of the five classes. The classes are defined as follows:

Class 1: Transition rules of the form

in where whereand where and and i.e. w₁ and w₂ do not have $ at their ends.

Class 2: Transition rules of the form

in where where and

where, and i.e. and both have $ at their ends.

Class 3: Transition rules of the form

in where where

and where and i.e. has at its end and does not have at its end.

Class 4: Transition rules of the form

in where where andwhere and i.e. does not have at its end and has at its end.

Class 5: Either transition rules of the form

in or transition rules of the form

in or transition rules of the form in.

The transition rules of are modified as follows to form the transition rules of.

Transition rules of which fall in class 1 and class 5 are kept same in.

For transition rules of which belong to class 2 two instances can occur;

case 1: For transition, where is a final state. In this case the transition rules are kept same in.

case 2: For transition, where is a non final state. In this case the transition rules of are modified as follows for.

For each transition rule in belonging to class 2 where is a non final state,where and are introduced in and there is no transition from in. These new rules in ensure that if the heads go off the right end of the tape in when is in a non final state then would go to state and would not accept the string as there is no transition from i.e. the above stated rules ensure the heads do not fall off the right end of the tape for when does not accept the word. As is all final if the heads go off the right end of the tape it will accept the given string.

For transition rules of which belong to class 3 the following modifications are needed. Class 3 also has two instances similar to class 2.

case 1: For transition, where is a final state. In this case the transition rules are kept same in.

case 2: For transition, where is a non final state. In this case the transition rules of are modified as follows for.

For each transition rule in belonging to class 3 where is a non final state,where is introduced inwhere denotes that the head on the upper strand has gone past the right end marker in the original machine on application of the above transition rule.

Only rules having λ on the upper strand are applied to because in the actual machine if the above rules of class 3 are applied then the upper head would have gone past the right end of the tape. So only rules having λ on the upper head can be applied to the machine. As replicates similar thing is done in too.

Thus, all the transition rules that can be applied to in with on the upper strand and and in the lower strand can also be applied to in. Rules having on the upper strand and and in the lower strand where the transition goes to a final state are applied to. Finally for rules with on the upper strand andand in the lower strand where the transition goes to a non final state, the rules of the form where are introduced in and there are no transition rules from These rules ensure that when M reaches the end of the string on a non final state then goes to and does not accept the string as there is no transition from i.e. the above stated rules ensure the heads do not fall off the right end of the tape for when heads off M fall off the right end and the state to which M goes is non final.

Class 4 rules are handled in a similar way to class 3 rules.

It is obvious from the transition rules introduced in that accepts the same family of languages as M.

Thus, 2FWK = 2AWK.

Theorem 6: All final 1 limited two-way Watson Crick automata accept the same family of languages as the family of languages accepted by 1 limited twoway Watson Crick automata with arbitrary transition rules.

Let be a two-way 1 limited non-deterministic Watson Crick automaton. We introduce an all final 1 limited two-way Watson Crick automaton Each transition rule t of the form in where falls under one of the four classes. The classes are defined as follows:

Class 1: Transition rules of the form

in where

Class 2: Transition rules of the form

in.

Class 3: Transition rules of the form

in.

Class 4: Transition rules of the form

in or transition rules of the form in

The transition rules of are modified as follows to form the transition rules of.

Transition rules of which fall in class 1 and class 4 are kept same in.

For transition rules of which belong to class 2 have two instances.

case 1: For transition, where is a final state. In this case the transition rules are kept same in.

case 2: For transition, where is a non final state. In this case the transition rules of are modified as follows for.

For each transition rule in belonging to class 2 where is a non final state,and where are introduced in. denotes that the head on the upper strand has gone past the right end marker in the original machine.

Only rules having on the upper strand can be applied to (for reasons similar to reasons stated in proof of Theorem 5). Thus, all the transition rules that can be applied to with on the upper strand and in the lower strand are applied to. For rules having on the upper strand and in the lower strand where the transition goes to a final state are applied to. Finally for rules with on the upper strand and in the lower strand where the transition goes to a non final state in, the rules of the formand, whereare introduced in. These rules ensure that when reaches the end of the string on a non final state, does not accept the string as there are no transitions from state

Class 3 is handled in a similar way as class 2.

It is obvious from the transition rules introduced in that accepts the same family of languages as.

Thus, 21FWK = 21WK.

Corollary 3: All final 1 limited two-way Watson Crick automata accept the same family of languages as the family of languages accepted by arbitrary twoway Watson Crick automata with arbitrary transition rules.

Proof: From Theorem 4 we know 2AWK = 21WK and from Theorem 6 we obtain 21FWK = 21WK. Thus combining both the results we get 21FWK = AWK.

Thus from the above Theorems we can state that 2AWK = 21FWK = 21WK = 2SWK = 2FSWK = 2FWK.

7. Power of Two-Way Non-Deterministic WK Automata

In this section we first show that AWK are subset of 2AWK. Then we further show that this subset relation is proper i.e. 2AWK are more powerful than AWK.

Theorem 7: AWK 2AWK.

The theorem says that non-deterministic Watson Crick automata are subset of two-way non-deterministic Watson Crick automata.

Proof:

Let be a non-deterministic Watson Crick automaton where is a set of alphabet, is a set of states, is the complementarity relation and is the initial state and is the set of final states. is the finite number of transition rules of the form, where

We introduce a two-way non-deterministic Watson Crick automaton

where is a set of alphabet, are the beginning and the end marker respectively, that is, the word w to be recognized is provided as an input to the automaton in the form is the complementarity relation and is the initial state and q_f is a final state. is the finite number of transition rules of the form

1) For each rule in introduce

in.

2).

3) For each state in introduce

in.

From the construction of it is evident that all that will be accepted by will be accepted by.

Theorem 8: One-Way Two headed finite automata are equivalent to AWK

An informal proof of this theorem is in [4].

Example 1

Let be a 2AWK where are the beginning and the end marker respectively, that is, the word w to be recognized is provided as an input to the automaton in the form is a set of states, is the identity complementarity relation and is the initial state and is the set of final states. is the finite number of transition rules. In this example the mirror language andwhere denotes the reverse of is accepted using two-way Watson Crick automaton.

The transition rules of are as follow

.

Theorem 9: One-way finite automata with 2 heads cannot accept the mirror language.

The above theorem is stated in [11].

Theorem 10: 2AWK are more powerful than AWK i.e. AWK 2AWK.

Proof. From Theorem 8 we know that AWK is equivalent to 1-way two headed finite automata and from Theorem 9 we know that 1-way two headed finite automata cannot recognize the mirror language. Thus AWK cannot recognize the mirror language. But in Example 1 we have shown that two-way AWK can accept the mirror language and in theorem 7 we have shown that AWK 2AWK i.e. 2AWK accepts all the family of languages which are accepted by AWK. Moreover it also accepts the mirror language which AWK cannot accept. Thus 2AWK accepts at least one language more than AWK. Hence we conclude that the accepting power of two-way AWK is more than AWK. Mathematically AWK 2AWK, i.e. the subset relation is proper.

Theorem 11: Family of languages accepted by WK automata is context sensitive.

A linear bounded Turing machine (LBA) can simulate the actions of two-way Watson Crick automaton. As the language accepted by LBA is context sensitive so the family of languages accepted by two-way Watson Crick automaton is also context sensitive.

8. Characterization of Recursively Enumerable (RE) Languages in Terms of 2AWK Automata

In this section we discuss 2AWK in the light of the RE languages. We show each language in the family of RE is the image of a gsm mapping of a language in 2 AWK.

Theorem 12: TS_V ( AWK(ctrl)

The proof of this theorem is in [4].

Theorem 13: For each recursively enumerable language L there is a gsm g_L such that L = g_L (2AWK (ctrl)).

Proof: We have already shown in Theorem 7 AWK 2AWK and it is stated in [4] that TS_V Î AWK(ctrl) and from corollary 2 we know that each language in the family of RE is the image of a gsm mapping of a language in TS_{0,1}. As TS_V Î AWK(ctrl) and AWK Î 2AWK, so we can state, each language in the family of RE is the image of a gsm mapping of a language in 2AWK(ctrl).

9. Conclusion

In this paper, we discuss about the power of a variant of non-deterministic Watson Crick automata known as 2AWK. We describe their structure and accepting conditions. We introduce different subclasses of 2AWK similar to AWK and show the equivalence of some of those subclasses. We further establish the fact that 2AWK are more powerful than AWK. Based on the relation between AWK and 2AWK we show that a gsm mapping of 2AWK results in the generation of each language in the family of the recursively enumerable languages.

REFERENCES

Abbreviations

AWK: non-deterministic Watson-Crick automata.

NWK: stateless non-deterministic Watson-Crick automata.

FWK: all final non-deterministic Watson-Crick automata.

SWK: simple non-deterministic Watson-Crick automata.

1WK: 1-limited non-deterministic Watson-Crick automata.

2AWK: two way non-deterministic Watson-Crick automata.

2NWK: two way stateless non-deterministic WatsonCrick automata.

2FWK: two way all final non-deterministic WatsonCrick automata.

2SWK: two way simple non-deterministic WatsonCrick automata.

21WK: two way 1-limited non-deterministic WatsonCrick automata.

TS_V: twin-shuffle language.

RE: recursive enumerable.

gsm: generalized sequential machine.