Henning Fernau
email: fernau@uni-trier.de

Lakshmanan Kuppusamy

Indhumathi Raman
email: indhumathi.r@vit.ac.in

Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems

Keywords: insertion-deletion systems, graph-controlled systems, descriptional complexity measures, computational completeness

We consider graph-controlled insertion-deletion systems and prove that the systems with sizes (i) (3; 1, 1, 1; 1, 0, 1), (ii) (3; 1, 1, 1; 1, 1, 0) and (iii) (2; 2, 0, 0; 1, 1, 1) are computationally complete. Moreover, graphcontrolled insertion-deletion systems simulate linear languages with sizes (2; 2, 0, 1, 1, 0, 0), (2; 2, 1, 0; 1, 0, 0), (3; 1, 0, 1; 1, 0, 0), or (3; 1, 1, 0; 1, 0, 0). Simulations of metalinear languages are also studied. The parameters in the size (k; n, i , i ; m, j , j ) of a graph-controlled insertion-deletion system denote (from left to right) the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; a similar list of three parameters concerning deletion follows.

Introduction

Insertion and deletion operations frequently occur in DNA processing and RNA editing. In the theoretical process of mismatched annealing of DNA sequences, certain segments of the strands are either inserted or deleted [START_REF] Gh | DNA Computing: New Computing Paradigms[END_REF]. During RNA editing, some fragments of messenger RNA are inserted or deleted [START_REF] Benne | RNA Editing: The Alteration of Protein Coding Sequences of RNA[END_REF], [START_REF] Biegler | Regulated RNA rewriting: Modelling RNA editing with guided insertion[END_REF]. The motivation for insertion operations can be found in [START_REF] Haussler | Insertion languages[END_REF], where this operation and its iterated variant were introduced as a generalization of concatenation and Kleene's closure. The deletion operation was introduced in [START_REF] Kari | On insertion and deletion in formal languages[END_REF]. Insertion and deletion operations together were introduced into formal language theory in [START_REF] Kari | Contextual insertions/deletions and computability[END_REF]. The corresponding grammatical mechanism is called insertion-deletion system (abbreviated as ins-del system). Informally, if a string η is inserted between two parts w 1 and w 2 of a string w 1 w 2 to get w 1 ηw 2 , we call the operation insertion, whereas if a substring δ is deleted from a string w 1 δw 2 to get w 1 w 2 , we call the operation deletion. Suffixes of w 1 and prefixes of w 2 are called contexts.

Several variants of ins-del systems have been considered in literature, like ins-del P systems [START_REF] Alhazov | P systems with minimal insertion and deletion[END_REF], tissue P systems with ins-del rules [START_REF] Kuppusamy | On the power of tissue P systems with insertion and deletion rules[END_REF], context-free insdel systems [START_REF] Margenstern | Context-free insertiondeletion systems[END_REF], matrix ins-del systems [START_REF] Kuppusamy | Matrix insertion-deletion systems for bio-molecular structures[END_REF][START_REF] Petre | Matrix insertion-deletion systems[END_REF], etc. All the mentioned papers (as well as [START_REF] Takahara | On the computational power of insertion-deletion systems[END_REF]) attempted to characterize the recursively enumerable languages (i.e., they show computational completeness) using ins-del systems. We refer to the survey article [START_REF] Verlan | Recent developments on insertion-deletion systems[END_REF] for details of variants thereof.

One of the important variants of ins-del systems is graph-controlled ins-del systems introduced in [START_REF] Freund | Graph-controlled insertiondeletion systems[END_REF] and further studied in [START_REF] Ivanov | Universality of graph-controlled leftist insertion-deletion systems with two states[END_REF]. In such a system, the concept of a component is introduced and is associated with every insertion or deletion rule. The transition is performed by choosing any applicable rule from the set of rules of the current component and by moving the resultant string to the target component specified in the rule. If the transition of strings from component to component establishes a tree structure for a given system, then this system can also be seen as an ins-del P system. The objective is to obtain computationally completeness results with few components and small descriptional complexity measures of the ins-del rules.

For an ins-del system, the descriptional complexity measures are based on the size comprising of (i) the maximal length of the insertion string, denoted by n, (ii) the maximal length of the left context and right context used in insertion rules, denoted by i and i , respectively, (iii) the maximal length of the deletion string, denoted by m, (iv) the maximal length of the left context and right context used in deletion rules denoted by j and j , respectively. The size of an ins-del system is denoted by (n, i , i ; m, j , j ).

Initially, computationally completeness results for graph-controlled ins-del systems were obtained with 5 components [START_REF] Krassovitskiy | Computational power of insertiondeletion (P) systems with rules of size two[END_REF], then reduced to 4 components with sizes (1, 1, 0; 2, 0, 0), (2, 0, 0; 1, 1, 0), (1, 1, 0; 1, 1, 0), (1, 1, 0; 1, 0, 1) [START_REF] Freund | Graph-controlled insertiondeletion systems[END_REF] and then later reduced to 3 components with sizes (1, 2, 0; 1, 1, 0), (1, 1, 0; 1, 2, 0) [START_REF] Ivanov | About one-sided one-symbol insertion-deletion P systems[END_REF]. In [START_REF] Ivanov | Universality of graph-controlled leftist insertion-deletion systems with two states[END_REF], even graph-controlled ins-del systems with only 2 components and sizes (1, 1, 0; 1, 2, 0), (1, 2, 0; 1, 1, 0) were shown to be computationally complete. As an ins-del system without graph-control can be seen as a graph-controlled ins-del system with just one component, it is remarkable in this context to note that such system with size (1, 1, 1; 1, 1, 1) are computationally complete; see [START_REF] Takahara | On the computational power of insertion-deletion systems[END_REF].

In this paper, we prove the computational completeness of the following graph-controlled ins-del systems: (i) 3 components with size (1, 1, 1; 1, 1, 0) or (1, 1, 1; 1, 0, 1); (ii) 2 components with size (2, 0, 0; 1, 1, 1). We also simulate linear grammars by graph-controlled ins-del systems having (i) 3 components with size (1, 0, 1; 1, 0, 0) or (1, 1, 0; 1, 0, 0); (ii) 2 components with size (2, 0, 1; 1, 0, 0) or (2, 1, 0; 1, 0, 0). We also extend the simulation technique to metalinear languages.

Preliminaries

We assume that the readers are familiar with the standard notations used in formal language theory. However, we now recall a few notations here.

Let N denote the set of positive integers, and [1 . . . k] = {i ∈ N : 1 ≤ i ≤ k}. Given an alphabet (finite set) Σ, Σ * denotes the free monoid generated by Σ. The elements of Σ * are called strings or words; λ denotes the empty string. For a string w ∈ Σ * , |w| denotes the length of a string w and w R denotes the reversal (mirror image) of w. Likewise, L R and L R are understood for languages L and language families L. RE denotes the family of the recursively enumerable languages, The family of linear and metalinear languages is denoted by LIN , MLIN , respectively, where MLIN is the smallest language class containing LIN and is closed under concatenation. It is known from [START_REF] Kutrib | Finite turns and the regular closure of linear contextfree languages[END_REF] that LIN is neither closed under concatenation nor under Kleene closure whereas MLIN is not closed under Kleene closure but closed under concatenation. Also, both LIN and MLIN are closed under reversal.

For the computational completeness results, we are using the fact that type-0 grammars in the special Geffert normal form are known to characterize the recursively enumerable languages. According to [START_REF] Freund | Graph-controlled insertiondeletion systems[END_REF], a type-0 grammar G = (N, T, P, S) is said to be in special Geffert normal form, SGNF for short, if -N decomposes as N = N ∪ N , where N = {A, B, C, D} and N contains at least the two nonterminals S and S , the only non-context-free rules in P are the two erasing rules AB → λ and CD → λ, the context-free rules are of the following forms:

X → Y b or X → bY where X, Y ∈ N , X = Y , b ∈ T ∪ N , or S → λ.
How to construct this normal form is described in [START_REF] Freund | Graph-controlled insertiondeletion systems[END_REF] and is based on [START_REF] Geffert | How to generate languages using only two pairs of parentheses[END_REF]. Also, the derivation of a string is done in two phases. First, the context-free rules are applied repeatedly and the phase I is completed by applying the rule S → λ in the derivation. In phase II, only the non-context-free erasing rules are applied repeatedly and the derivation ends. It is to be noted that as these context-free rules are more of a linear type, it is easy to see that there can be at most only one nonterminal from N present in the derivation of G. We exploit this observation in the proofs of Theorem 2 and Theorem 4. Also, note that X = Y, X, Y ∈ N in the context-free rules.

Insertion-Deletion Systems

We now give the basic definition of insertion-deletion systems, following [START_REF] Gh | DNA Computing: New Computing Paradigms[END_REF][START_REF] Kari | Contextual insertions/deletions and computability[END_REF].

Definition 1. An insertion-deletion system is a construct γ = (V, T, A, R), where V is an alphabet, T ⊆ V is the terminal alphabet, A is a finite language over V , R is a finite set of triplets of the form (u, η, v) ins or (u, δ, v) del , where

(u, v) ∈ V * × V * , η, δ ∈ V + .
The pair (u, v) is called the context, η is called the insertion string, δ is called the deletion string and x ∈ A is called an axiom. For all contexts of t where t ∈ {ins, del}, if u = λ (v = λ), then we call the operation t to be right context (left context). If both u, v = λ for a rule, then it means, the corresponding insertion/deletion can be done freely anywhere in the string and is called contextfree insertion/deletion. An insertion rule will be of the form (u, η, v) ins , which means that the string η is inserted between u and v. A deletion rule will be of the form (u, δ, v) del , which means that the string δ is deleted between u and v. In other words, (u, η, v) ins corresponds to the rewriting rule uv → uηv, and (u, δ, v) del corresponds to the rewriting rule uδv → uv. Consequently, for x, y ∈ V * we can write x ⇒ y if y can be obtained from x by using either an insertion rule or a deletion rule which is given as follows:

1. x = x 1 uvx 2 , y = x 1 uηvx 2 , for some x 1 , x 2 ∈ V * and (u, η, v) ins ∈ R. 2. x = x 1 uδvx 2 , y = x 1 uvx 2 , for some x 1 , x 2 ∈ V * and (u, δ, v) del ∈ R.
The language generated by γ is defined by

L(γ) = {w ∈ T * | x ⇒ * w, for some x ∈ A} ,
where ⇒ * is the reflexive and transitive closure of the relation ⇒.

Graph-Controlled Insertion-Deletion Systems

A graph-controlled insertion-deletion system with k components, or (k-)GCID for short, is a construct Π = (k, V, T, A, H, i 0 , i f , R) where k is the number of components, -V is an alphabet, -T ⊆ V is the terminal alphabet, -A ⊆ V is a finite set of axioms, -H is a set of labels associated (in a one-to-one manner) to the rules in R,

-i 0 ∈ [1 . . . k] is the initial component, -i f ∈ [1 . . . k]
is the final or target component, and -R is a finite set of rules of the form (i, r, j) where r is an insertion rule of the form (u, η, v) ins or deletion rule of the form (u, δ, v) del and i, j ∈ [1 . . . k].

A rule of the form l : (i, r, j), where l ∈ H is the label associated to the rule, denotes that the string is sent from component i (for short denoted as Ci) to Cj after the application of the insertion or deletion rule r on the string.

A configuration of Π is represented by (w) i where i is the number of the current component (initially i 0 ) and w is the current string. A transition (w) i ⇒ (w ) j is performed if there exists a rule l : (i, r, j) in R such that w ⇒ w on applying the insertion or deletion rule r; in this case, we also write (w

) i ⇒ l (w ) j or (w ) j ⇐ l (w) i . By (w) i ⇒ l
⇐ l (w ) j , we mean that (w ) j is derivable from (w) i using rule l and (w) i is derivable from (w ) j using rule l . The language of a graph-controlled insertion-deletion system is the set of all terminal strings in the target component i f reachable from an axiom and the initial component i 0 . Formally,

L(Π) = {w ∈ T * | (x) i0 ⇒ * (w) i f for some x ∈ A}.
Next, we discuss about the size of a graph-controlled ins-del system. A graphcontrolled ins-del system Π is of size (k; n, i , i ; m, j , j ) (with the corresponding language classes denoted by GCID(k; n, i , i ; m, j , j )) if k = the number of components n = max{|η| : (i, (u, η, v) ins , j) ∈ R} (max. length of the inserted string) i = max{|u| : (i, (u, η, v) ins , j) ∈ R} (max. length of the left context) i = max{|v| : (i, (u, η, v) ins , j) ∈ R} (max. length of the right context) m = max{|δ| : (i, (u, δ, v) del , j) ∈ R} (max. length of the deleted string) j = max{|u| : (i, (u, δ, v) del , j) ∈ R} (max. length of the left context) j = max{|v| : (i, (u, δ, v) del , j) ∈ R} (max. length of the right context)

Let us give some examples for GCID systems.

Example 1. The following GCID system Π 1 of size (2; 1, 0, 0; 0, 0, 0) generates the language

L 1 = {w ∈ {a, b} * : |w| a = |w| b }. Π 1 = (2, {a, b}, {a, b}, {λ}, {r1, r2}, 1, 1, R) ,
where the rules of R are: r1 : (1, (λ, a, λ) ins , 2), r2 : (2, (λ, b, λ) ins , 1).

Example 2. With axiom

A = {ab, λ}, two rules grouped in singleton compo- nents C1 = {(1, (a, a, b) ins , 2)}, C2 = {(2, (a, b, b) ins , 1)}, initial and target component C1, the GCID system Π 2 can describe L 2 = {a n b n : n ≥ 0}, i.e., L 2 ∈ GCID(2; 1, 1, 1; 0, 0, 0).
Example 3. Consider the GCID system Π 3 of size (3; 1, 0, 1; 1, 0, 0) as follows:

Π 3 = (3, {S, S , a, b}, {a, b}, {SS }, H, 1, 1, R) ,
where the rules of R are the following ones: We claim that Π 3 generates L 3 = {a n b n : n ≥ 1} * . We prove our claim by discussing the working of the rules of Π 3 here. Starting with the axiom SS in C1, a is inserted before S and then b is inserted before S in order, repeatedly, and this leads to (a n Sb n S ) in C1. After n(≥ 0) cycles of repetitions, rule r1.2 is applied and this deletes S and we move to C3 with the string a n b n S . We now have a choice of applying rule r3.1 or r3.2. In the latter case, S is deleted and the process terminates at the target component C1. In the former case, we are back to the starting point in order to generate a n b n a m b m SS . On repeating this process several times as desired, the process can be terminated by applying the rule r3.2. With these arguments, one can see that this system generates L 3 .

Observe the similarities between the examples:

L 1 is the iterated shuffle clo- sure of (L 2 ∪ L R 2 ), while L 3 is the Kleene closure of L 2 . Notice that L 1 / ∈ LIN and L 3 /
∈ MLIN , and the latter can be proved in the same way as argued in [4, page 137] for the Łukasiewicz language.

Auxiliary Results

In order to simplify the proofs of some of our main results, the following observations are helpful.

Theorem 1. For all non-negative integers k, n, i , i , m, j, j , we have that

GCID(k; n, i , i ; m, j , j ) = [GCID(k; n, i , i ; m, j , j )] R .
Proof. To an ins-del rule (x, y, z) µ with µ ∈ {ins, del}, we associate the reversed rule ρ

(r) = (z R , y R , x R ) µ . Let Π = (k, V, T, A, H, i 0 , i f , R) be a graph-controlled insertion-deletion system with k components. Map a rule l : (i, r, j) ∈ Π to l : (i, ρ(r), j) in ρ(R). Define Π R = (k, V, T, A R , H, i 0 , i f , ρ(R)).
Then, an easy inductive argument shows that L(Π R ) = (L(Π)) R . Observing the sizes of the system now shows the claim.

Corollary 1. Let L be a language class that is closed under reversal. Then, for all non-negative integers k, n, i , i , m, j , j , we conclude that 1. L = GCID(k; n, i , i ; m, j , j ) if and only if L = GCID(k; n, i , i ; m, j , j ); 2. L ⊆ GCID(k; n, i , i ; m, j , j ) if and only if L ⊆ GCID(k; n, i , i ; m, j , j ).

Computational Completeness Results

In this section, we prove the computational completeness results for GCID systems of sizes (i) (3; 1, 1, 1; 1, 1, 0) (ii) (3; 1, 1, 1; 1, 0, 1) and (iii) (2; 2, 0, 0; 1, 1, 1). One may note that, in the first (second) system, the deletion is left context (right context) and in the third system, the insertions are performed in a context-free manner.

Theorem 2. GCID(3; 1, 1, 1; 1, 1, 0) = RE .

Proof. Consider a type-0 grammar G = (N, T, P, S) in SGNF. We build a GCID system Π such that L(Π) = L(G). Let Π = (3, V, T, {S}, H, 1, 1, R). The rules in P are labelled injectively with labels from

[1 . . . |P |]. Let V = N ∪ T ∪ {p : p ∈ [1 . . . |P |]}.
R is defined as follows. The rules are classified into components C1, C2 and C3 as indicated by the first character following the rule label. We simulate the rule p: X → bY by the following ins-del rules:

p1.1 : (1, (λ, p, X) ins , 2) p2.1 : (2, (λ, b, p) ins , 3), p2.2 : (2, (Y, X, λ) del , 1) p3.1 : (3, (b, Y, p) ins , 3), p3.2 : (3, (Y, p, λ) del , 2)
We simulate the rule q: X → Y b by the following ins-del rules:

q1.1 : (1, (λ, q, X) ins , 2) q2.1 : (2, (λ, Y, q) ins , 3), q2.2 : (2, (λ, q, λ) del , 1) q3.1 : (3, (q, b, X) ins , 3), q3.2 : (3, (b, X, λ) del , 2)

We simulate the rule f : AB → λ by the following ins-del rules:

f 1.1 : (1, (λ, f, A) ins , 2) f 2.1 : (2, (λ, f, λ) del , 1), f 2.2 : (2, (f, A, λ) del , 3) f 3.1 : (3, (f, B, λ) del , 2)
We simulate the rule g: CD → λ by the following ins-del rules:

g1.1 : (1, (λ, g, C) ins , 2) g2.1 : (2, (λ, g, λ) del , 1), g2.2 : (2, (g, C, λ) del , 3) g3.1 : (3, (g, D, λ) del , 2)
We simulate the rule h : S → λ by the ins-del rule h1.1 : (1, (λ, S , λ) del , 1).

We now proceed to prove that L(Π) = L(G). We do this by explaining how the simulation of the rules of G should work and why no other malicious derivations are possible in Π. Working of p : X → bY : Consider the string αXβ in C1. Then there is a unique sequence of rule applications in Π as follows.

(αXβ) 1 ⇒ p1.1 (αpXβ) 2 ⇒ p2.1 (αbpXβ) 3 ⇒ p3.1 (αbY pXβ) 3 ⇒ p3.2 (αbY Xβ) 2 ⇒ p2.2 (αbY β) 1 .
Note that though applying the rule p3.1 leaves the string in C3 itself, rule p3.1 cannot be applied again (the benefit of using double-sided context). Also, only one X of N is present in the derivation until a Y ∈ N is introduced, thus, p2.2 cannot be used before the rule p2.1 is applied. Working of q : X → Y b: Consider the string αXβ in C1. On applying rule q1.1, we insert q before X and we get αqXβ in C2. Now, we can apply either q2.1 or q2.2. In the latter case, we delete the just inserted marker q and end up with αXβ in C1 (back to the starting point). Hence, we choose rule q2.1 eventually to move on. In this case, consider the following sequence of rule applications in Π.

(αXβ) 1 ⇒q1.1 ⇐q2.2 (αqXβ) 2 ⇒ q2.1 (αY qXβ) 3 ⇒ q3.1 (αY qbXβ) 3 ⇒ q3.2 (αY qbβ) 2
At this point, we again have a choice of applying rule q2.1 or q2.2. In the former case, we will again insert a Y before q yielding αY Y qbβ in C3. As Y ∈ N is the only nonterminal in the string, the first symbol of β cannot be X. Thus, we cannot apply any rule in C3 and the derivation stops with nonterminals in a non-target component. In the latter case, by applying q2.2 we delete q and get αY bβ in C1, which is the target component.

We next proceed to discuss the simulation of the non context-free erasing rules AB → λ and CD → λ. Working of f : AB → λ: The working of the rule is shown by the following sequence of rule applications.

(αABβ) 1 ⇒ f 1.1 ⇐ f 2.1 (αf ABβ) 2 ⇒ f 2.2 (αf Bβ) 3 ⇒ f 3.1 (αf β) 2 ⇒ f 2.1 (αλβ) 1
Working of g : CD → λ: Similar to the working of the rule f : AB → λ.

The rule (1, (λ, S , λ) del , 1) directly erases S . We start at S in C1 and by repeatedly applying the rules p, q, f, g, h, we eventually get (S) 1 ⇒ * (w) 1 . This proves that L(G) ⊆ L(Π).

To prove the reverse relation (L(Π) ⊆ L(G)), we observe that the rules of Π are applied in groups and each group of rules corresponds to one of p, q, f, g, h. Also, it is not possible to switch between the simulation of some p, say, to that of f , as we always use unique marker symbols to prevent this from happening. This observation completes the proof.

As RE is known to be closed under reversal, we conclude with Corollary 1:

Theorem 3. GCID(3; 1, 1, 1; 1, 0, 1) = RE .
Theorem 4. GCID(2; 2, 0, 0; 1, 1, 1) = RE .

Proof. Consider a type-0 grammar G = (N, T, P, S) in SGNF. We construct a GCID system Π such that L(Π) = L(G). Let Π = (2, V, T, {S}, H, 1, 1, R). The rules from P in G are labelled injectively with labels from

[1 . . . |P |]. The alphabet of Π is V = N ∪ T ∪ {p, p : p ∈ [1 . . . |P |]}. R is defined as follows.
We simulate the rule p: X → bY , with X, Y ∈ N , by the following ins-del rules:

p1.1 : (1, (λ, bY, λ) ins , 2) p2.1 : (2, (Y, X, λ) del , 1)
We simulate the rule q: X → Y b, with X, Y ∈ N , by the following ins-del rules:

q1.1 : (1, (λ, Y b, λ) ins , 2) q2.1 : (2, (λ, X, Y ) del , 1)
We simulate the rule f : AB → λ, with A, B ∈ N , by the following ins-del rules:

f 1.1 : (1, (λ, f f , λ) ins , 2), f 1.2 : (1, (A, f, f ) del , 1), f 1.3 : (1, (λ, A, f ) del , 2) f 2.1 : (2, (f , B, λ) del , 1), f 2.2 : (2, (λ, f , λ) del , 1)
We simulate the rule g: CD → λ by the following ins-del rules: g1.1 : (1, (λ, gg , λ) ins , 2), g1.2 : (1, (C, g, g ) del , 1), g1.3 : (1, (λ, C, g ) del , 2) g2.1 : (2, (g , D, λ) del , 1), g2.2 : (2, (λ, g , λ) del , 1)

We simulate the rule h : S → λ by the ins-del rule h1.1 : (1, (λ, S , λ) del , 1). We now proceed to reason why L(Π) = L(G). Working of p : X → bY : Consider a string αXβ in C1. The string bY is free to be inserted anywhere in the string using rule p1.1 and the derivation moves to C2. Rule p2.1 can be applied only if bY is inserted before X. Recall that X, Y ∈ N and these types of nonterminals only occur once in valid sentential forms of G (SGNF property). In this case, the X is deleted yielding bY and the derivation ends at the target component C1. If bY has been inserted elsewhere, then no rule of C2 can be applied and we are trapped in a non-target component with nonterminals in the string. Working of q : X → Y b: Similar to the working of the rule p as explained above. Working of f : AB → λ: Consider the string αABβ in C1. We introduce two markers f, f together anywhere in the string using the rule f 1.1 and move to C2. Suppose that f f has been inserted between A and B. Now, there is a choice of applying rule f 2.1 or f 2.2. In the latter case, we will delete the marker f and come to the target component C1 with αAf Bβ. If we introduce f f again, this will eventually lead to a string having the nonterminals f and A in it, thus not deriving any terminal string. This observation forces one to choose rule f 2.1 before applying f 2.2. In this case, there is a unique sequence of rule applications:

(αAf f Bβ) 2 ⇒ f 2.1 (αAf f β) 1 ⇒ f 1.2 (αAf β) 1 ⇒ f 1.3 (αf β) 2 ⇒ f 2.2 (αλβ) 1
Suppose that f f has not been inserted between A and B, then it is not difficult to see that the derived string will always contain some nonterminals. Working of g : CD → λ: Similar to the working of the rule f : AB → λ.

The rule (1, (λ, S , λ) del , 1) directly erases S . We start at S in C1 and by repeatedly applying the rules p, q, f, g, h, we eventually get (S) 1 ⇒ * (w) 1 . As argued above, no malicious derivations can lead to terminal strings in C1.

(Meta)linear Languages

We next prove that GCID systems of sizes (2; 2, 1, 0; 1, 0, 0), (2; 2, 0, 1; 1, 0, 0), (3; 1, 1, 0; 1, 0, 0), or (3; 1, 0, 1; 1, 0, 0) can simulate all linear languages. In these systems, deletions are performed in a context-free manner. While comparing the last two sizes with the first two sizes, one may note that the length of the inserted string is reduced at the cost of increasing the number of components. We also show how to extend the simulations beyond linear languages.

Theorem 5. LIN GCID(2; 2, 1, 0; 1, 0, 0).

Proof. Consider a linear grammar G = (N, T, P, S), where every rule of P is of the form X → Y a or X → aY or X → a or X → λ. We construct a GCID system Π = (2, V, T, {S}, H, 1, 1, R) for G. The rules from P in G are labelled injectively with labels from

[1 . . . |P |]. The alphabet of Π is V = N ∪ T ∪ {p : p ∈ [1 . . . |P |]}.
The set of rules R of Π is defined as follows. We simulate the rule p : X → Y a by the following ins-del rules:

p1.1 : (1, (X, p, λ) ins , 2), p1.2 : (1, (p, Y a, λ) ins , 2) p2.1 : (2, (λ, X, λ) del , 1), p2.2 : (2, (λ, p, λ) del , 1)
We simulate the rule q : X → aY by the following ins-del rules:

q1.1 : (1, (X, q, λ) ins , 2), q1.2 : (1, (q, aY, λ) ins , 2) q2.1 : (2, (λ, X, λ) del , 1), q2.2 : (2, (λ, q, λ) del , 1)

We next simulate the rule f : X → a by the following ins-del rules:

f 1.1 : (1, (X, a, λ) ins , 2) f 2.1 : (2, (λ, X, λ) del , 1)
We now prove the theorem by discussing the working of the above rules. Working of p : X → Y a: Consider the string αXβ in C1. On applying rule p1.1, we insert p after X and get αXpβ in C2. At this point, we have a choice of applying rule p2.1 or p2.2. In the latter case, the marker p is deleted and we move to C1 with αXβ in the string and this is our starting point. Hence we have to use rule p2.1 eventually to proceed. In this case, X is deleted and move to C1 with αpβ. At this point, we note that the rule p1.1 cannot be applied since in linear grammar there is at most one nonterminal (in this case, X) in the string; this was already deleted in the previous step. With these arguments, we simulate the rule X → Y a as follows:

(αXβ) 1 ⇒p1.1 ⇐p2.2 (αXpβ) 2 ⇒ p2.1 (αpβ) 1 ⇒ p1.2 (αpY aβ) 2 ⇒ p2.2 (αY aβ) 1 .
In the above sequence, we note that before the derivation (αpβ) 1 ⇒ p1.2 (αpY aβ) 2 , the rule p1.1 cannot be applied since in a linear grammar there is at most one nonterminal (in this case, X) in the string and it is already deleted in the previous step. Working of q : X → aY : Similar to the working of the above rule p : X → Y a. The sequence of rule applications in Π is given below for a better understanding.

(αXβ) 1 ⇒q1.1 ⇐q2.2 (αXqβ) 2 ⇒ q2.1 (αqβ) 1 ⇒ q1.2 (αpaY β) 2 ⇒ q2.2 (αaY β) 1 .
The working of rule f : X → a is simple and straightforward. Since we start at S in C1 and if we repeatedly apply the rules p, q, f , we eventually get (S) 1 ⇒ * (w) 1 . This proves that L(G) ⊆ L(Π).

For the converse direction L(G) ⊇ L(Π), observe the remarks that we gave above when explaining the working of the simulations; apart from unnecessary additional loops in the simulation, no successful derivations are possible in Π other than those intended for the simulation of G.

The strictness of the inclusion follows from Examples 1 and 3.

Remark 1. By allowing for a few more components, we can extend the previous simulation result to cover Kleene closures of linear languages or also MLIN . For instance, starting with axiom S S and a third component containing rules r3.1 : (3, (S , S, λ) ins , 1) and r3.2 : (3, (λ, S , λ) del , 1) and changing f 2.1 to transit to C3, the modified system Π would describe (L(G)) + , or, by having S as the axiom and starting in C3, we can get (L(G)) * .

Likewise, we can describe metalinear languages with three or four components.

Theorem 6. MLIN GCID(4; 2, 1, 0; 1, 0, 0) ∩ GCID(3; 2, 1, 0; 1, 0, 1).

Proof. If L ∈ MLIN happens to be a linear language, we can proceed as in Theorem 5. So, we assume that L ∈ MLIN -LIN is given. We can think of the work of a metalinear grammar G with L(G) = L ⊆ T * (generating the concatenation of k linear languages L(G 1 ), . . . , L(G k ) with start symbols S 1 , . . . , S k , respectively, and k pairwise disjoint nonterminal alphabets N 1 , . . . , N k ) as follows: starting with S 1 S 2 as the axiom, first, G 1 generates a terminal word. Then, S 2 → S 2 S 3 is executed, and G 2 generates a terminal word, starting from S 2 . This strategy continues, until S k-1 → S k-1 S k is executed, followed by the generation of a terminal word by G k-1 and finally S k → S k initiates the last grammar G k to append a terminal word.

Let us first focus on GCID(4; 2, 1, 0; 1, 0, 0). More formally, we construct

a GCID system Π = (4, V, T, {S 1 S 2 }, H, 1, 1, R) for G. Let V 1 , . . . , V k be the alphabets resulting from the construction of GCID systems Π i for G 1 , . . . , G k according to Theorem 5. Let N i = V i -T and assume (w.l.o.g.) that N 1 , . . . , N k are pairwise disjoint. Let V = k i=1 V i ∪ {S i : i ∈ [1 . . . k]}. Let R i be the rule set of Π i . R i coincides with R i except for (possibly) terminating rules of the type f 2.1 that target at C3 for i ∈ [1 . . . (k -1)]. Let R = k i=1 R i ∪ R T ,
where R T collects transition rules that are described in details in the following.

The work of grammar G i , say, of G 1 , is simulated (as described in the proof of Theorem 5). Then, (in general) we transit to the third component. We perform the following transition rules: Observe that the applications of the new rules (in comparison to what is inherited from Theorem 5) is deterministic, and due to the new components, no interference with previously introduced rules is possible. Furthermore, the context-free deletion rules in C2 of Theorem 5 will delete only nonterminals of N i , i ∈ [1 . . . k] in the present simulation; hence, they do not interfere with the new nonterminals like S i .

r 1→2 2.1 : (2, (λ, r 1→2 , λ) del , 1) r 1→2
We now turn to GCID(3; 2, 1, 0; 1, 0, 1). The only real problem merging C2 and C4 was that during the simulation of G i , possibly the symbol S i+1 gets deleted. This can be prevented by requiring the right context of r i→i+1 in the rule that deletes S i+1 . More precisely, the modified rules for P i will be r i→i+1 3.1 : (3, (S i+1 , r i→i+1 , λ) ins , 2) and r i→i+1 2.2 : (2, (λ, S i+1 , r i→i+1 ) del , 3). The remaining technical details are left to the reader.

Remark 1 and more concretely Example 3 shows the claimed strictness of the inclusion.

Since LIN and MLIN are known to be closed under reversal [START_REF] Kutrib | Finite turns and the regular closure of linear contextfree languages[END_REF], by using Corollary 1, we can immediately conclude the next two theorems (7 and 8): Theorem 7. LIN GCID(2; 2, 0, 1; 1, 0, 0). Theorem 8. MLIN GCID(4; 2, 0, 1; 1, 0, 0) ∩ GCID(3; 2, 0, 1; 1, 1, 0). Theorem 9. LIN GCID(3; 1, 1, 0; 1, 0, 0).

Proof. Consider a linear grammar G = (N, T, P, S). We construct a GCID system Π = (3, V, T, {S}, H, 1, 1, R). The rules from P in G are assumed to be labelled injectively with labels from the set [1 . . . We simulate the rule q : X → aY by the following ins-del rules:

|P |]. The alphabet of Π is V = N ∪ T ∪ {p, p : p ∈ [1 . . . |P |]}.
q1.1 : (1, (X, q, λ) ins , 3), q1.2 : (1, (q, q , λ) ins , 2), q1.3 : (1, (q , Y, λ) ins , 2) q2.1 : (2, (q, a, λ) ins , 3), q2.2 : (2, (λ, q , λ) del , 1) q3.1 : (3, (λ, X, λ) del , 1), q3.2 : (3, (λ, q, λ) del , 1)

We simulate the rule f : X → a by the following ins-del rules:

f 1.1 : (1, (X, a, λ) ins , 3) f 3.1 : (3, (λ, X, λ) del , 1)
Working of p : X → Y a: Consider the string αXβ in C1. On applying rule p1.1, we insert p after X and get αXpβ in C3. At this point, we have a choice of applying rule p3.1 or p3.2. In the latter case, the marker p is deleted and we move to C1 with αXβ as the string and this is our starting point. Hence, we use rule p3.1 eventually to proceed. Then, X is deleted and we move to C1 with αpβ. Now, the rule p1.1 cannot be applied since in linear grammars there is at most one nonterminal (in this case, X) in the string that was already deleted in the previous step. Hence, we simulate the rule X → Y a as follows:

(αXβ) 1 ⇒p1.1 ⇐p3.2 (αXpβ) 3 ⇒ p3.1 (αpβ) 1 ⇒ p1.2 (αpaβ) 2 ⇒ p2.1 (αpp aβ) 3 ⇒ p3.2 (αp aβ) 1 ⇒ p1.3 (αp Y aβ) 2 ⇒ p2.2 (αY aβ) 1 .
Working of q : X → aY : Consider the string αXβ in C1. On applying rule q1.1, we insert q after X and get αXqβ in C3. At this point, we have a choice of applying rule q3.1 or q3.2. In the latter case, the marker q will be deleted and we move back to the starting point. Hence we have to use rule q3.1 eventually to proceed. In this case, X is deleted and we move to C1 with αqβ where q is inserted after q and the string moves to C2 with αqq β. In C2, we can apply the rule q2.1 or q2.2. On applying q2.2, q is deleted and the string αqβ will be in C1 and we are back to the previous step. This is also depicted in the following derivation. This forces us to apply the rule q2.1 and the sequence of rule applications is shown in the derivation. With these arguments, we simulate the rule X → aY as follows:

(αXβ) 1 ⇒q1.1 ⇐q3.2 (αXqβ) 3 ⇒ q3.1 (αqβ) 1 ⇒q1.2 ⇐q2.2 (αqq β) 2 ⇒ q2.1 (αqaq β) 3 ⇒ q3.1 (αaq β) 1 ⇒ q1.3 (αaq Y β) 2 ⇒ q2.2 (αaY β) 1 .
The working of rule f : X → a is simple and straightforward. By repeatedly applying p, q, f , we eventually get (S) 1 ⇒ * (w) 1 . Thus L(G) ⊆ L(Π). Moreover, as argued above, no other derivations are possible for Π, entering C1 with a string αXβ. So, by induction, L(G) ⊇ L(Π) also follows.

As LIN is known to be closed under reversal, by using Corollary 1, we have: Theorem 10. LIN GCID(3; 1, 0, 1; 1, 0, 0).

In the literature, GCID(4; 1, 1, 0; 1, 0, 1), GCID(4; 1, 0, 1; 1, 1, 0) (see [START_REF] Freund | Graph-controlled insertiondeletion systems[END_REF]) and i) GCID(5; 1, 1, 0; 1, 1, 0), ii) GCID(5; 1, 1, 0; 1, 0, 1), iii) GCID(5; 1, 1, 0; 2, 0, 0), iv) GCID(5; 1, 0, 1; 2, 0, 0), v) GCID(5; 2, 0, 0; 1, 1, 0), vi) GCID(5; 2, 0, 0; 1, 0, 1) (see [START_REF] Krassovitskiy | Computational power of insertiondeletion (P) systems with rules of size two[END_REF]) describe RE . Thus, the generative power of GCID(4; 1, 1, 0; 1, 0, 0), GCID(4; 1, 0, 1; 1, 0, 0), GCID(5; 1, 1, 0; 1, 0, 0), GCID(5; 1, 0, 1; 1, 0, 0) is open. In the following, we discuss the power of these systems.

Remark 2. As in Remark 1, one can see that the Kleene star of each of the linear languages lies in GCID(4; 1, 1, 0; 1, 0, 0) ∩ GCID(4; 1, 0, 1; 1, 0, 0). Inheriting the proof idea of Theorem 6, we deduce the following from Theorem 9, 10: Theorem 11. MLIN ∈ GCID(5; 1, 1, 0; 1, 0, 0) ∩ GCID(5; 1, 0, 1; 1, 0, 0).

Conclusions

We have studied GCID systems of various small sizes, proving them to be either computationally complete or able to simulate at least all (meta-)linear languages. Example 2 shows (together with [START_REF] Verlan | Recent developments on insertion-deletion systems[END_REF]) that two components are more powerful than one for systems of size (1, 1, 1; x, y, z) with y + z ≤ 1, x ∈ {0, 1}. Proving a non-trivial simulation result for the family of context-free languages (say, by GCID systems with size (3; 1, 1, 0; 1, 1, 0)) is left open. Also, we have indicated how to simulate Kleene closures of meta-linear languages; it would be therefore interesting to see if the regular closure of the linear languages can be also simulated; refer to [START_REF] Kutrib | Finite turns and the regular closure of linear contextfree languages[END_REF] for details of this language class.

The underlying control graph of a k-GCID system Π is defined to be a graph with k nodes labelled C1 through Ck. There exists a directed edge from Ci to Cj if and only if there exists a rule of the form (i, r, j) in R of Π. If the undirected simple graph corresponding to this underlying directed graph is a tree, then Π can be viewed as an insertion-deletion P system (see [START_REF] Freund | Graph-controlled insertiondeletion systems[END_REF]). In this paper, the underlying graphs of the GCID systems that simulate the families RE and LIN (in Theorems 2, 4 and 5) are trees. Hence, the corresponding results can be immediately also read as results on insertion-deletion P systems. However, one may note that the control graph of the construction of Theorem 9 contains a triangle (q1.3 leads from C1 to C2, q2.1 from C2 to C3 and q3.1 from C3 to C1 in the proof of Theorem 9) and is hence not a tree. Whether or not similar results hold for insertion-deletion P systems remains open. The control graphs of the graph-controlled ins-del systems discussed in this paper are visualized in Figures 1 and2 for the case of Theorem 2 and 9, respectively. The annotations given on the edges tells what part of the simulation is responsible for this edge. The according pictures of the simulations in the metalinear cases are even a bit more involved (as we have four components in the first part of Theorem 6) and is hence omitted. However, as there are only connections betweeen C1 and C2, betweeen C2 and C3, and betweeen C3 and C4, this corresponds again to an insertion-deletion P system.

C2 C1 C3

p, q, f, g p, q, f, g p, q, f, g p, q, f, g h p, q Fig. 1. Control graph structure of Theorem 2; the corresponding simple undirected graph is a path on three vertices, which corresponds to three nested membranes.

C2 C1 C3

p, q p, q p, q p, q, f p, q, f Fig. 2. Control graph structure of Theorem 9; the corresponding simple undirected graph is a cycle on three vertices, which cannot correspond to any nested membrane structure.

r1. 1 :

 1 (1, (λ, a, S) ins , 2) r1.2 : (1, (λ, S, λ) del , 3) r2.1 : (2, (λ, b, S ) ins , 1) r3.1 : (3, (λ, S, S ) ins , 1) r3.2 : (3, (λ, S , λ) del , 1)

  3.1 : (3, (S 2 , r 1→2 , λ) ins , 4) r 1→2 3.2 : (3, (r 1→2 , S 2 S 3 , λ) ins , 2) r 1→2 4.1 : (4, (λ, S 2 , λ) del , 3), Similar transition rules are added to start simulations of G 3 , . . . , G k-1 . Finally, we have the rules: r k-1→k 2.1 : (2, (λ, r k-1→k , λ) del , 1) r k-1→k 3.1 : (3, (S k , r k-1→k , λ) ins , 4) r k-1→k 3.2 : (3, (r k-1→k , S k , λ) ins , 2) r k-1→k 4.1 : (4, (λ, S k , λ) del , 3),

  The set of rules R of Π is defined as follows. We simulate the rule p : X → Y a by the following ins-del rules:

	p1.1 : (1, (X, p, λ) ins , 3),	p1.2 : (1, (p, a, λ) ins , 2),	p1.3 : (1, (p , Y, λ) ins , 2)
	p2.1 : (2, (p, p , λ) ins , 3),	p2.2 : (2, (λ, p , λ) del , 1)
	p3.1 : (3, (λ, X, λ) del , 1),	p3.2 : (3, (λ, p, λ) del , 1)

Acknowledgement

The second author would like to acknowledge the project SR/S3/EECE/054/2010, Department of Science and Technology, New Delhi, India.


Laurette Marais

Lynette Van Zijl

Unary Self-Verifying Symmetric Difference Automata

We investigate self-verifying nondeterministic finite automata, in the case of unary symmetric difference nondeterministic finite automata (SV-XNFA). We show that there is a family of languages L n≥2 which can always be represented non-trivially by unary SV-XNFA. We also consider the descriptional complexity of unary SV-XNFA, giving an upper and lower bound for state complexity.

Introduction

Any nondeterministic finite automaton (NFA) has an equivalent deterministic finite automaton (DFA) which can by found by applying the subset construction [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF]. This subset construction uses the union set operation. Symmetric difference NFA (XNFA), on the other hand, employ the symmetric difference set operation [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF] during the determinisation process with the subset construction. XNFA may also be considered as a special case of weighted automata over GF [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF] [START_REF] Van Der Merwe | Minimal DFA for symmetric difference NFA[END_REF]. XNFA, even in the unary case, are interesting because of the different descriptional complexity when compared to traditional NFA. For example, an n-state unary XNFA may have an equivalent minimal DFA with 2 n -1 states, whereas the bound is e Θ √ n ln n in the case of NFA [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF]. In this work, we consider selfverification for XNFA.

Self-verifying NFA (SV-NFA) [START_REF] Assent | An upper bound for transforming self-verifying automata into deterministic ones[END_REF][START_REF] Hromkovič | On the power of Las Vegas II. Two-way finite automata[END_REF][START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF] are automata with two kinds of final states, namely, accept states and reject states. Each path in the automaton may reach either an "Accept", "Reject" or "I do not know" state. Once a path has been found that either accepts or rejects, it is guaranteed that no other path with the same label will reach the opposite answer. Furthermore, every word is guaranteed one path that reaches either an accept or a reject state. Consequently, unlike with NFA, rejection is the result of reaching a reject state, and not the result of a failure to reach an accept state.

Assent and Seibert [START_REF] Assent | An upper bound for transforming self-verifying automata into deterministic ones[END_REF] showed that any n-state SV-NFA has an equivalent DFA with O(2 n / √ n) states. Jirásková and Pighizzini [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF] improved their result, and showed a tight upper bound h(n), where h(n) grows like 3 n 3 , for an SV-NFA with a binary alphabet. In the unary case, it was shown that the upper bound of e Θ √ n ln n is not tight for unary SV-NFA. In this article, we define self-verifying XNFA (SV-XNFA), and consider the case of unary SV-XNFA. We show the existence of a family of languages accepted by unary SV-XNFA, and point out some conditions for the existence of n-state unary SV-XNFA. We also give an upper bound and lower bound for the state complexity.

Preliminaries

An NFA N is a five-tuple N = (Q, Σ, δ, Q 0 , F ), where Q is a finite set of states, Σ is a finite alphabet, δ : Q×Σ → 2 Q is a transition function (here, 2 Q indicates the power set of Q), Q 0 ⊆ Q is a set of initial states, and F ⊆ Q is the set of final (acceptance) states. The transition function δ can be extended to strings in the Kleene closure Σ * of the alphabet: δ (q, w 0 w 1 . . . w k ) = δ(δ(. . . δ(q, w 0 ), w 1 ), . . . , w k ) .

For convenience, we write δ(q, w) to mean δ (q, w). An NFA N is said to accept a string w ∈ Σ * if q 0 ∈ Q 0 and δ(q 0 , w) ∈ F , and the set of all strings (also called words) accepted by N is the language L(N ) accepted by N . Any NFA has an equivalent DFA which accepts the same language. The DFA equivalent to a given NFA can be found by the subset construction [START_REF] Hopcroft | Introduction to automata theory, languages, and computation[END_REF]. In essence, the subset construction keeps track of all the states that the NFA may be in at the same time, and forms the states of the equivalent DFA by grouping of the states of the DFA. In short,

δ(A, σ) = q∈A δ(q, σ)
for any A ⊆ Q and σ ∈ Σ.

An XNFA M = (Q, Σ, δ, Q 0 , F ) is defined similarly to an NFA, with the difference that the XNFA accepts a string w ∈ Σ * if q 0 ∈ Q 0 , and |δ(q 0 , w) ∩ F | is odd. This acceptance condition reflects the parity nature of the XNFA, so that a string is accepted when there is an odd number of paths which lead to final states [START_REF] Vuillemin | Compact normal form for regular languages as XOR automata[END_REF]. This definition of acceptance ensures that an XNFA can be seen as a special case of a weighted automaton [START_REF] Van Der Merwe | Minimal DFA for symmetric difference NFA[END_REF]. When the subset construction is applied to find the DFA equivalent to the XNFA, the symmetric difference (in the set theoretic sense) is used to reflect the parity of the paths. That is,

δ(A, σ) = q∈A δ(q, σ) for any A ⊆ Q and σ ∈ Σ.
For clarity, the DFA equivalent to an XNFA N is termed an XDFA and denoted with N D (with corresponding Q D , δ D etc).

It was shown (amongst others) in [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF][START_REF] Vuillemin | Compact normal form for regular languages as XOR automata[END_REF] that XNFA can be investigated by considering them as linear machines over the Galois field GF [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF]. We also use that approach in this work. Consider the transition table of a unary XNFA N = (Q, Σ, δ, Q 0 , F ), where each row represents a mapping from a state q ∈ Q to a set of states P ∈ 2 Q . Then P can be written as a vector with a one in position i if q i ∈ P , and a zero in position i if q i ∈ P . Hence, the transition table can be represented as a matrix of zeroes and ones (see Example 1). This is known as the characteristic or transition matrix of the XNFA.

Initial and final states can be represented by vectors, and appropriate vector and matrix multiplications over GF [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF] represent the behaviour of the XNFA3 . For more detail, see for example [START_REF] Van Der Merwe | Minimal DFA for symmetric difference NFA[END_REF]. For the purposes of this work, we consider only unary XNFA with one alphabet symbol. In general, for larger alphabets, there is a matrix associated with each alphabet symbol.

Let M be the characteristic matrix of N . The characteristic polynomial c(X) of M is given by det(M -IX), and c(X) is said to be the characteristic polynomial of N .

Note that the characteristic matrix of an XNFA does not contain information about the choice of initial and final states, so in fact any such matrix represents a set of XNFA sharing a transition graph but differing in choice of initial and final states. A characteristic polynomial is associated with the matrix, but many matrices may share the same polynomial, so a polynomial over GF(2) represents a set of characteristic matrices. A useful result from linear field theory [START_REF] Stone | Discrete mathematical structures and their applications[END_REF] states that any monic polynomial c(X) = X n + c n-1 X n-1 + . . . c 2 X 2 + c 1 X + c 0 over GF(2) has a so-called companion matrix (also called a normal form matrix) M of the form

M =        0 0 . . . 0 c 0 1 0 . . . 0 c 1 0 1 . . . 0 c 2 . . . . . . . . . . . . 0 0 . . . 1 c n-1        .
Thus, given a polynomial over GF [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF], it is possible to construct its companion matrix directly, and then construct an XNFA from the companion matrix. Such an XNFA will have the transition function δ(q i , a) = q i+1 for 0 ≤ i < n -1, and q j ∈ δ(q n-1 , a) for all j such that c j = 0.

Finally, each c(X) over GF(2) is associated with a certain cycle structure. Specifically, given a unary XNFA N , the properties of its characteristic polynomial c(X) allow conclusions about the possible length of the cycle of states of the equivalent XDFA N D (see for example [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF][START_REF] Stone | Discrete mathematical structures and their applications[END_REF][START_REF] Dornhoff | Applied modern algebra[END_REF]). Theorem 1. [START_REF] Stone | Discrete mathematical structures and their applications[END_REF] Let c(X) be a polynomial of degree n over GF(2) that does not have X as a factor. [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF], consider its factors. For each cycle of length k i induced by factor φ i (X) and for each cycle of length k j induced by factor φ j (X), c(X) has gcd(k i , k j ) cycles of length lcm(k i , k j ).

-If c(X) is a primitive irreducible polynomial over GF(2), then c(X) has a single cycle of length 2 n -1. -If c(X) is an irreducible but not primitive polynomial over GF(2), then c(X) has (2 n -1)/b cycles of length b, where b is a factor of 2 n -1. -If c(X) is a reducible polynomial over GF
The choice of initial states for N determines which cycle in the cycle structure of c(X) represents the equivalent XDFA N D . We give an example of an XNFA to illustrate the discussion above.

Example 1. Let N be an XNFA where Q = {q 0 , q 1 , q 2 , q 3 }, Σ = {a}, Q 0 = {q 0 }, F = {q 1 , q 3 } and δ is defined in Table 1 (start states are indicated by →, and final states by ←). This corresponds to the matrix M below and characteristic polynomial c(X) = X 4 + X 3 + X + 1.

M =     0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1     Table 1. Transition function of N δ a → q0 q1 ← q1 q2 q2 q3 ← q3 q0, q1, q3 Table 2. Transition function of ND δD a → [q0] [q1] ← [q1] [q2] [q2] [q3] ← [q3] [q0, q1, q3] [q0, q1, q3] [q0, q2, q3] ← [q0, q2, q3] [q0]
The transition function δ D of the equivalent XDFA N D is shown in Table 2 and N D is shown in Fig. 1. Note that [q 0 , q 1 , q 3 ] / ∈ F D , since it contains an even number of states from F . We now recap the definition of SV-NFA:

Definition 1. [4, 6] A self-verifying nondeterministic finite automaton (SV- NFA) is a 6-tuple N = (Q, Σ, δ, Q 0 , F a , F r )
, where Q, Σ, δ and Q 0 are defined as for standard NFA. Here, F a ⊆ Q and F r ⊆ Q are the sets of accept and reject states, respectively. The remaining states, that is, the states belonging to Q \ (F a ∪ F r ), are called neutral states. For each input string w in Σ * , it is required that there exists at least one path ending in either an accept or a reject state; that is, δ(q 0 , w)∩(F a ∪F r ) = ∅ for any q 0 ∈ Q 0 , and there are no strings w such that both δ(q 0 , w) ∩ F a and δ(q 1 , w) ∩ F r for any q 0 , q 1 ∈ Q 0 are nonempty.

Unlike an NFA, an SV-NFA leads to an explicit answer state for any string w ∈ Σ * . Hence, its equivalent DFA must do so too. The path for each w in a DFA is unique, so each state in the DFA is an accept or reject state. Hence, for any DFA state d, there is some SV-NFA state q r ∈ d such that q r ∈ F a so that d ∈ F a D or q r ∈ F r so that d ∈ F r D . Since each state in the DFA is a subset of states of the SV-NFA, accept and reject states cannot occur together in a DFA state. That is, if d is a DFA state, then for any p, q ∈ d, if p ∈ F a then q / ∈ F r and vice versa.

Combining the notions of SV-NFA and XNFA, we now define SV-XNFA.

Definition 2. A self-verifying symmetric difference finite automaton (SV-XNFA) is a 6-tuple N = (Q, Σ, δ, Q 0 , F a , F r )
, where Q, Σ, δ and Q 0 are defined as for XNFA, and F a and F r are defined as for SV-XNFA. That is, each state in the SV-XDFA equivalent to N must contain an odd number of states from either F a or F r , but not both.

Note that the acceptance condition for SV-XNFA (or the SV condition) implies that if a state in the SV-XDFA of an SV-XNFA N contains an odd number of states from F a , it may also contain an even number of states from F r , and so belongs to F a D , and vice versa. Parity is not applied to neutral states, so that any state in the XDFA may contain any number of neutral states from N .

The choice of F a and F r for a given SV-XNFA N is called an SV-assignment of N . An SV-assignment where either F a or F r is empty, is called a trivial SVassignment. Otherwise, if both F a and F r are nonempty, the SV-assignment is non-trivial. Definition 3. Let N be an XNFA. A non-trivial SV-assignment for N such that L(N ) = ∅ and L(N ) = Σ * , is called an interesting SV-assignment. An SV-XNFA with an interesting SV-assignment is called an interesting SV-XNFA.

Example 2. Let N be an XNFA where Q = {q 0 , q 1 , q 2 , q 3 , q 4 }, Σ = {a}, Q 0 = {q 0 , q 1 } and δ is defined in Table 3.

The transition function δ D of the equivalent XDFA is shown in Table 4. Then F a = {q 2 , q 4 } and F r = {q 0 } is an interesting SV-assignment. The resulting SV-XDFA N D is shown in Fig. 2. We see that F a D = {[q 1 , q 2 ], [q 2 , q 3 ], [q 3 , q 4 ], [q 1 , q 4 ]}, since these states each contain one state from F a . Similarly, it holds that F r D = {[q 0 , q 1 ], [q 0 , q 1 , q 2 , q 4 ], [q 0 , q 3 ]}, since each state contains q 0 . Note that [q 0 , q 1 , q 2 , q 4 ] contains even number of states from F a .

We now investigate when interesting SV-assignments are possible for unary XNFA. Consider any unary XNFA N and its corresponding transition matrix M over GF [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF]. Then M can be either singular, or non-singular. If M is singular, it is known [START_REF] Stone | Discrete mathematical structures and their applications[END_REF] that the XDFA N D equivalent to N forms a state graph with a transient head followed by a cycle. If M is non-singular, then N D forms a cycle.

a ← [q1, q2] [q2, q3] a ← [q2, q3] [q3, q4] a ← [q3, q4] [q0, q1, q2, q4] r ← [q0, q1, q2, q4] [q0, q3] r ← [q0, q3] [q1, q4] a ← [q1, q4] [q0, q1] q0, q1 start q1, q2 q2, q3 q3, q4 q1, q4 q0, q3 q0, q1, q2, q4
In the rest of this article, we only consider unary XNFA whose transition matrices are non-singular. By Lemma 1 below, this means we only consider polynomials over GF(2) that do not have X as a factor. Noting the correspondence between a given XNFA, its matrix representation over GF [START_REF] Van Zijl | Generalized nondeterminism and the succinct representation of regular languages[END_REF], and the corresponding characteristic polynomial c(X), we investigate whether there are properties of polynomials that guarantee the existence or non-existence of SV-assignments for XNFA with certain characteristic polynomials. We are specifically interested in finding properties that will guarantee the existence of SV-XNFA with n states that accept languages that require n D > n states in the equivalent SV-XDFA. This implies that we focus on interesting SV-assignments when determining the existence of SV-XNFA for certain polynomials.

Lemma 1. The companion matrix of a polynomial over GF(2) is singular if and only if X is a factor of the polynomial.

Proof. Let c(X) be some polynomial over GF(2) of degree n. If and only if X is a factor of c(X), then the coefficient of X 0 is zero, and so in the companion matrix, M 0,n-1 = 0. Then det(M ) = 0, which implies that M is singular [START_REF] Dornhoff | Applied modern algebra[END_REF]. Theorem 2. There is no n-state SV-XNFA such that its characteristic polynomial is primitive and irreducible.

Proof. Let N = (Q, Σ, δ, Q 0 , F ) be an n-state unary XNFA with characteristic polynomial c(X). If c(X) is primitive and irreducible, then the XDFA N D forms a cycle of length 2 n -1. Each state in the cycle is a non-empty subset of Q. If there are 2 n -1 states, then every non-empty subset of Q is a state in the XDFA, including the state consisting of all the states in Q.

Since each q ∈ Q appears as a state in the cycle, each q must either be an accept or reject state. There are two cases to consider. If n is even, then the state consisting of all the states in Q contains either an even number of accept states and an even number of reject states, or an odd number of accept states and an odd number of reject states. In either case the SV condition is violated, since each SV-XDFA state must contain an odd number of either F a or F r , but not both.

On the other hand, if n is odd, then -in order for the state consisting of all the states in Q to be either accepting or rejecting -some A ⊂ Q where |A| is odd must contain, say, the accepting states, while Q \ A contains the rejecting states and |Q \ A| is even. But the XDFA also contains a state consisting of Q \ A, that is a state consisting entirely of an even number of reject states. Hence if n is odd, this necessarily results in a neutral state in the XDFA, which again violates the SV condition. Therefore, no SV-XNFA is possible.

Note that Theorem 2 excludes all SV-assignments for primitive polynomials, including trivial or uninteresting SV-assignments. On the other hand, we now prove that for a certain family of polynomials, interesting SV-assignments are always possible. Theorem 3. Let c(X) = X n + X n-1 + X + 1, with companion matrix M , and let N be an XNFA with transition matrix M and Q 0 = {q 0 }. Then N has an interesting SV-assignment, and the equivalent XDFA N D forms a cycle of length 2n -2.

Proof. The transition function of N is given in Table 5. Since δ(q i , a) = q i+1 for all i < n -1, the XDFA N D contains the states [q 0 ], [q 1 ], ..., [q n-1 ] in its cycle. Also, δ(q n-1 , a) = {q 0 , q 1 , q n-1 }. Now, δ({q 0 , q i , q n-1 }, a) = {q 0 , q i+1 , q n-1 } for 1 ≤ i ≤ n -3, since δ({q 0 , q i , q n-1 }, a) = {q 1 } ⊕ {q i+1 } ⊕ {q 0 , q 1 , q n-1 } = {q 0 , q i+1 , q n-1 }, as q i+1 = q n-1 for 1 ≤ i ≤ n-3. However, δ({q 0 , q n-2 , q n-1 }, a) = {q 1 }⊕{q n-2+1 }⊕{q 0 , q 1 , q n-1 } = {q 0 }. Therefore, N D contains [q 0 ], [q 1 ], ..., [q n-1 ] and [q 0 , q i , q n-1 ] for 1 ≤ i ≤ n -2, and hence has n + n -2 = 2n -2 states. Now, since every state in N D has odd size, any choice of F a and F r so that F a ∪ F r = Q and F a ∩ F r = ∅ with F a and F r non-empty will guarantee that Table 5.

Transition function of N with c(X) = X n + X n-1 + X + 1 δ a q0 q1 q1 q2 . . . . . . qn-2 qn-1 qn-1 q0, q1, qn-1
each state in the XDFA contains an odd number of states from either F a or F r and zero or an even number of states from the other, and hence will be a non-trivial SV-assignment. Since [q 0 ], [q 1 ], ..., [q n-1 ] ∈ Q D , it will also necessarily be an interesting SV-assignment.

Languages for unary SV-XNFA

Given the existence of SV-XNFA for certain c(X) as shown above, we may now consider whether there is a family of languages L n≥2 such that each L i may be represented by an SV-XNFA in a non-trivial way. That is, we consider whether there are languages that may be represented by SV-XNFA with n states that require n D > n states in their equivalent SV-XDFA. The next theorem presents such a language family. Theorem 4. For any integer n ≥ 2, let L n = a (2n-2)i+j , for i ≥ 0 and 0 ≤ j < n -1, and L c n = a (2n-2)i+j , for i ≥ 0 and n -1 ≤ j < 2n -2. Then there exists a pair of SV-XNFA with n states and the same transition graph that accept L n and L c n respectively. Moreover, these languages each require an SV-XDFA with 2n -2 states.

Proof. Using the construction given in the proof of Theorem 3, we construct N with n states so that N D has 2n-2 states. The states in the SV-XDFA are given in Figure 3.

Then

F a = {q i |0 ≤ i ≤ n -2} and F r = {q n-1 } is an interesting SV- assignment. Consequently, d 0 , d 1 , ..., d n-2 ∈ F a D and d n-1 , d n , ..., d 2n-3 ∈ F r D
, so the language accepted by N is L n = a (2n-2)i+j , for i ≥ 0 and 0 ≤ j < n -1. Since this pattern of n -1 accept states followed by n -1 reject states requires 2n -2 states, N D is the minimal SV-XDFA that accepts L n .

Also,

F r = {q i |0 ≤ i ≤ n -2} and F a = {q n-1 } is an interesting SV- assignment that would cause d 0 , d 1 , ..., d n-2 ∈ F r D and d n-1 , d n , ..., d 2n-3 ∈ F a D so that N accepts L c n = a (2n-2)i+j , for i > 0 and n -1 ≤ j < 2n -2.
Similarly as for L n , 2n -2 states are required to accept L c n . This leads to a pair of SV-XNFA with n states and the same transition graphs that accept L n and L c n respectively, while in the deterministic case, an SV-XDFA with at least 2n -2 states is required. The ability of self-verifying automata to represent complementary pairs of languages using the same transition graph is discussed in [START_REF] Geffert | Pairs of complementary unary languages with "balanced" nondeterministic automata[END_REF].

d0 = [q0] d1 = [q1] . . . dn-2 = [qn-2] dn-1 = [qn-1] dn = [q0, q1, qn-1] dn+1 = [q0, q2, qn-1] . . . d2n-3 = [q0, qn-2, qn-1]

Descriptional complexity of unary SV-XNFA

We now turn to the question of state complexity for SV-XNFA. By Theorem 1, the maximum cycle length for any c(X) of degree n is 2 n -1, and therefore this is an upper bound for the number of states in the equivalent XDFA of any XNFA with n states. However, it is not a tight upper bound for SV-XNFA, because this cycle length is only achieved if c(X) is primitive and from Theorem 2 it is clear such XDFA cannot have SV-assignments. Instead, we show in this section that for certain c(X) of degree n, there exist SV-XNFA with characteristic polynomial c(X) for which the equivalent SV-XDFA have at least 2 n-1 -1 states, and that for any n ≥ 2, there is a language L n that can be represented by an n-state SV-XNFA while requiring an (2 n-1 -1)-state SV-XDFA. Lemma 2. Let c(X) = (X + 1)φ(X) be a polynomial of degree n with nonsingular companion matrix M , and let N be an XNFA with transition matrix M and Q 0 = {q 0 }. Then the equivalent XDFA N D has the following properties:

1. |Q D | > n 2. |d| is odd for d ∈ Q D 3. [q 0 ], [q 1 ], ..., [q n-1 ] ∈ Q D Proof.
Since X + 1 is a factor, 1 is a root of the polynomial, and so c(X) must have an even number of terms, including X 0 . The companion matrix M of c(X) is

M =             0 0 0 • • • 0 0 c 0 1 0 0 • • • 0 0 c 1 0 1 0 • • • 0 0 c 2 . . . . . . . . . . . . . . . . . . 0 0 0 • • • 1 0 c n-2 0 0 0 • • • 0 1 c n-1            
.

The last column contains an odd number of 1's, representing an odd number of transitions from state q n-1 . That is, δ(q n-1 , a) = {q c |c ∈ C} = Q c where |C| is odd.

Since δ(q i , a) = q i+1 for all i < n-1, N D contains the states [q 0 ], [q 1 ], ..., [q n-1 ], as well as [Q c ], and therefore forms a cycle with at least n+1 states. These states all have odd size, so it only remains to show that all other states in the cycle must have odd size as well.

Let P = {q i0 , q i1 , ..., q i k } ⊆ Q where k is even and so |P | is odd. Then if i j < n -1 for all 0 ≤ j ≤ k, then δ(P, a) = {q i0+1 , q i1+1 , ..., q i k +1 }, and so |δ(P, a)| must be odd as well. However, suppose q n-1 ∈ P . We may assume that q n-1 = q i k . Let P = {q i0+1 , q i1+1 , ..., q i k }, so |P | = |P | -1 and therefore even. Then δ(P, a)

= P ⊕ Q c . Let m = |P ∩ Q c |. Then |δ(P, a)| = |P | + |Q c | -2m. Since |P | is even, |Q c |
is odd and 2m is even, it follows that |δ(P, a)| is odd.

Therefore, any state with odd size in N D transitions to a state with odd size, and so all the states in the XDFA cycle have odd size.

Theorem 5. Let c(X) = (X + 1)φ(X) be a polynomial of degree n with nonsingular companion matrix M . Then there is an XNFA N with transition matrix M and Q = {q 0 } for which there is an interesting SV-assignment.

Proof. From Lemma 2 it follows that the XNFA N whose transition matrix is the companion matrix of c(X) has a cycle with length greater than n in which each state has odd size. Furthermore, [q 0 ], [q 1 ], ..., [q n-1 ] are all states in Q D , so q 0 , q 1 , ..., q n-1 must all be in either F a or F r .

Therefore, any choice of F a and F r so that F a ∪ F r = Q and F a ∩ F r = ∅ with F a and F r non-empty will guarantee that each state in the XDFA contains an odd number of states from either F a or F r and zero or an even number of states from the other, and hence will be an interesting SV-assignment. Lemma 3. Let c(X) = (X + 1)φ(X) be a polynomial of degree n with nonsingular companion matrix M and where φ(X) is a primitive polynomial. Let N be an XNFA with transition matrix M and Q 0 = {q 0 }, then N D forms a cycle of length 2 n-1 -1.

Proof. We calculate the number and lengths of all cycles for c(X). By Theorem 1, factors X + 1 and φ(X) each induce a single cycle of length 2 m -1 with m = 1 and m = n -1 respectively, as well as a single cycle each of length 1, which is the so-called empty cycle ε. Therefore c(X) has the following cycles:

-ε X+1 and X + 1: gcd(1, 1) cycle(s) of length lcm(1, 1) -ε φ(X) and X + 1: gcd(1, 1) cycle(s) of length lcm(1, 1) -ε X+1 and φ(X): gcd(1, 2 n-1 -1) cycle(s) of length lcm(1, 2 n-1 -1) -ε φ(X) and φ(X): gcd(1, 2 n-1 -1) cycle(s) of length lcm(1, 2 n-1 -1) Therefore, c(X) has two cycles of length 1, one of which is ε c(X) , and two cycles of length 2 n-1 -1. By Lemma 2, N D must be a cycle with length greater than n, so it must have length 2 n-1 -1. Theorem 6. For any n ≥ 2, there is an interesting SV-XNFA N whose equivalent N D has 2 n-1 -1 states.

Proof. Let c(X) = (X + 1)φ(X) be a polynomial of degree n, where φ(X) is a primitive polynomial, and let M be its non-singular companion matrix. Let N be an XNFA with transition matrix M and let Q 0 = {q 0 }. By Theorem 5, N has an interesting SV-assignment, and by Lemma 3, the equivalent N D has 2 n-1 -1 states.

The following theorem shows that, for any n ≥ 2, there exists an n-state SV-XNFA that accepts a language requiring at least 2 n-1 -1 states in an equivalent SV-XDFA. Theorem 7. For any n ≥ 2, there is a language L n so that some n-state SV-XNFA accepts L n and the minimal SV-XDFA that accepts L n has 2 n-1 -1 states.

Proof. Let c(X) = (X + 1)φ(X) where φ(X) is a primitive polynomial and let c(X) have degree n. We construct an SV-XNFA N with n states whose equivalent N D has 2 n-1 -1 states as in Theorem 6, and let F a = {q 0 } and F r = Q \ F a . Then L = a (2 n-1 -1)i+j for i ≥ 0 and j ∈ J, where J is some set of integers. Now, from the transition matrix of N it follows that 0, n ∈ J, while 1, 2, ..., n -1 / ∈ J, since q 0 ∈ δ(q 0 , a n ) and q 0 / ∈ δ(q 0 , a m ) for m < n. If there is an N D with fewer than 2 n-1 -1 states that accepts L, then there must be some d j = {q 0 } ∈ Q D such that q 0 ∈ d j , q 0 ∈ δ(d j , a n ) and there is no m < n so that q 0 ∈ δ(d j , a m ).

Let d k be any state in N D such that d k = {q 0 }. Let max(d k ) be the largest subscript of any SV-XNFA state in d k . Then max(d k ) > 0. Let m = n-max(d k ), so m < n, then from the transition matrix of N it follows that q 0 ∈ δ(d k , a m ). That is, for any d k there is an m < n so that q 0 ∈ δ(d k , a m ).

Therefore, there is no N D with fewer than 2 n-1 -1 states that accepts L.

This gives a lower bound of 2 n-1 -1 for the state complexity of unary SV-XNFA.

Conclusion

We introduced the notion of unary self-verifying symmetric difference automata, and showed that for certain polynomials, interesting SV-XNFA exist. We also showed that for primitive polynomials, no SV-assignments for unary XNFA are possible. This provides an upper bound of 2 n -1 on the state complexity of unary SV-XNFA that is known not to be tight. Furthermore, we demonstrated that 2 n-1 -1 is a lower bound for unary SV-XNFA. Directions for future work include determining a tight bound, as well as providing a more detailed exposition of the properties of polynomials over GF(2) that lead to SV-assignments, and especially interesting SV-assignments. Also, further consideration may be given to the question of which languages can be represented succinctly by SV-XNFA.

Fig. 1 .

 1 Fig. 1. Example 1: ND

Fig. 2 .

 2 Fig. 2. Example 2: ND

Fig. 3 .

 3 Fig. 3. Theorem 4: states in the SV-XDFA

Table 3 .

 3 Transition function of N

		δ	a
	r	q0 q1
		→ q1 q2
	a ← q2 q3
		q3 q4
	a ← q4 q0, q1, q2

Table 4 .

 4 Transition function of ND

		δD	a
	r	[q0, q1]	[q1, q2]

In GF(2), 1 + 1 = 0.