On the Languages Accepted by Watson-Crick Finite Automata with Delays

Abstract

In this work, we analyze the computational power of Watson-Crick finite automata (WKFA) if some restrictions over the transition function in the model are imposed. We consider that the restrictions imposed refer to the maximum length difference between the two input strands which is called the delay. We prove that the language class accepted by WKFA with such restrictions is a proper subclass of the languages accepted by arbitrary WKFA in general. In addition, we initiate the study of the language classes characterized by WKFAs with bounded delays. We prove some of the results by means of various relationships between WKFA and sticker systems.

1. Introduction

DNA computing is a research area that draws its inspiration from the processes that take place in nature based on the functioning and structure of biomolecules, DNA, RNA, and proteins [1]. For more than 20 years, several models have been proposed in this research area, most of them universal and complete models, inspired by natural processes carried out in living cells. One of the first computational models proposed in the framework of DNA computing was the Watson-Crick finite automaton (WKFA) [2], which is a type of finite state abstract machine that takes its input tape from the DNA double strand and takes into account the complementarity relationships between symbols as it happens in nature with respect to the DNA nucleotides. That is, adenine (A) is related with thymine (T) and cytosine (C) is related with guanine (G), according to the Watson-Crick complementarity rule. The other aspect taken under consideration in this model is the ability of DNA to recombine. DNA recombination occurs at the ends of a molecule that has been previously denatured and fractionated, that is the primers of the molecule that have a length that allows to keep the molecules stable. The length of these “sticky ends” will be used in this work to characterize the language acceptation by WKFA. Several variants of the WKFA model have been proposed in recent years. We can mention, among others, the reversible WK automata [3], the unary WK automata [4], the WK Jumping Finite Automata [5], and the $5^{\prime }\to 3^{\prime }$ sensing WKFA [6], among others. In [7], a system with several WKFA and parallel communication is proposed. A survey on the WKFA model can be found in [8].

Another computation model proposed in the DNA computing framework was the sticker systems [9]. The characteristics of this model are similar to WKFA (double strands and complementarity) but within a generative approach. In this case, we have a finite set of (possibly incomplete) double strands (the axioms) and a finite set of rules (dominoes) that can enlarge the axioms by using an operation over strands called sticking. The sticking operation is based again on the DNA recombination by the double strand and the complementarity relationship. It could be considered that sticker systems and WKFA are very similar models whose main difference is that WKFA are accepting systems (at least in their basic definition), while sticker systems are generating systems.

In this work, we propose an additional restriction in order to accept or reject a double strand in the WKFA. We consider that the length of the primers of the double strand during the computation time, does not exceed a predefined positive integer value. We can impose this feature in the computations performed during the application of transitions in the WKFA, as is the case in the delayed computations of sticker systems [10], or we can define it explicitly in the transitions of the model. In this work we will propose the latter approach, and explicitly define the delays in the definition of the model transition function. Once the characteristic feature we are working with has been explicitly defined, we will proceed to study its computational power by relating it to the classical theory of formal languages. It is important to study such kinds of restrictions in the model because if we wish to see practical applications of the model such as its application in bioinformatics [11], then working with the model in a generic way implies having to solve extremely difficult problems such as working with ambiguous and non-deterministic models. By imposing these types of constraints, the model can be put into a practical context that allows the application of machine learning techniques in order to solve problems of a very diverse nature [12]. Hence, it is important: (1) To study the scope of the restrictions from a formal point of view (i.e., study the classes of languages that can be defined with the restricted model), and (2) explicitly define the restrictions imposed for better use in other application areas.

The structure of this paper is as follows: In the next section we will introduce the basic concepts about formal language theory and the WKFA and sticker systems that we will use in the rest of the work. In addition, we define the delays in sticker systems and we relate sticker systems with WKFA. In Section 3, we will introduce the WKFA model with bounded delays and we define some relationships between their language classes. In addition, we provide a sufficient condition to define bounded delays as the intial delays in the WKFA. Finally, in Section 4, we provide some results about the language classes in WKFA with only initial delays. We finish our work with some conclusions and future work on the topic addressed in this work.

2. Basic Concepts and Notation

In this section, we introduce basic concepts from formal language theory according to [13,14] and from stickers according to [1] that we will use in the sequel.

An alphabet $\Sigma$ is a finite nonempty set of elements named symbols. A string defined over $\Sigma$ is a finite ordered sequence of symbols from $\Sigma$. The infinite set of all the strings defined over $\Sigma$ is denoted by ${\Sigma }^{*}$. Given a string $x\in {\Sigma }^{*}$ we denote its length by $\left|x\right|$. The empty string is denoted by $\lambda$ and ${\Sigma }^{+}$ denotes ${\Sigma }^{*}-\left\{\lambda \right\}$. Given a string x we denote the reversal string of x by $x^r$. Given two strings $x=x_1{x}_2\cdots x_p$ and $y=y_1{y}_2\cdots y_m$, we denote the product (concatenation) of x by y as the string $xy=x_1{x}_2\cdots x_p{y}_1{y}_2\cdots y_m$. A language L defined over $\Sigma$ is a set of strings over $\Sigma$.

A grammar is a construct $G=(N,\Sigma ,P,S)$ where N and $\Sigma$ are the alphabets of auxiliary and terminal symbols with $N\cap \Sigma =Ø$, $S\in N$ is the axiom of the grammar and P is a finite set of productions in the form $\alpha \to \beta$, where $\alpha \in {(N\cup \Sigma )}^{*}N{(N\cup \Sigma )}^{*}$ and $\beta \in {(N\cup \Sigma )}^{*}$. The language of the grammar is denoted by $L\left(G\right)$ and it is the set of terminal strings that can be obtained from S by applying symbol substitutions according to P. Formally, $w_1\underset{G}{\Rightarrow }{w}_2$ if $w_1=u\alpha v$, $w_2=u\beta v$, and $\alpha \to \beta \in P$. We denote the reflexive and transitive closure of $\underset{G}{\Rightarrow }$ by $\stackrel{*}{\underset{G}{\Rightarrow }}$. The language generated by G is defined by the set $L\left(G\right)=\{w\in {\Sigma }^{*}:S\stackrel{*}{\underset{G}{\Rightarrow }}w\}$.

We say that a grammar $G=(N,\Sigma ,P,S)$ is right (left) linear (regular) if every production in P is in the form $A\to uB$ ($A\to Bu$) or $A\to w$ with $A,B\in N$ and $u,w\in {\Sigma }^{*}$. The class of languages generated by right (left) linear grammars is the class of regular languages and is denoted by $\mathcal{REG}$. We say that a grammar $G=(N,\Sigma ,P,S)$ is linear if every production in P is in the form $A\to uBv$ or $A\to w$ with $A,B\in N$ and $u,v,w\in {\Sigma }^{*}$. The class of languages generated by linear grammars is denoted by $\mathcal{LIN}$. A well-known result from formal language theory is the inclusion $\mathcal{REG}\subset \mathcal{LIN}$.

A deterministic finite automata (DFA) is an abstract machine $A=(Q,\Sigma ,\delta ,q_0,F)$, where Q is a finite set of states, $\Sigma$ is an input alphabet, $\delta :Q\times \Sigma \to Q$ is a transition function, $q_0\in Q$ is an initial state, and $F\subseteq Q$ is a set of final states. The extension of the transition function over strings $\widehat{\delta }:Q\times {\Sigma }^{*}\to Q$ is defined as $\widehat{\delta }(q,\lambda )=q$, and $\widehat{\delta }(q,xa)=\delta (\widehat{\delta }(q,x),a)$ for every $x\in {\Sigma }^{*}$, and $a\in \Sigma$. In the following, we will not distinguish between $\delta$ and $\widehat{\delta }$, and its meaning will depend on the function arguments. The language accepted by a DFA A is the set $L\left(A\right)=\{x\in {\Sigma }^{*}:\delta (q_0,x)\in F\}$. A classical result from formal language theory is that the class of languages accepted by deterministic finite automata is $\mathcal{REG}$. For the case of non-deterministic finite automata, the transition function is defined as $\delta :Q\times \Sigma \to \mathcal{P}\left(Q\right)$, where $\mathcal{P}\left(Q\right)$ is the power set of Q. It is a classical result from formal language theory that the set of languages accepted by non-deterministic finite automata is again $\mathcal{REG}$.

Regular languages can be defined by regular expressions. They are a language specification based on definition rules that consider letters of the alphabet, the union, product and closure operators, and the use of parentheses to reorder the priority of operators.

A homomorphism h is defined as a mapping $h:\Sigma \to {\Gamma }^{*}$ where $\Sigma$ and $\Gamma$ are alphabets. We can extend the definition of homomorphisms over strings as $h\left(\lambda \right)=\lambda$ and $h\left(ax\right)=h\left(a\right)h\left(x\right)$ with $a\in \Sigma$ and $x\in {\Sigma }^{*}$. The homomorphism over a language $L\subseteq {\Sigma }^{*}$ is defined as $h\left(L\right)=\left\{h\right(x):x\in L\}$.

Given an alphabet $\Sigma =\{a_1,\cdots ,a_n\}$, we use the symmetric (and injective) relation of complementarity $\rho \subseteq \Sigma \times \Sigma$. For any string $x\in {\Sigma }^{*}$, we denote by $\rho \left(x\right)$ the string obtained by substituting the symbol a in x by the symbol b such that $(a,b)\in \rho$ (remember that $\rho$ is injective) with $\rho \left(\lambda \right)=\lambda$.

Given an alphabet V, a sticker over V is the pair $(x,y)$ such that $x=x_{1}v{x}_2$, $y=y_{1}w{y}_2$ with $x,y\in {\Sigma }^{*}$ and $\rho \left(v\right)=w$. The sticker $(x,y)$ will be denoted by $\left(\begin{array}{c}x\\ y\end{array}\right)$. A sticker $\left(\begin{array}{c}x\\ y\end{array}\right)$ will be a complete and complementary molecule if $\left|x\right|=\left|y\right|$ and $\rho \left(x\right)=y$. A complementary and complete molecule $\left(\begin{array}{c}x\\ y\end{array}\right)$ will be denoted as $\left[\begin{array}{c}x\\ y\end{array}\right]$. The set of all complete and complementary molecules over V will be called the Watson-Crick domain and denoted by $W{K}_{\rho }\left(V\right)$.

We define the following sets, where $\rho$ denotes the symmetric relation between the symbols in V:

$L_{\rho }\left(V\right)=(\left(\begin{array}{c}\lambda \\ V^{*}\end{array}\right)\cup \left(\begin{array}{c}{V}^{*}\\ \lambda \end{array}\right)){\left[\begin{array}{c}V\\ V\end{array}\right]}_{\rho }^{*}$,

$R_{\rho }\left(V\right)={\left[\begin{array}{c}V\\ V\end{array}\right]}_{\rho }^{*}(\left(\begin{array}{c}\lambda \\ V^{*}\end{array}\right)\cup \left(\begin{array}{c}{V}^{*}\\ \lambda \end{array}\right))$,

$L{R}_{\rho }\left(V\right)=(\left(\begin{array}{c}\lambda \\ V^{*}\end{array}\right)\cup \left(\begin{array}{c}{V}^{*}\\ \lambda \end{array}\right)){\left[\begin{array}{c}V\\ V\end{array}\right]}_{\rho }^{+}(\left(\begin{array}{c}\lambda \\ V^{*}\end{array}\right)\cup \left(\begin{array}{c}{V}^{*}\\ \lambda \end{array}\right))$.

In addition, we can consider the set $W_{\rho }\left(V\right)=L_{\rho }\left(V\right)\cup R_{\rho }\left(V\right)\cup L{R}_{\rho }\left(V\right)$. Observe that $W{K}_{\rho }\left(V\right)$ is included in each set from $L_{\rho }\left(V\right),R_{\rho }\left(V\right)$ and $L{R}_{\rho }\left(V\right)$.

Kari et al. [9] defined the sticking operation $\mu$ which can be considered as a product operation over stickers. Basically, given two stickers x and y, the operation $\mu (x,y)$ returns a new sticker by taking into account the complementarity relation $\rho$ between the upper string in x and the lower string in y and vice versa.

Sticker systems were defined by Freund et al. in [15] and by Kari et al. in [9] as a generative model to apply the sticking operation $\mu$ (a product-like operation over stickers) to obtain languages. At the same time, Păun and Rozenberg [10] introduced some aspects which will be highly related to the present work such as the (bounded) delayed languages defined by sticker systems. A sticker system is defined by the tuple $\gamma =(V,\rho ,A,D)$, where V is an alphabet, $\rho \subseteq V\times V$ is a symmetric (and injective) relation, D is a finite subset of $W_{\rho }\left(V\right)\times W_{\rho }\left(V\right)$ where its elements are called dominoes, and A is a finite subset of $L{R}_{\rho }\left(V\right)$ which are the axioms of the system. The derivation relation ⇒ between stickers, according to a sticker system $\gamma$, can be defined as follows:

$x\Rightarrow y$ iff $y=\mu (u_1,\mu (x,u_2))$ such that $(u_1,u_2)\in D$.

Given that ⇒ is a relation between stickers subjected to a sticker system $\gamma$, we will denote the reflexive and transitive closure of ⇒ by $\stackrel{*}{\Rightarrow }$. Now, we can define the language of complete and complementary molecules generated by the sticker system $\gamma =(V,\rho ,A,D)$ with no restrictions as follows:

$L{M}_n\left(\gamma \right)=\{w\in W{K}_{\rho }\left(V\right):x\stackrel{*}{\Rightarrow }w,x\in A\}$.

In addition, the language generated by $\gamma$ is defined as:

$L_n\left(\gamma \right)=\{x\in V^{*}:\left[\begin{array}{c}x\\ \rho \left(x\right)\end{array}\right]\in L{M}_n\left(\gamma \right)\}$.

The family of languages generated by arbitrary sticker systems is denoted by $\mathcal{ASL}\left(n\right)$.

The maximal length of an overhang in a sticker $z=\left(\begin{array}{c}x\\ y\end{array}\right)$ is called the delay of z. Observe that the delay of a sticker z is the maximal length of the right or left overhang located in the upper or lower strand. Formally, if $z=u\left[\begin{array}{c}v\\ \rho \left(v\right)\end{array}\right]w$, with $u,w\in \left(\begin{array}{c}\lambda \\ V^{*}\end{array}\right)\cup \left(\begin{array}{c}{V}^{*}\\ \lambda \end{array}\right)$, then the delay of z equals to the maximum value between $\left|u\right|$ and $\left|w\right|$, where $\left|u\right|=|u^{\prime }|$ if $u=\left(\begin{array}{c}{u}^{\prime }\\ \lambda \end{array}\right)$ or $u=\left(\begin{array}{c}\lambda \\ u^{\prime }\end{array}\right)$, and $\left|w\right|=|w^{\prime }|$ if $w=\left(\begin{array}{c}{w}^{\prime }\\ \lambda \end{array}\right)$ or $w=\left(\begin{array}{c}\lambda \\ w^{\prime }\end{array}\right)$. The delay associated to a derivation in a sticker system is the maximal delay of the stickers that are produced during that derivation. For any sticker system $\gamma$, the language of strings generated by $\gamma$ with a delay d is denoted by $L_d\left(\gamma \right)$. A sticker system $\gamma$ is said to have a bounded delay if there is $d>1$ such that $L_d\left(\gamma \right)=L_n\left(\gamma \right)$· The family of languages generated by arbitrary sticker systems with a bounded delay is denoted by $\mathcal{ASL}\left(b\right)$.

Watson-Crick finite automata (WKFA) were defined first by Freund et al. [2] as an acceptance model to deal with stickers. It can be defined by the tuple $M=(V,\rho ,Q,$ $s_0,F,\delta )$, where Q and V are disjoint alphabets (states and symbols), $\rho \subseteq V\times V$ is a symmetric (and injective) relation of complementarity, $s_0\in Q$ is the initial state, $F\subseteq Q$ is a set of final states, and $\delta :Q\times \left(\begin{array}{c}{V}^{*}\\ V^{*}\end{array}\right)\to \mathcal{P}\left(Q\right)$. A transition step in an arbitrary WK finite automaton M is denoted by $\underset{M}{\mapsto }$. So, $\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)q\left(\begin{array}{c}{x}_2{x}_3\\ y_2{y}_3\end{array}\right)\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1{x}_2\\ y_1{y}_2\end{array}\right)p\left(\begin{array}{c}{x}_3\\ y_3\end{array}\right)$ iff $p\in \delta (q,\left(\begin{array}{c}{x}_2\\ y_2\end{array}\right))$, with $x_1,x_2,x_3,y_1,y_2,y_3\in V^{*}$. The transitive and reflexive closure of $\underset{M}{\mapsto }$ is denoted by $\stackrel{*}{\underset{M}{\mapsto }}$. We can use a normal form such that for every transition $q\in \delta (q,\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right))$ then $|x_1{x}_2|=1$. This normal form defines the so-called 1-$limited$ WK finite automata and they were proved to be equivalent to arbitrary ones [2].

The language of complete and complementary molecules accepted by M will be defined by the set $L_m\left(M\right)=\{\left[\begin{array}{c}x\\ y\end{array}\right]:s_0\left[\begin{array}{c}x\\ y\end{array}\right]\stackrel{*}{\underset{M}{\mapsto }}\left[\begin{array}{c}x\\ y\end{array}\right]q,$ with $q\in F$ and $x,y\in V^{*}\}$, while the upper strand language accepted by M will be defined as:

$$L_u\left(M\right)=\{x\in V^{*}:s_0\left[\begin{array}{c}x\\ y\end{array}\right]\stackrel{*}{\underset{M}{\mapsto }}\left[\begin{array}{c}x\\ y\end{array}\right]q,q\in F\wedge x,y\in V^{*}\}.$$

The class of languages accepted by arbitrary WKFA in the upper strand is denoted by $\mathcal{AWK}$.

We can use a normal form such that for every transition $q\in \delta (q,\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right))$ then $x_1=\lambda$ or $x_2=\lambda$. This normal form defines the so called simple WKFA and they were proved to be equivalent to arbitrary ones [2].

Now, we will relate the languages in $\mathcal{AWK}$ with the languages generated by sticker systems through the following result.

Theorem 1.

Let $M=(V,\rho ,Q,s_0,F,\delta )$ be a simple WKFA. Then there exists a sticker system $\gamma =(V^{\prime },{\rho }^{\prime },A,D)$, a morphism h and a regular language R which satisfies $h(L_n\left(\gamma \right)\cap R)=L_u\left(M\right)$.

Proof. 

Let us take $M=(V,\rho ,Q,s_0,F,\delta )$ to be a simple WKFA with $Q=\{s_0,q_1,\dots ,q_n\}$ and $V=\{a_1,\cdots ,a_n\}$. Observe that this restriction over WKFA does not affect the computational capacity of the model, given that simple is a normal form for WKFA. We can define the sticker system $\gamma =(V^{\prime },{\rho }^{\prime },A,D)$ where the elements of $\gamma$ are defined as follows:

• $V^{\prime }=V\cup Q\cup \{q_f,\#\}$, where $q_f,\#\notin Q\cup V$;
• ${\rho }^{\prime }$ is defined as:

  $${\rho }^{\prime }\left(a\right)=\left\{\begin{array}{cc}a\hfill & \mathrm{if}a\in Q\cup \{q_f,\#\}\hfill \\ \rho \left(a\right)\hfill & \mathrm{if}a\in V\hfill \\ ;\hfill \end{array}\right.$$
• The set of axioms A is defined through the following rules:
  • $\left(\begin{array}{c}\#\\ s_0\#\end{array}\right)$
    This axiom places the initial state of M as the first state in the sequence defined to accept any string.
  • $\left(\begin{array}{c}{s}_0\#\\ q{s}_0\#\end{array}\right)$ where $q\in \delta (s_0,\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right))$
    An axiom is created for every transition from the initial state of the WKFA, $s_0$. The overhang end on the left lower strand of the axiom corresponds to the state of the WKFA that is reached from the initial state with a $\lambda$-movement.
  • $\left(\begin{array}{c}{s}_0\#\\ q_f{s}_0\#\end{array}\right)$ if $s_0\in F$
    If the initial state in the WKFA is final too, then this axiom is inserted. That is, the additional state $q_f$ is produced from the initial state without any input symbol.
• The set D is defined by the pairs according to the following rules:
  • $(\left(\begin{array}{c}q\\ p\end{array}\right),\left(\begin{array}{c}x\\ y\end{array}\right))$ where $p\in \delta (q,\left(\begin{array}{c}x\\ y\end{array}\right))$ and $x=\lambda$ or $y=\lambda$.
    That means that, in M, it is possible to transit from q to p with the pair $\left(\begin{array}{c}x\\ y\end{array}\right)$.
  • $(\left(\begin{array}{c}\#q\\ q_f\#\end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right))$ where $q\in F$.
    For each final state $q_i\in F$ of the WKFA, these stickers mark the end of the state sequence in the WKFA to accept the input.
  • $(\left(\begin{array}{c}{q}_f\\ \lambda \end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right))$
    This rule is added to avoid overhang ends in the left side of the sticker system. When this rule is added there is no way to add another one according to the automata transitions.

Now, observe the following accepting computation in M:

$$s_0\left[\begin{array}{c}x\\ y\end{array}\right]\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)q_{i_1}\left(\begin{array}{c}{x}_2\dots x_n\\ y_2\dots y_n\end{array}\right)\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1{x}_2\\ y_1{y}_2\end{array}\right)q_{i_2}\left(\begin{array}{c}{x}_3\dots x_n\\ y_3\dots y_n\end{array}\right)\underset{M}{\mapsto }\cdots \underset{M}{\mapsto }\left(\begin{array}{c}{x}_1{x}_2\dots x_n\\ y_1{y}_2\dots y_n\end{array}\right)q_{i_n},$$

where $q_{in}\in F$. The following derivation is hold in $\gamma$:

$$\left(\begin{array}{c}\#\\ s_0\#\end{array}\right)\underset{\gamma }{\Rightarrow }\left(\begin{array}{c}{s}_0\#x_1\\ q_{i_1}{s}_0\#y_1\end{array}\right)\underset{\gamma }{\Rightarrow }\left(\begin{array}{c}{q}_{i_1}{s}_0\#x_1{x}_2\\ q_{i_2}{q}_{i_1}{s}_0\#y_1{y}_2\end{array}\right)\underset{\gamma }{\Rightarrow }\cdots \underset{\gamma }{\Rightarrow }\left(\begin{array}{c}{q}_{i_{n-1}}\dots q_{i_1}{s}_0\#x_1\dots x_n\\ q_{i_n}{q}_{i_{n-1}}\dots q_{i_1}{s}_0\#y_1\dots y_n\end{array}\right)\underset{\gamma }{\Rightarrow }\cdots$$

$$\cdots \underset{\gamma }{\Rightarrow }\left(\begin{array}{c}\#q_{i_n}{q}_{i_{n-1}}\dots q_{i_1}{s}_0\#x_1\dots x_n\\ q_f\#q_{i_n}{q}_{i_{n-1}}\dots q_{i_1}{s}_0\#y_1\dots y_n\end{array}\right)\underset{\gamma }{\Rightarrow }\left(\begin{array}{c}{q}_f\#q_{i_n}{q}_{i_{n-1}}\dots q_{i_1}{s}_0\#x_1\dots x_n\\ q_f\#q_{i_n}{q}_{i_{n-1}}\dots q_{i_1}{s}_0\#y_1\dots y_n\end{array}\right),$$

and it can easily be shown that $x_1\dots x_n\in L_u\left(M\right)$ iff $q_f\#q_{i_n}{q}_{i_{n-1}}\dots q_{i_1}{s}_0\#x_1\dots x_n\in L_n\left(\gamma \right)$.

A regular set R is defined by the regular expression:

$$q_f\#{(s_0+q_1+\cdots +q_n)}^{*}\#{(a_1+a_2+\cdots +a_n)}^{*}.$$

The above regular expression guarantees that only strings containing a single symbol $q_f$ can be produced and, therefore, in the sticker system, the molecules obtained correspond only to those that have reached a final state in the WKFA. On the other hand, note that without the set R acting as a control set, the sticker system could generate molecules that would not be recognized in the automaton. In other words, nothing prevents the sticker system from continuing to add stickers that could complete new molecules once the molecule accepted by the automaton has been generated.

Finally, we can define the morphism $h:V^{\prime }\to V$ as follows:

$$h\left(a\right)=\left\{\begin{array}{cc}a\hfill & \mathrm{if}a\in V\hfill \\ \lambda \hfill & \mathrm{if}a\notin V.\hfill \end{array}\right.$$

Hence, $q_f\#q_{i_n}{q}_{i_{n-1}}\dots q_{i_1}{s}_0\#x_1\dots x_n\in L_n\left(\gamma \right)\cap R$, $h(q_f\#q_{i_n}{q}_{i_{n-1}}\dots q_{i_1}{s}_0\#x_1\dots x_n)=x_1\dots x_n$, and the theorem holds.

It can be observed that the sequence of states needed to accept any string x in M is defined by the reverse of the sequence of states between the # marks in the stickers obtained in $\gamma$. □

Example 1.

Let us take the simple WKFA defined by the transition diagram in Figure 1.

From the previous WKFA, we build a sticker system, such that A and D are defined as follows:

$A=\{\left(\begin{array}{c}\#\\ q_0\#\end{array}\right)\}$.

$D=\{(\left(\begin{array}{c}{q}_0\\ q_1\end{array}\right),\left(\begin{array}{c}\lambda \\ a\end{array}\right)),(\left(\begin{array}{c}{q}_1\\ q_4\end{array}\right),\left(\begin{array}{c}a\\ \lambda \end{array}\right)),(\left(\begin{array}{c}{q}_1\\ q_2\end{array}\right),\left(\begin{array}{c}ab\\ \lambda \end{array}\right)),(\left(\begin{array}{c}{q}_2\\ q_1\end{array}\right),\left(\begin{array}{c}\lambda \\ ba\end{array}\right)),(\left(\begin{array}{c}{q}_2\\ q_3\end{array}\right),\left(\begin{array}{c}\lambda \\ bb\end{array}\right)),$

$(\left(\begin{array}{c}{q}_2\\ q_5\end{array}\right),\left(\begin{array}{c}\lambda \\ b\end{array}\right)),(\left(\begin{array}{c}{q}_3\\ q_2\end{array}\right),\left(\begin{array}{c}\lambda \\ bb\end{array}\right)),(\left(\begin{array}{c}\#q_4\\ q_f\#\end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right)),(\left(\begin{array}{c}\#q_5\\ q_f\#\end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right)),(\left(\begin{array}{c}{q}_f\\ \lambda \end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right))\}.$

The regular expressión defined to control the stickers generation is defined as follows:

$$q_f\#{(q_0+q_1+q_2+q_3+q_4+q_5)}^{*}\#{(a+b)}^{*}.$$

3. Accepting Languages with Bounded Delays in WKFA

In this section, we will introduce the delays during a WKFA computation in a way similar to sticker systems [10].

Let us suppose that we consider the following computation in a WKFA $M=(V,\rho ,Q,s_0,$$F,\delta )$ with $x=x_1{x}_2\dots x_n$ and $y=y_1{y}_2\dots y_n$:

$$q_0\left[\begin{array}{c}x\\ y\end{array}\right]\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1\\ y_1\end{array}\right)q_{i_1}\left(\begin{array}{c}{x}_2\dots x_n\\ y_2\dots y_n\end{array}\right)\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1{x}_2\\ y_1{y}_2\end{array}\right)q_{i_2}\left(\begin{array}{c}{x}_3\dots x_n\\ y_3\dots y_n\end{array}\right)\underset{M}{\mapsto }\cdots \underset{M}{\mapsto }\left(\begin{array}{c}{x}_1{x}_2\dots x_n\\ y_1{y}_2\dots y_n\end{array}\right)q_{i_n},$$

where $x_j,y_j\in V^{*}$, $q_{i_j}\in Q$, if $0\le |x_1{x}_2\dots x_j|-|y_1{y}_2\dots y_j|\le d$, for $1\le j\le n$, and $q_{i_n}\in F$ then we say that M accepts $\left[\begin{array}{c}x\\ y\end{array}\right]$ with an upper bounded delay d. If $0\le |y_1{y}_2\dots y_j|-|x_1{x}_2\dots x_j|\le d$, for $1\le j\le n$ we say that M accepts $\left[\begin{array}{c}x\\ y\end{array}\right]$ with a lower bounded delay d. If $\left|\right|x_1{x}_2\dots x_j|-|y_1{y}_2\dots y_j\left|\right|\le d$, for $1\le j\le n$ we say that M accepts $\left[\begin{array}{c}x\\ y\end{array}\right]$ with an arbitrary bounded delay d. The language accepted by M with upper (lower, arbitrary) bounded delay d in the upper strand is denoted by $L_{u,updel}(M,d)$ ($L_{u,lowdel}(M,d),L_{u,del}(M,d)$). The class of languages accepted by arbitrary WKFA in the upper strand with upper (lower, arbitrary) bounded delay equals to d will be denoted by ${\mathcal{AWK}}_{updel}\left(d\right)$ (${\mathcal{AWK}}_{lowdel}\left(d\right)$, ${\mathcal{AWK}}_{del}\left(d\right)$).

The definition of delays in the computation of the automaton is a constraint that reduces the computational power of the model. This can be formalized by the following result.

Lemma 1.

For every integer value $d>0$, ${\mathcal{AWK}}_{updel}\left(d\right)⊊\mathcal{AWK}$.

Proof. 

Let us consider the language $L=\{wcw:w\in {\{a,b\}}^{*}\}$. This language belongs to $\mathcal{AWK}$ given that it can be accepted by the following WKFA.

$\delta (q_0,\left(\begin{array}{c}a\\ \lambda \end{array}\right))=\left\{q_0\right\}$	$\delta (q_0,\left(\begin{array}{c}b\\ \lambda \end{array}\right))=\left\{q_0\right\}$	$\delta (q_0,\left(\begin{array}{c}c\\ \lambda \end{array}\right))=\left\{q_1\right\}$
$\delta (q_1,\left(\begin{array}{c}a\\ a\end{array}\right))=\left\{q_1\right\}$	$\delta (q_1,\left(\begin{array}{c}b\\ b\end{array}\right))=\left\{q_1\right\}$	$\delta (q_1,\left(\begin{array}{c}\lambda \\ c\end{array}\right))=\left\{q_2\right\}$
$\delta (q_2,\left(\begin{array}{c}\lambda \\ a\end{array}\right))=\left\{q_2\right\}$	$\delta (q_2,\left(\begin{array}{c}\lambda \\ b\end{array}\right))=\left\{q_2\right\},$

with $F=\left\{q_2\right\}$ and $\rho =\left\{\right(a,a),(b,b),(c,c\left)\right\}$. Observe that the automaton reads first in the upper strand the string w until it reaches the symbol c always being in the state $q_0$. Once the symbol c has been read, the automaton changes its state and it then starts to match the string after the symbol c with the string starting on the lower strand. If the symbol c is found in the lower strand then it proceeds to read the rest of the input string in the lower strand.

It is easy to see that for any delay value $d>0$, a string $wcw$ with $\left|w\right|>d$ will not be parsed with a delay less than or equal to d given that the automaton needs to read the string w first before arriving to the symbol c. In such a case, the automaton produces a delay greater than d given that $\left|w\right|>d$. □

Now, we are going to consider the relationships between the upper, lower, and arbitrary delays. In this case, we will work with arbitrary WKFA and the identity as the relation $\rho$ defined in the automata. Observe that this does not detract from the generality of our results since the complementarity relationship can be reduced to the identity as shown in [16].

Lemma 2.

For every integer value $d>0$, ${\mathcal{AWK}}_{lowdel}\left(d\right)={\mathcal{AWK}}_{updel}\left(d\right)$.

Proof. 

Let $M_1=(V,\rho ,Q,s_0,F,{\delta }_1)$ be an arbitrary WKFA with $\rho$ being the identity relation, and L be the language accepted by $M_1$ with a bounded upper (lower) delay d. Then, from $M_1$ we can obtain the WKFA $M_2=(V,\rho ,Q,s_0,F,{\delta }_2)$ where $p\in {\delta }_2(q,\left(\begin{array}{c}y\\ x\end{array}\right))$ if $p\in {\delta }_1(q,\left(\begin{array}{c}x\\ y\end{array}\right))$. It is easy to see that if w is accepted by $M_1$ with an upper (lower) delay d, then w is accepted by $M_2$ by a lower (upper) delay given that the relation $\rho$ is the identity and the transitions in $M_2$ swap the contents of the upper and lower strands. □

Lemma 3.

${\mathcal{AWK}}_{updel}\left(0\right)=\mathcal{REG}$.

Proof. 

Let $M=(V,\rho ,Q,s_0,F,\delta )$ be an arbitrary WKFA and $L=L_{u,updel}(M,0)$. For every $x\in L_{u,updel}(M,0)$ there exists a computation in M as follows:

$$q_0\left[\begin{array}{c}x\\ x\end{array}\right]\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1\\ x_1\end{array}\right)q_{i_1}\left(\begin{array}{c}{x}_2\dots x_n\\ x_2\dots x_n\end{array}\right)\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1{x}_2\\ x_1{x}_2\end{array}\right)q_{i_2}\left(\begin{array}{c}{x}_3\dots x_n\\ x_3\dots x_n\end{array}\right)\underset{M}{\mapsto }\cdots \underset{M}{\mapsto }\left(\begin{array}{c}{x}_1{x}_2\dots x_n\\ x_1{x}_2\dots x_n\end{array}\right)q_{i_n}.$$

Observe that $\rho$ is the identity relation and, we can assume that $x_i\in V$, $1\le i\le n$. Then, from M we can obtain a non-deterministic finite automata $A=(Q,V,s_0,f,F)$, such that $p\in f(q,a)$ iff $p\in \delta (q,\left(\begin{array}{c}a\\ a\end{array}\right))$.

It is easy to see that $x\in L\left(A\right)=L$. Hence, ${\mathcal{AWK}}_{updel}\left(0\right)\subseteq \mathcal{REG}$. In order to see that $\mathcal{REG}\subseteq {\mathcal{AWK}}_{updel}\left(0\right)$, we take any arbitrary deterministic finite automata $A=(Q,\Sigma ,f,q_0,F)$, and we obtain the WKFA $M=(\Sigma ,\rho ,Q,q_0,F,\delta )$ where $\rho$ is the identity relation, and $p\in \delta (q,\left(\begin{array}{c}a\\ a\end{array}\right))$ iff $f(q,a)=p$. Again, it is easy to see that $x\in L_{u,updel}(M,0)$ iff $x\in L\left(A\right)$. Then, $\mathcal{REG}\subseteq {\mathcal{AWK}}_{updel}\left(0\right)$, and the lemma holds. □

A Sufficient Condition for Bounded Delays in WKFA

We have seen how delays during computation, regardless of whether they occur on the upper or lower strand, can be variable. That is, given a delay value d, the computation can produce that delay incrementally (i.e., starting with a delay less than d and then increasing it to the required value). In this section, we will propose a way to produce the required delay instantaneously. Informally, the approach we are going to propose requires producing the desired delay in the first movement of the computation and, subsequently, maintaining it until a point in time where it is completely reduced. This, without being a normal form, can be interesting when dealing with WKFA inductive inference as proposed in [12].

We say that M accepts x in the upper strand with an initial delay k iff M applies the following transition sequences to accept $x=x_1{x}_2\cdots x_l$. Remember that we can use the identity relation without loss of generality.

• First movement (initial delay)

  $$s_0\left(\begin{array}{c}{x}_1{x}_2\cdots x_l\\ x\end{array}\right)\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1{x}_2\cdots x_k\\ \lambda \end{array}\right)s_1\left(\begin{array}{c}{x}_{k+1}\cdots x_l\\ x\end{array}\right).$$
• Delay propagation$\forall i\ge 1$ such that $(i+1)·k<l$

  $$\left(\begin{array}{c}{x}_1\cdots x_{i·k}\\ \rho (x_1\cdots x_{(i-1)·k})\end{array}\right)p\left(\begin{array}{c}{x}_{i·k+1}\cdots x_l\\ \rho (x_{(i-1)·k+1}\cdots x_l)\end{array}\right)\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1\cdots x_{(i+1)·k}\\ \rho (x_1\cdots x_{i·k})\end{array}\right)q\left(\begin{array}{c}{x}_{(i+1)·k+1}\cdots x_l\\ \rho (x_{i·k+1}\cdots x_l)\end{array}\right).$$
• Final movement$\forall m\ge 0$ such that $l-m+1<k$

  $$\left(\begin{array}{c}{x}_1\cdots x_m\\ \rho (x_1\cdots x_{m-k})\end{array}\right)p\left(\begin{array}{c}{x}_{m+1}\cdots x_l\\ \rho (x_{m-k+1}\cdots x_l)\end{array}\right)\underset{M}{\mapsto }\left(\begin{array}{c}{x}_1\cdots x_l\\ \rho (x_1\cdots x_l)\end{array}\right)q.$$

Therefore, M accepts x in the upper strand by first processing k symbols of the upper strand, and then processing alternately k symbols of the lower and upper strand. When there are less than k symbols left in the upper strand, all the remaining symbols are processed. Figure 2 shows graphically how the stickers are organized as they are processed with initial delays.

Observe that the movements of the automata can adapted to be simple: The movement $q\in \delta (p,\left(\begin{array}{c}x\\ y\end{array}\right))$, with $\left|x\right|=\left|y\right|=k$ can be replaced by the following two movements $q^{\prime }\in \delta (p,\left(\begin{array}{c}\lambda \\ y\end{array}\right))$ and $q\in \delta (q^{\prime },\left(\begin{array}{c}x\\ \lambda \end{array}\right))$. Hence, the scheme to process the stickers in a simple WKFA with initial delays is shown in Figure 3.

Observe that according to the previous figure, in the WKFA the delay always equals to k given that first it is produced in the upper strand and then the lower strand is completed. In the following we will work with simple WKFA with only initial delays.

4. Languages Accepted by WKFA with Only Initial Delays

Let M be a simple WKFA with only initial delay movements, and let d be the delay at every computation step in M. If a sticker system $\gamma$ is built from M as established in Theorem 1, then $L_n\left(\gamma \right)\in \mathcal{ASL}\left(b\right)$. This is due to the fact that, according to the definition of a WKFA with an initial delay d, the length of the delay that may appear in any of the two strands when processing a sequence cannot be longer than d. Therefore, in the sticker system, during its construction, the overhang end in the right side cannot be longer than d, and, in the left side, longer than one.

Example 2.

Let us take the simple WKFA with initial delays defined by the transition diagram of Figure 4. Observe that the bounded delay in this case equals to 2.

Observe that the bounded delay in this case equals to 2 and $L_u\left(M\right)=L_{u,updel}(M,2)$.

From the previous WKFA, we build a sticker system γ, such that A and D are defined as follows:

$A=\{\left(\begin{array}{c}\#\\ q_0\#\end{array}\right)\}.$

$D=\{(\left(\begin{array}{c}{q}_0\\ q_1\end{array}\right),\left(\begin{array}{c}aa\\ \lambda \end{array}\right)),(\left(\begin{array}{c}{q}_1\\ q_2\end{array}\right),\left(\begin{array}{c}\lambda \\ aa\end{array}\right)),(\left(\begin{array}{c}{q}_2\\ q_3\end{array}\right),\left(\begin{array}{c}bb\\ \lambda \end{array}\right)),(\left(\begin{array}{c}{q}_3\\ q_0\end{array}\right),\left(\begin{array}{c}\lambda \\ bb\end{array}\right)),(\left(\begin{array}{c}{q}_3\\ q_4\end{array}\right),\left(\begin{array}{c}\lambda \\ bb\end{array}\right)),$

$(\left(\begin{array}{c}{q}_4\\ q_5\end{array}\right),\left(\begin{array}{c}b\\ \lambda \end{array}\right)),(\left(\begin{array}{c}{q}_5\\ q_6\end{array}\right),\left(\begin{array}{c}\lambda \\ b\end{array}\right))(\left(\begin{array}{c}\#q_4\\ q_f\#\end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right)),(\left(\begin{array}{c}\#q_6\\ q_f\#\end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right)),(\left(\begin{array}{c}{q}_f\\ \lambda \end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right))\}.$

In this case, $L_u\left(M\right)=L_n\left(\gamma \right)$ which can be defined by the regular expression:

$$\left(aabb\right){\left(aabb\right)}^{*}(b+\lambda ),$$

given that, once a molecule is completed in γ, after having reached the final state $q_4$, there is no possibility of lengthening the molecule and completing a larger one, as the upper and lower strand would not be complementary.

Thus, the definition of a regular expression for derivative control, as in the proof of Theorem 1, is completely unnecessary in the case of initial delays. This aspect will be formalized by the following theorem.

Theorem 2.

Let $M=(V,\rho ,Q,s_0,F,\delta )$ be a simple WKFA with only initial delays. Then there exists a sticker system $\gamma =(V^{\prime },{\rho }^{\prime },A,D)$ and a morphism h which satisfies $h\left(L_n\left(\gamma \right)\right)=L_u\left(M\right)$.

Proof. 

Let $M=(V,\rho ,Q,s_0,F,\delta )$ be a simple WKFA with only initial delays. Then we define a sticker system $\gamma$ and a morphism h as in the proof of Theorem 1. Observe that in this case, there is no way to keep on derivating a sticker once the pairs $(\left(\begin{array}{c}\#q\\ q_f\#\end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right))$ and $(\left(\begin{array}{c}{q}_f\\ \lambda \end{array}\right),\left(\begin{array}{c}\lambda \\ \lambda \end{array}\right))$ have been applied given that the rest of elements in D do not preserve the complementarity since the relation $\rho$ is the identity. □

It is known that $\mathcal{ASL}\left(b\right)\subseteq \mathcal{LIN}$ (Theorem 4.3 in [10]). That theorem is proven by building a linear grammar $G=(N,T,S,P)$ from a sticker system $\gamma =(V,\rho ,A,D)$. In the grammar G, the molecules are obtained by a derivation from the ends of the molecule until reaching its central part in a reverse process to the one that happens in the sticker system. We can take advantage of this result together with the results we have proven before to characterize the language accepted by the WKFA with only initial delays. It is established by the following result.

Theorem 3.

Let $M=(V,\rho ,Q,s_0,F,\delta )$ be a simple WKFA with only initial delays. Then $L_u\left(M\right)\in \mathcal{REG}$.

Proof. 

A sticker system $\gamma$ can be obtained from M, according to the proof of Theorem 1. Let $\gamma =(V^{\prime },{\rho }^{\prime },A,D)$ and $V^{\prime }=V\cup Q\cup \{\#,q_f\}$ be such a sticker system. Let $G=(N,\left[\begin{array}{c}{V}^{\prime }\\ V^{\prime }\end{array}\right],S,P)$ be a linear grammar built from $\gamma$ as described in [10]. It can be observed that, for every production in G in the form $A\to \alpha B\beta$ the sticker $\alpha$ is defined from the symbols in $Q\cup \{\#,q_f\}$ while the sticker $\beta$ is defined from the symbols in V.

Now, a left linear grammar $G^{\prime }=(N,V,S,P^{\prime })$ can be constructed from G. The set of productions in $P^{\prime }$ is defined as follows:

• $A\to B{v}_1$ if $A\to \left(\begin{array}{c}{u}_1\\ u_2\end{array}\right)B\left(\begin{array}{c}{v}_1\\ v_2\end{array}\right)\in P$;
• $A\to h\left({\omega }_1\right)$ if $A\to \left(\begin{array}{c}{\omega }_1\\ {\omega }_2\end{array}\right)\in P,$

where the morphism $h:V^{\prime }\to V$ is defined as $h\left(a\right)=a$ if $a\in V$ and $h\left(a\right)=\lambda$ if $a\in Q\cup \{\#,q_f\}$. The language generated by the grammar $G^{\prime }$ is the result of removing the symbols in $Q\cup \{\#,q_f\}$ from the strings generated by G in the upper strand. These strings are the strings in $L_u\left(M\right)$. Since $G^{\prime }$ is a left linear grammar and $L\left(G^{\prime }\right)=L_u\left(M\right)$ then $L_u\left(M\right)\in \mathcal{REG}$. □

5. Conclusions

In this paper we addressed some aspects of the languages defined by WKFA where the delay between the two strands in obtaining the upper strings is bounded. This aspect is interesting because, on the one hand, it allows us to relate two classical DNA computational models such as Watson-Crick finite automata and sticker systems. On the other hand, it allows us to establish a result that limits the computational capacity of the WKFA model, i.e., by introducing a bounded delay, we are reducing the class of languages that the model is able to accept.

Another aspect we want to highlight is that the study of language families characterized by bounded delays is a prior step to establishing efficient methods for their inductive inference, that is the application of machine learning techniques to obtain DNA computational models. In this sense, some previous results allow us to approach this aspect in a reasonable way [12]. The imposition of some kind of constraints and normal forms for some classes of languages accepted by WKFA is important in establishing the machine learning algorithms to infer WKFA from positive examples. It is well known in formal language theory that from linear languages there exist inherently ambiguous languages [17]. Since WKFA can be represented by intersections of linear and even linear languages [18], then the inherent ambiguity of some languages accepted by this model is unavoidable. This leads to multiple options, when specifying a set of transitions during the elaboration of a model by using machine learning techniques. The imposition of features such as initial delays makes the ambiguity disappear given that a predefined form is imposed on the transitions and makes it feasible to automatically learn some subclasses of this model.

There are additional aspects of this work that deserve to be explored in future research. For example, one aspect to consider is whether delays induce a hierarchy of languages in a gradual way, i.e., whether any language accepted by a WKFA with a bounded delay d can be accepted by a WKFA with a smaller delay. In the case of a negative answer to this question, we could obtain an infinite hierarchy, where the smallest class would be defined by the class of regular languages (null delays) which, in turn, would contain the languages that can be accepted only with initial delays.