We explore the relationship of Watson-Crick automata and string assembling systems. In the general case, Watson-Crick automata are more powerful, so restricting the study to the stateless variant is of interest. We show that the class of languages of stateless Watson-Crick automata are strictly included in the class of languages of automata with at least two states, then compare string assembling systems with the stateless variant. It turns out, that there are languages that can be generated by string assembling systems, but not accepted by stateless WatsonCrick automata, but the question concerning the exact relationship of the language classes remains open.
The double stranded structure of DNA motivated the
introduction and study of double stranded strings with the
tools and techniques of formal language theory, that is, the
definition of string operations which model the
biochemical processes that the corresponding strings can undergo,
see the monograph [
Sticker systems were introduced in [
Research supported by the construction EFOP-3.6.3-VEKOP-162017-00002 supported by the European Union, co-financed by the European Social Fund, and by grant K 120558 of the National Research, Development and Innovation Office of Hungary (NKFIH), financed under the K 16 funding scheme.
Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
The other model interesting for our investigations is
called Watson-Crick finite automaton, and it was
introduced in [
For a finite alphabet of symbols V , let V denote the set of all strings over V , and let V + = V n fl g where l denotes the empty string. We consider two languages L1; L2 V equal if they differ in at most the empty string, L1 n fl g = L2 n fl g. The length of a word w 2 V is denoted by jwj, the number of occurrences of a symbol x 2 V in w is denoted by jwjx.
(w1; w2) 2 V
V
V We denote the last letters and the first letters of a string u u u
as end( ) and bgn( ): v v v w1 , while w2 1. If u = u0x; v = v0y for some x; y 2 V; u0; v0 2 V , u0x x then end( ) = . Similarly, the first letters y for u = xu0 and v = yv0 are denoted
where x; y 2 V; u0; v0 2 V . of the pair as bgn( l xu0 yv0 ) = 2. Otherwise, if one of the strings is empty, we l l u0x x have end( ) = , end( ) = , v0y y l l ) = , and bgn( ) =
for xu0
The complementarity relation is a symmetric relation on the letters of the alphabet r V V . We call the set of sequences of pairs of complementary symbols a WatsonCrick domain and denote it with W Kr (V ), more formally, The string pair
w case of written as
where w = x1x2 : : : xn; w0 = y1y2 : : : yn. We w0 also denote the complement of x 2 V by x, that is, (x; x) 2 r, and the complement of x is x, so x = x, and (x; x) 2 r.
w1 w1
The difference between w2 and ww12 is that w2 only gives a different notation for (w1; w2), while in the w1
2 W Kr (V ), jw1j = jw2j and w2 is the comw2 plement of w1, w2 = w1 (also w2 = w1). 2.1
Now we recall the definition of Watson-Crick automata
from [
The construct M = hV; r; Q; q0; F; d i is a Watson-Crick automaton (WK automaton in short), where
V
r F
q0 2 Q is the initial state,
V d : Q
V sition relation.
! 2Q is a finite relation, the state tran
ww21 q ww43 where ww21 2 VV is the part of the input which is already read, q 2 Q is the state of the WK automaton, and ww34 2 VV is the part of the input which is not read yet.
), and defined as follows.
Let uv11 ; uv22 ; uv33 2 VV ; uv11uv22vu33 2 W Kr (V ), q; q0 2 Q. Then u1 q v1 u2u3 if and only if, q0 2 d (q; u2 ). We may also write v2 if we are not interested in the states of the automaton and in the rest of the input to be read.
If the reflexive and transitive closure of ) is denoted by ) , then the language accepted by M is
w L(M) = fw 2 V j q0 w ) w w
q f ; w w where 2 W Kr (V ); q f 2 Fg: 2.2
Now we recall the definition of string assembling systems
from [
The 4-tuple S = hS; A; T; Ei is a string assembling system (SAS in short), where
A T E uv u
S+
or S+
S+ of the form
S+ is the finite set of axioms of the form u
with u 2 S+; v 2 S , uv S+ is the finite set of assembly units, S+ is the finite set of ending assembly units uv or v with u 2 S ; v 2 S+.
v uv to the unit
A derivation step of the SAS S as above is denoted by ), and defined as follows. We say that we added the unit xu2 u1 , denoted as v1 u1 v1 ) u1u2 ; v1v2 if and only if, x y = end( u1 ) for some x; y 2 S, and
v1 2 T [ E. Moreover, if ju1u2j yv2 can be written as u1u2 = v1v2u0 for some u0 2 S , or the other way around, if ju1u2j jv1v2j, then u1u2v0 = v1v2 for some v0 2 S .
A sequence of derivation steps is a derivation. A derivation is successful, if after choosing an axiom from A, we jv1v2j, then u1u2 yv2 xu2 add assembling units from T , then close the derivation by adding a unit from E, in such a way that the upper and lower string of the string pair which is produced is identical.
If the reflexive and transitive closure of ) is denoted by ) , then the language generated by S is
u L(S) = fw 2 S+ j v ) w w
is a successful derivationg:
Now we introduce some additional notation that will be useful later. The string pair generated in k derivation steps, or in the case of WK automata, the string pair read in k transition steps, is denoted by u(k) , that is, v(k) uv00 ) uv00uv11 :: :: :: vukk 11vukk = uv((kk)) . The pair uv((00)) denotes an axiom, or in the case of WK automata, the l pair , representing the fact that nothing has been read l from the input yet.
Let Dk denote the difference of the length of upper and u lower element of the string pair added in the kth v derivation step, or read in the kth state transition, that is,Dk = juj jvj, and let D(k) denote the difference of the generated strings or the strings read on the upper and lower pert of the input tape in k derivation or state transition steps, that is, for u(k) , let D(k) = ju(k)j jv(k)j.
v(k)
generated by a computational model X by L (X ), so let L (SAS) and L (W K) denote the classes of languages generated by SAS and accepted by WK automata, respectively. 3
The computational power of Watson-Crick automata and string assembling systems In the following, we would like to point out some of the similarities of WK automata and SAS, and then investigate whether these similarities help us to establish a relationship between their computational power.
Consider the WK automata M = hV; r ; Q; q0; F; d i and
the SAS S = hS; A; T; Ei. They both work with double
stranded strings, and there is a relation between the upper
and lower strings in both cases. In the case of SAS, this
relation is the identity relation, in WK automata, on the other
hand, the relation can be an arbitrary symmetric relation.
This might seem to be an important difference, but it is
not. It is known from [
We can also find similarities in the functioning of the two models. Adding building units to the generated string by a SAS from A, T , or E, corresponds to reading substrings of the input by a WK automaton with a transition from the initial state, a transition between arbitrary states, and a transition leading to and accepting state, respectively. While the states of WK automata are explicitly given, “states” of a SAS are implicit, they are “hidden” in the overlapping pairs of letters of the building units. 3.1
Known results on WK automata and SAS
As we have seen, SAS can basically add three types of
units to the generated strings, while WK automata can
have an arbitrary number of states, so it seems to be
reasonable to review results related to the number of states of
WK automata. In [
Concerning the power of SAS, already in the
introductory paper [
Comparing the power of WK automata and SAS Let us start by establishing the relationship between languages of (unrestricted) WK automata and SAS.
L (SAS)
L (W K).
Proof. According to Theorem 3.1 of [
On the other hand, L (W K) 6= L (SAS), since according
Theorem 3.6 in [
Let M = hfag; rid ; fq0; q f ; q f 0 g; q0; fq f ; q f 0 g; d i where
power of WK automata is greater than the power of SAS. Now we continue by restricting the power of WK automata by considering its variants with reduced number of states. First, we look at the relationship between stateless WK automata and SAS.
with m states by W KjQj=m and by L (W KjQj=m) the class of languages they accept.
Theorem 1. Let M be a nondeterministic stateless WK automaton. Then there exists an SAS S generating the language accepted by M with an initial marker, that is, $L(M) = L(S) where $ 62 V .
Proof. Consider M = hV; rid ; fqg; q; fqg; d i, we construct the SAS S = hS; A; T; Ei as follows.
First we show that any w 2 L(M) can be generated by S.
$ $ $ 2 A; $ 2 E.
Let su and sl denote the already read part of the upper and lower strands of the input of M. For all possible pairs of letters end( $su ) = x , if u can be read by M, $sl y v
xu there has to be a unit which can be added by S. We yv have added all possible building units for the reading of u
to S, so if a string pair can be read by M, then the v corresponding building unit can be added by S.
ment for a string to be accepted is the property that it can be read completely. In the last reading step, reading some u
, the two heads reach the end of the upper and lower v
S = V [ f$g ($ 62 V ),
$ A = f $ g,
xu T = f yv
x j for all y
2 S transitions d (q;
$ E = T [ f $ g.
u v ) = qg,
strings simultaneously. All string pairs corresponding to some unit in T have an appropriate transition in d , so S can finish the string generation by adding some unit from T , which must contain all units that can end the generation, so $
E = T [ f $ g:
Now we show that any $w 2 L(S) can be accepted by M. For all $w, we have a derivation $ $ ) $u1 $v1 ) $u1u2 $v1v2 ) : : : ) $u1u2 : : : ut , $v1v2 : : : vt xui xui yvi where $w = $u1u2 : : : ut = $v1v2 : : : vt ; yvi i t. Since we created the building units in such a way that their initial pairs of letters contain all possible combinations, even if x = end( u(i 1) ) holds, the ability y v(i 1)
2 T [ E; 1 depends only on the string pair to add unit As d (q; u i ) = q, and M is stateless, only the read string vi pair ui determines the success of the reading a word.
vi The derivation above (besides the leading $ sign) is a successful reading of the word w ui . vi u1 v1 ) u1u2 v1v2 ) : : : ) u1u2 : : : ut , v1v2 : : : vt thus w 2 L(M).
anything about the containment relationship betweem
L (SAS) and L (W KjQj=1), it still establishes some kind of
connection between the two languages classes. Moreover,
our statement is “stronger” then the similar statement in
[
Lemma 1. There is a WK automaton with two states which accepts the language L = fw j w 2 fa; bg ; jwja = 2(1 + 2i); i 0g.
Proof. The language can be accepted by the following
Let M = hfa; bg; rid ; fq0; q f g; q0; fq f g; d i with d : where in the first and last configuration M is in states q0 and q f , respectively, and in one of the two states in the intermediate configurations, uvii 2 f la ; bx ; xly j x; y 2 fa; bgg; 0 i t, correspond to the reading steps.
In any case, by reading ui = b , Di = 0, and M vi x remains in the same state, by reading ui vi = a l 1 and M remains in the same state, by reading l xy l
, Di = 2, and M changes to the other state. xy It is clear that D(i) can only increase after a reading step a was read, and can only decrease if l was read. l xy Therefore, in order for D(i) = 0, some need to be a read, together with reading twice as many . Thus, if l D(i) = 0, the already read part of the upper string contains an even number of as.
If w is accepted, then D(i) = 0 and M must be in state q f . In order for M to be in state q f , an odd number (1 + 2k; k l 0) of reading had to happen, which means that 2(1 + xy
a 2k) number of reading had to happen. Thus, M can l only accept words containing 2(1 + 2k) number of as.
Now we show that M can accept any w 2 L. First it a b needs to read and (choosing the appropriate x) l x until it reaches the end of the upper string. We are in state q0, since we have started in q0 and remained in q0 all the way. The reading head of the lower string is behind the upper head by the number of as, by 2(1 + 2k). In order l to catch up with the upper head, we need to read xy a number of times. At each such reading step, M changes its state. Since the number if as in w is 2(1 + 2k) and we read two letters from the lower string, the lower reading head reaches the end of the word after 1 + 2k, that is, after an odd number of reading steps. Therefore, M enters q f when started in q0, so w is accepted.
Corollary 1. The language L = fw j w 2 fa; bg ; jwja = (1 + 2i)k; i 0g can be accepted for any k 2 by a WK automaton similar to the above, with
Thus, L = fw j w 2 fa; bg ; jwja = 2(1 + 2i); i 0g can be accepted by a WK automaton with two states, but it cannot be accepted by stateless WK automata, as we will show in the following.
Lemma 2. If M is a stateless WK automaton, then L(M) = L(M) .
Proof. Let M = hV; rid ; fqg; q; fqg; d i be a stateless WK automaton. It is clear that L(M) L(M) . To show the ¥ converse inclusion, consider L(M) = S L(M)i, and a i=0 word w 2 L(M) . There are three possible cases. 1. If w 2 L(M)0, then w = l 2 L(M), 2. if w 2 L(M)1, then w 2 L(M), 3. if w 2 L(M)k; k 2, then w can be written as w = w1w2:::wk, where wi 2 L(M); 1 i k.
w1 q w2:::wk is a possible configuration, since w1 2 L, w1 w2:::wk so the two reading heads can be positioned after w1.
If a configuration w1:::wi 1 q wi:::wk can occur, w1:::wi 1 wi:::wk then also w1:::wi q wi+1:::wk is a possible configuraw1:::wi wi+1:::wk tion, since wi can be read (as wi 2 L). Therefore, w can wi be read in such a way that both reading heads reach the end of the tape, and since there is only one state, M accepts w.
Corollary 2. L = fw j w 2 fa; bg ; jwja = 2 + 4i; i cannot be accepted by any stateless WK automaton. 0g Proof. If L = L(M) for a stateless WK automaton M, then L = L , according to the lemma above. Let w 2 L be such, that jwja = 2. Then w2 2 L , but w2 2= L, so L 6= L , therefore L 6= L(M), which is a contradiction.
S = fa; bg, A = f T = f
x1a b b g.
in L (W KjQj=1) can be generated by SAS.
Lemma 3. L = fw j w 2 fa; bg ; jwja = 2 + 4i; i be generated by SAS. 0g can Proof. Let S = hS; A; T; Ei with
; aa aa x1b x2x3 ab a ;
; xabb y ba b , bba bb ; xbab y , ; bbb b xbba y g, , g where x; x1; x2; x3; x4; y 2 S, xaa y ,
We have chosen the assembly units of the SAS S in such a way that the difference between the length of the upper and lower string indicates how many as must be added to the upper string in order to obtain a correct number. The following four cases are possible.
1. At least 3 as are missing: D(i) = 3 + 4n, 2. at least 2 as are missing: D(i) = 2 + 4n, 3. at least 1 a is missing: D(i) = 1 + 4n, 4. at least 0 a is missing: D(i) = 0 + 4n,
where n 2 Z and we are after the ith derivation steps.
More formally we can express the above as follows. u(k)
obtained in k derivation v(k) steps. Then the congruence 2 ju(k)ja
D(k) (mod 4) must hold during the whole generating process: ju(k)ja is the number of as in the upper string. In case of ju(k)ja + 2 = 4i + j; (i 0; 1 j 4), (4i + 4) (4i + j) = (4i + 4) ju(k)ja 2 indicates the least number of as that we need to add in order for the number to be a multiple of 4. D(k) = (4 j) + 4n; n 2 Z indicates this too, so (4i + 4) ju(k)ja 2 2
ju(k)ja D(k) = (4 j) + 4n (mod 4): tion steps. After adding the unit vk+1 step, the congruence still holds, since
uk+1 in the (k + 1)th x1b a b if x2x3 ; a ; b , then ju(k+1)ja = ju(k)ja so D(k) = D(k+1), thus 2 ju(k+1)ja = 2 ju(k)ja D(k) = D(k+1) also hold.
ju(k)ja)
Using that a b (mod m) if and only if mj(a b), that is, if a b 0 (mod m), in the remaining cases we show the congruence (2 D(k) 0 (mod 4) holds.
xabb xbab xbba If ; ; , then
y y y ju(k)ja + 1 and D(k+1) = D(k) + 3 holds, so 2 ju(k+1)ja D(k+1) = 2 (ju(k)ja + 1) (D(k) + 3) = 2 ju(k)ja D(k) 4 0 (mod 4) also holds; ju(k+1)ja = xaa if
y D(k) + 2 hold, so 2 2) (D(k) + 2) = 2 also holds;
x1a if D(k) 1) (D(k) holds.
x2x3x4 1 hold, so 2
1) = 2 , then ju(k+1)ja = ju(k)ja + 2 and D(k+1) = ju(k+1)ja ju(k)ja
D(k+1) = 2 D(k) 4
(ju(k)ja + 0 (mod 4) , then ju(k+1)ja = ju(k)ja + 1 and D(k+1) = ju(k+1)ja ju(k)ja
D(k+1) = 2 (ju(k)ja + D(k) 0 (mod 4) also
by S. The assembling units of S are chosen in such a way that as and bs can follow each other in arbitrary order in the upper string, and the lower string of each unit can be arbitrary (only the length of the strings are fixed), so it is possible to add to the lower strings the appropriate letters.
Axioms are chosen as follows. We create the least number of axioms which satisfy the above mentioned congruence and provide the arbitrary letter order. The idea is to u create axioms of the form with upper strings of a v fixed length at most n 2 N, and the lower strings being at most as long as the upper, thus juj = i; i = 1 : : : n; 1 jvj juj. Then we discard those which do not satisfy the congruence, or which are not necessary for the initiation of the generation. a b This way, for i = 1 we have and as a b axioms, but we discard these, because they do not satisfy the congruence. For i = 2 we have the units aa aa ab ab ba ba bb
; ; ; ; ; ; , and a aa a ab b ba b bb aa ab ba
. We keep ; ; , so we can bb aa a b begin the generation of words starting with aa, ab, ba. We cannot generate words starting with bb, so for i = 3 we only consider the units starting with bb bba bba bba bbb bbb bbb
; ; ; ; ; . We b bb bba b bb bbb
bba bbb keep ; , so we are able to start the genbb b eration of words beginning with bb. We can start the generation with all possible combinations of letters, so no more axioms are needed.
We proceed with units in T in a similar manner: we create the least possible number of elements that satisfy the congruence, but we also allow that lower strings are longer than the upper strings. Let us suppose that the current string pair satisfies the congruence. If we would like to continue the upper string with b, then string, so we need a unit of the form we need to add an appropriate letter also to the lower x1b
. x2x3 If we would like to continue the upper string with a, then x2x3x4 have the unit we need to add two letters to the lower string, so we x1a
, or we need to add further letters to the upper string. If to the upper string – we would like to add an a, then we need to xabb add three letters, so we have the units , y xbab xbba
and ; y y – we would like to add two as, then we have the xaa unit .
y The number of letters needed to be added to the upper or lower strings are determined by the congruence.
and bs on the upper string, while the lower can only be the same length as the upper if the congruence is satisfied. In this case the generation can be finished with the ending a b units or :
a b
L (SAS) 6
L (W KjQj=1): Proof. The statement is clear by combining Lemma 3 and
4
We have started to investigate the relationship between the computational power of WK automata and string assembling systems. We know that in the general case, WK automata are stronger than SAS, so the comparison with WK automata having a restricted number of states is of interest.
First we have shown that WK automata with at least two states are strictly more powerful than stateless WK automata, then constructed a language that can be generated by SAS, but cannot be accepted by stateless WK automata. The exact relationship of the two language classes, that is the question whether there are languages accepted by stateless WK automata which cannot be generated by