Turlough Neary
email: tneary@ini.phys.ethz.ch

2-state 2-symbol Turing Machines with Periodic Support Produce Regular Sets

We say that a Turing machine has periodic support if there is an infinitely repeated word to the left of the input and another infinitely repeated word to the right. In the search for the smallest universal Turing machines, machines that use periodic support have been significantly smaller than those for the standard model (i.e. machines with the usual blank tape on either side of the input). While generalising the model allows us to construct smaller universal machines it makes proving decidability results for the various state-symbol products that restrict program size more difficult. Here we show that given an arbitrary 2-state 2-symbol Turing machine and a configuration with periodic support the set of reachable configurations is regular. Unlike previous decidability results for 2-state 2-symbol machines we included in our consideration machines that do not reserve a transition rule for halting, which further adds to the difficulty of giving decidability results.

Introduction

The search for Turing machines with small states-symbol products has received attention for a number of different variations of the model [START_REF] Cook | Universality in elementary cellular automata[END_REF][START_REF] Neary | The complexity of small universal Turing machines: a survey[END_REF][START_REF] Wagner | Universelle Turingmaschinen mit n-dimensionale band[END_REF][START_REF] Watanabe | 5-symbol 8-state and 5-symbol 6-state universal Turing machines[END_REF]. The variant that has received the most attention is what we call here the standard model [START_REF] Baiocchi | Three small universal Turing machines[END_REF][START_REF] Minsky | Size and structure of universal Turing machines using tag systems[END_REF][START_REF] Neary | Four small universal Turing machines[END_REF][START_REF] Rogozhin | Small universal Turing machines[END_REF] (single-tape Turing machines with the usual blank symbol and a specially reserved halt instruction). As one might expect if we generalise the standard model or the type of encoding it may use we can give machines with smaller state-symbol products. One generalisation used in the literature is to allow periodic support (an infinitely repeated word to the left of the input and another infinitely repeated word to the right). Universal machines that use such a generalisation are call weakly universal. Watanabe gave a number of small semi-weakly universal machines [START_REF] Watanabe | 5-symbol 8-state and 5-symbol 6-state universal Turing machines[END_REF] (a repeated word only appears on one side of the input). Later, Cook [START_REF] Cook | Universality in elementary cellular automata[END_REF] gave small weakly universal machines that simulate the cellular automaton Rule 110, and these were improved upon in [START_REF] Neary | Small weakly universal Turing machines[END_REF] to give weakly universal machines for the state-symbol pairs of (6, 2), [START_REF] Hermann | The uniform halting problem for generalized one state Turing machines[END_REF][START_REF] Hermann | The uniform halting problem for generalized one state Turing machines[END_REF] and [START_REF] Cook | Universality in elementary cellular automata[END_REF][START_REF] Kudlek | Small deterministic Turing machines[END_REF].

For the standard model a number of authors have given lower bounds on the size of the smallest possible universal Turing machines by proving the halting problem decidable for machines with the following state-symbol pairs: (2, 2) [START_REF] Kudlek | Small deterministic Turing machines[END_REF][START_REF] Pavlotskaya | Solvability of the halting problem for certain classes of Turing machines[END_REF], [START_REF] Hermann | The uniform halting problem for generalized one state Turing machines[END_REF][START_REF] Cook | Universality in elementary cellular automata[END_REF] [10], (2, 3) (claimed by Pavlotskaya [START_REF] Pavlotskaya | Solvability of the halting problem for certain classes of Turing machines[END_REF]), (1, n) [START_REF] Hermann | The uniform halting problem for generalized one state Turing machines[END_REF] and (n, 1) (trivial), where n 1. Unfortunately, these results do not provide lower bounds relevant to the weak and semi-weak machines mentioned above, and while generalising the encoding can simplify the task of finding machines with smaller state-symbol products the task of giving decidability results becomes more difficult. In this work we give decidability results for 2-state 2-symbol machines with periodic support. Our main result is as follows:

Theorem 1. Given an arbitrary 2-state, 2-symbol, single-tape Turing machine with periodic support, the set of reachable configurations from an arbitrary configuration is regular.

This result implies the decidability of many questions for 2-state 2-symbol machines with periodic support such as (1) Will a computation halt? (2) Does word w appear on the tape during a computation? (3) Given a number x does a computation enter a repeating sequence of configurations of length x? The halting property in question 1 is the standard way of signaling the end of a computation in Turing machines. Each of the properties in ( 2) and ( 3) above have been used as a means to signal the end of a computation in universal machines [START_REF] Cook | Universality in elementary cellular automata[END_REF][START_REF] Wagner | Universelle Turingmaschinen mit n-dimensionale band[END_REF]. The weakly universal machines in [START_REF] Cook | Universality in elementary cellular automata[END_REF][START_REF] Neary | Small weakly universal Turing machines[END_REF] use the appearance of a special word to simulate a halting Turing machine and so our results show that there exists no 2-state 2-symbol weakly universal machine that ends its computation in this way. Our proof does not assume that there is a transition rule reserved for halting which further adds to the difficulty when compared to previous decidability proofs for 2-state 2-symbol machines.

The layout of the paper is as follows: In Section 2 we explain notation and give some definitions including definitions for two types of computation, periodic and semi-periodic, and we then show that if a computation is periodic or semiperiodic the set of reachable configurations is regular. In Section 3 we reduce the number of cases to be considered leaving the cases only in Figure 1 to be solved, and in Section 4 we solve the Figure 1 cases to prove Theorem 1.

Turing Machines with Periodic Support

Definition 1. A Turing machine with periodic support is a tuple M = (Q, Σ, f, l, r). Here Q = {q 1 , . . . q |Q| } and Σ are the finite sets of states and tape symbols respectively, and l, r ∈ Σ * are the left and right blank words respectively, where |r| > 0 and |l| > 0. The transition function is of the form

f : Q × Σ → Σ × {L, R} × Q.
We write f as a list of transition rules. Each transition rule is a quintuple (q x , σ 1 , σ 2 , d, q y ), with initial state q x , read symbol σ 1 ∈ Σ, write symbol σ 2 ∈ Σ, move direction d ∈ {L, R} and next state q y . Definition 2. A configuration c of a Turing machine with periodic support has the form c = u q x α v where q x is the current state, the tape head is reading the symbol α, and the words u, v ∈ Σ * .

For a machine with periodic support, when the tape head moves to the right of v the word r is appended to the right of v and when the tape head moves to the left of u the word l is prepended to the left of u. When l = r = 0 we have the classic Turing machine with blank symbol 0. We write c 1 c 2 to denote that configuration c 2 is obtained via a single Turing machine computation step on c 1 and we write c 1 * c t if there exists a sequence of 0 or more computations steps of the form c 1 c 2 . . . c t-1 c t . We say that c t is reachable from c 1 and call c 1 c 2 . . . c t-1 c t a computation sequence.

We label each Turing machine tape cell with an index. The cell with index i, which we will call cell i, has cell i -1 immediately to its left and cell i + 1 immediately to its right. The position function p(t) gives the index of the cell being read by the tape head at time t. The rightmost position up to time t is a cell index P r (t) = max t t (p(t ), p r ) and the leftmost position up to time t is a cell index P l (t) = min t t (p(t ), p l ), where p l and p r are respectively the leftmost and rightmost cells occupied by the input w.

Definition 3 (Periodic computation).

Let M be a Turing machine with periodic support. The computation of M is periodic if there is a sequence s of transition rules and a time t, such that sequence s is executed between times t + i|s| and t + (i + 1)|s| for all i ∈ N, where |s| is the number of rules in s.

Lemma 1. If a computation is periodic, then {c i |c 1 * c i } is a regular set.
Proof. After t time steps M has gone through a sequence of configurations c 1 c 2 . . . c t . There are two possible cases for the repeated sequence s, the sequence has either an equal or unequal number of left and right instructions. If there is an equal number of left and right instructions then after a further |s| time steps we get c t , c t+1 , . . . , c t+s where c t and c t+s are identical. So in this case the set of configurations reachable from c 1 is the finite regular set {c 1 , c 2 , . . . , c t+s-1 }.

If the number of left and right instructions in s are not equal, then we need only consider the case where there are more right than left instructions (as the case of more left than right instructions is symmetric). At time t we have a configuration c t = uu 1 q x,1 α 1 v 1 such that the tape head visits the leftmost symbol in u 1 but does not revisit any symbol in u. Between times t and t + s sequence s is executed giving the configuration sequence c t c t+1 . . . c t+s where c t+i = uu i q x,i α i v i for 0 i < s and c t+|s| = uu u 1 q x,1 α 1 v 1 . In configuration c t+|s| the words u 1 and v 1 must appear immediately to the left and right of the tape head position as the sequence of symbols read when executing s in the |s| time steps following c t+|s| is identical to the sequence of symbols read in the |s| time steps following c t . Since the tape head will not visit any cell to the left of the leftmost symbol in u 1 when executing s the word u is not revisited by the tape head and is not altered for the remainder of the computation. For each subsequent execution of s another u is placed on the tape and so on iteration j + 1 of s we get a configuration sequence of the form c t+|s|j c t+|s|j+1 c t+|s|j+2 . . . c t+|s|(j+1) where c t+|s|j+i = u(u ) j u i q x,i α i v i and 0 i < s. So the set of configurations reachable from c 1 is the regular set {c 1 , c 2 , . . . , c t } ∪ u i (u ) * u i q x,i α i v i where 0 i < s. Lemma 2. Let M be a 2-state, 2-symbol Turing machine with periodic support. If, when M is started on a configuration c 1 , there exists an m ∈ N such that on more than |r|2 m+1 occasions the tape head of M is over a cell P r (t) and does not visit cell P r (t) -m after time t, then the set {c i |c 1 * c i } is regular.

Proof. Let uu q x αv r be a configuration at time t with |u | = m and the tape head over cell P r (t). If no cell to the left of P r (t) -m is visited after time t, then the future computation depends only on u q x αv r . By definition of P r (t) no cell to the right of the tape head's location at symbol α has yet been read and so v r must be a suffix of r. As a result, there are only |r|2 m+1 possible values for u q x αv r . So, after |r|2 m+1 times where the tape head is over cell P r (t) and no longer visits cell P r (t) -m, there are two times t j and t k that have the same value for u q x αv r . Since the future computation depends only on u q x αv r , the sequence of transition rules executed between times t j and t k are repeated ad infinitum. So from Lemma 1 the set

{c i |c 1 * c i } is regular.
Using a similar argument to the one used in Lemma 2 we get Comment 1.

Comment 1 Let M be a 2-state, 2-symbol Turing machine with periodic support. If, when M is started on a configuration c 1 , there exists an m ∈ N such that on more than |l|2 m+1 occasions the tape head of M is over a cell P l (t) and does not visit cell P l (t) + m after time t, then the set

{c i |c 1 * c i } is regular.
Comment 2 Let M be a Turing machine with periodic support. If M started on configuration c does not make at least 2 consecutive right moves an inifinite number of times and at least 2 consecutive left moves an infinite number of times, then it either enters a loop or gives a computation of the type describe by Lemma 1 or Comment 1, and so the set of reachable configurations is regular.

Definition 4 (Semi-periodic computation). Let M be a Turing machine with periodic support. The computation of M is semi-periodic if there are 2x + 2 sequences of transition rules, s r , s l , e 1 , e 2 . . . e x , h 1 , h 2 . . . h x , such that there is a time z where the sequence

S = (s r ) i+1 e 1 (s l ) i+1 h 1 (s r ) i+1 e 2 (s l ) i+1 h 2 . . . (s r ) i+1 e x (s l ) i+1 h x
is executed between times t(i) and t(i + 1) for all i ∈ N, where

t(i) = z + (i 2 +i)x 2 (|s r | + |s l |) + i(|e 1 h 1 e 2 h 2 . . . e x h x |), f (s r ) = m, f (s l ) = -m, 0 f (e i ) < m, -m < f (h i )
0, and -m < f (S) 0 where f (s) =(number of right instructions in sequence s)-(number of left instructions in sequence s). Also, for every instruction sequence y that is a prefix of s l we have f (y) -m, and for every instruction sequence y that is a prefix of s r we have f (y) m.

Lemma 3. If a computation is semi-periodic, then {c i |c 1 * c i } is a regular set.
Proof. At time t(i) the sequence S is about to be executed by M for the (i + 1) th time. The configuration at time t(i) is given below on the left side of (1). From S in Definition 4 the execution begins with (s r ) i+1 , and so between times t(i)+|s r |k and t(i) + |s r |(k + 1) we execute the sequence s r , for 0 k i. In Equation ( 1) during the execution of each s r the tape head does not move to the left of the word u r,1 or to the right of the word v r,1 , and so since s r has more right move than left move instructions we can use an argument similar to the one used in Lemma 1 to show that after k iterations of s r (|s r |k time steps) the configuration on the right side of Equation ( 1) is produced. Continuing on, the left side of Equation (2) gives the configuration after i iterations of s r , and one further iteration of s r gives the configuration on the right. In the configuration on the right of Equation ( 2) the word v e1,1 = v r ,1 v e 1 , where v r ,1 is the length |v r,1 | -m word that appears immediately to the right of the tape head after the last s r in (s r ) i+1 has executed (recall that each s r shifts the tape head m cells to the right in the word v r,1 ). The leftmost (s r ) i+1 instruction sequence in S has now completed and so e 1 , the next sequence in S, executes.

In Equation ( 3) we show the |e 1 | times steps that complete the execution of e 1 . Before we proceed we explain the presence of the word u 1 (the length f (e 1 ) prefix of u ) that appears in the configuration on the right of Equation (3). Immediately following the execution of e 1 we execute the sequence (s l ) i+1 , and as usual we give words u l,1 and v l,1 such that during the execution of each s l the tape head does not move to the left of u l,1 or to the right of v l,1 . From Definition 4 we know that executing e 1 shifts the tape head f (e 1 ) cells to the right. So from Equation (3) after the execution of e 1 (before the first s l is about to execute) the tape head is at least f (e 1 ) cells to the right of the rightmost u subword in (u ) i+1 . For every prefix y of s l we have f (y) -m and so when executing s l the tape head does not visit cells more than m positions to the left of its initial location when it began s l . So since |u | = m and the initial tape head location is at least f (e 1 ) cells to the right of the rightmost u , the leftmost f (e 1 ) symbols in the rightmost u (i.e. the prefix word u 1 ) are not entered when executing the first s l and so we have u 1 to the left of u l,1 in Equation [START_REF] Hermann | The uniform halting problem for generalized one state Turing machines[END_REF]. Note that in Equation (3) permitting the tape head to enter cells to the left of u e1,1 when executing e 1 will not effect the value of u 1 , as it is only possible to iterate s l if u 1 is a prefix of u (see Equation ( 4)) and so the prefix value of u 1 is implied by the fact that (s l ) i+1 is executed immediately after e 1 .

u h 1 ur,1 qr,1αr,1 vr,1(v ) i v e 1 |sr |k u h 1 (u ) k ur,1 qr,1αr,1 vr,1(v ) i-k v e 1 (1)
u h 1 (u ) i ur,1 qr,1αr,1 vr,1v e 1 |sr | u h 1 (u ) i+1 ue 1 ,1 qe 1 ,1αe 1 ,1ve 1 ,1 (2)
u h 1 (u ) i+1 ue 1 ,1 qe 1 ,1αe 1 ,1ve 1 ,1 |e 1 | u h 1 (u ) i u 1 u l,1 q l,1 α l,1 v l,1 v e 2 (3)
u h 1 (u ) i u 1 u l,1 q l,1 α l,1 v l,1 v e 2 |s l |k u h 1 (u ) i-k u 1 u l,1 q l,1 α l,1 v l,1 (v ) k v e 2 (4) u h 1 ,1 q h 1 ,1 α h 1 ,1 v h 1 ,1 (v ) i+1 v e 2 |h 1 | u h 2 ur,1 qr,1αr,1vr,1v 1 (v ) i v e 2 (5)
u h n ur,1 qr,1αr,1vr,1v n (v ) i v e n |sr |k u h n (u ) k ur,1 qr,1αr,1vr,1v n (v ) i-k v e n ( 6
)
The execution of sequence (s l ) i+1 as shown in Equation ( 4) proceeds in a manner similar to that of (s r ) i+1 . The main difference is that s l has more left move than right move instructions and so each successive s l sequence begins m cells further to the left. Following the execution of (s l ) i+1 , the sequence h 1 is executed as shown in Equation ( 5). In the configuration on the left of Equation ( 5) the word u h1,1 = u h 1 u 1 u l 1 , where u l 1 is the length |u l,1 | -m word that appears immediately to the left of the tape head after the last s l in (s l ) i+1 has executed (recall each s l shifts the tape head m cells to the left in the word u l,1 ). The word v 1 that appears in the configuration on the right of Equation ( 5) is the length f (h 1 ) suffix of v and its presence can be explained in a manner similar to that of u 1 in the previous paragraph. Continuing with the execution of sequence S, on the right side of Equation ( 5) following the execution of h 1 the configuration is ready to allow the next (s r ) i+1 sequence to execute. Note that unlike the configuration on the left of Equation ( 1), the configuration on the right of Equation ( 5) has the word v 1 to the left of (v ) i . This implies that (v ) i is a prefix of v 1 (v ) i as to execute (s r ) i+1 we must have the word (v ) i to the right of v r1,1 . This prefix property holds for each v j word produced by executing a h j sequence. Similarly all words of the form (u ) i u j share a suffix that allows (s r ) i+1 to execute, where u j is a word produced by executing an e j sequence (see Equation ( 3)). Returning to Equation ( 5), at the right end of the configuration v e 2 is of the correct form to allow e 2 to execute at the end of the (s r ) i+1 scan right, and following this we once again scan left with (s l ) i+1 where u h 2 allows the execution of h 2 . So the process of scanning right with (s r ) i+1 and left with (s l ) i+1 is repeated with the n th scan right given in Equation ( 6). This continues until the sequence S is completed for the value i, whereupon S begins for i + 1. The configurations for the n th iteration of S can be obtained from the configurations for the first iteration of S simply by increasing the number of u and/or the number of v words in each configuration. So the set of configurations reachable by M is the union of the finite set of configurations before the first iteration of S and the configurations indicated in Equations ( 1) to [START_REF] Neary | Four small universal Turing machines[END_REF].

Reducing the Number of Cases through Symmetries

There are 4096 possible 2-state 2-symbol machines and in this section we show how to reduce the number of cases to the 378 machines given in Figure 1. Equation ( 7) below gives the form of an arbitrary 2-state 2-symbol Turing machine where σ i ∈ {0, 1}, d j ∈ {L, R} and q k ∈ {q a , q b }. In the sequel we denote each possible machine as a triple (Σ, D, Q) where Σ = {σ 1 , σ 2 , σ 3 , σ 4 }, D = {d 1 , d 2 , d 3 , d 4 }, and Q = {q 1 , q 2 , q 3 , q 4 }. Each Σ, D and Q has 16 possible values and here we show how to reduce the number of cases under consideration to 6, 7, and 9, respectively (see Tables 1 to 3). We do this by identifying symmetries using the notion of regular equivalent machines which we define below, and we also solve some of the simplest cases from Σ, D and Q.

q a , 0, σ 1 , d 1 , q 1 q a , 1, σ 2 , d 2 , q 2 q b , 0, σ 3 , d 3 , q 3 q b , 1, σ 4 , d 4 , q 4 (7)
Before we proceed we give some preliminary definitions and notation. Given a set with two elements {y, z} we define y = z and z = y. Given w = w 0 w 1 . . . w m ∈ {0, 1} * , we write w = w 0 w 1 . . . w m to denote the word obtained by flipping each bit w i ∈ {0, 1} in w . We define three functions g reverse , g b-flip and g s-flip each of which map a configuration c = u q x α v to another configuration as follows

g reverse (c) = v q x α u g b-flip (c) = u q x α v g s-flip (c) = u q x α v
where if w = w 0 w 1 . . . w m then w = w m w m-1 . . . w 0 .

Definition 5. Given Turing machines M and M with periodic support, we say that M and M are regular equivalent if for every computation sequence c 1 c 2 . . . c t of M there is a computation sequence g(c 1 ) g(c 2 ) . . . g(c t ) of M and vice versa, where g ∈ {g reverse , g b-flip , g s-flip }.

Showing one direction of the equivalence is sufficient to prove that a pair of machines are regular equivalent as each function from g is its own inverse. Comment 3 follows from Definition 5 as regularity is closed under g, and used with Lemma 4 reduces the number of cases for Theorem 1.

Comment 3 Let M be a Turing machine with periodic support such that the set of configurations reachable from any arbitrary configuraiton is regular. Then if Turing machines M and M are regular equivalent, for every configuration of M with periodic support, the set of configurations reachable for M is regular.

Lemma 4. Let M be an arbitrary 2-state, 2-symbol Turing machine with periodic support. Then applying any one of the mappings in Equations ( 8) to [START_REF] Pavlotskaya | Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T'juring[END_REF] to all transition rules in M gives a regular equivalent Turing machine M .

f d-flip (q x , σ, σ , D, q y ) → (q x , σ, σ , D, q y ) (

f b-flip (q x , σ, σ , D, q y ) → (q x , σ, σ , D, q y ) (

f s-flip (q x , σ, σ , D, q y ) → (q x , σ, σ , D, q y ) (

Proof. To prove this lemma we show that for each mapping on M given by Equations ( 8) to [START_REF] Pavlotskaya | Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T'juring[END_REF] there is a g ∈ {g reverse , g b-flip , g s-flip }, such that for each computation sequence c 1 c 2 . . . c t of M there is a computation sequence g(c 1 ) g(c 2 ) . . . g(c t ) of M satisfying Definition 5 (recall that it is sufficient to prove only one direction of the equivalence). For each of the translations in Equations ( 8), ( 9) and [START_REF] Pavlotskaya | Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T'juring[END_REF] we set g to g reverse , g b-flip , or g s-flip , respectively. For example, if we apply the translation in Equation ( 8) to M , then for each computation sequence c 1 c 2 . . . c t of M there is a computation sequence g reverse (c 1 ) g reverse (c 2 ) . . . g reverse (c t ) of M . Each of the three cases (i.e. applying Equations ( 8), ( 9) or ( 10)) can easily be verified using an inductive argument showing that if M gives c i c i+1 then M gives g(c i ) g(c i+1 ).

It is a straightforward matter to apply the mappings in Lemma 4 to the cases in Tables 1 to 3 to show that every case not given in the tables is regular equivalent to a case that is in the tables. Applying the mapping in [START_REF] Pavlotskaya | Solvability of the halting problem for certain classes of Turing machines[END_REF] to machines for Σ 1 , Σ 2 , Σ 3 and Σ 4 gives machines for the Σ cases (1, 1, 1, 1), (1, 1, 0, 1), (1, 1, 1, 0) and (1, 1, 0, 0) respectively1 . Applying the mapping in [START_REF] Pavlotskaya | Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T'juring[END_REF] to Σ 2 , Σ 3 and Σ 5 gives the Σ cases (0, 1, 0, 0), (1, 0, 0, 0), and (1, 0, 0, 1) respectively, and applying the mapping [START_REF] Pavlotskaya | Solvability of the halting problem for certain classes of Turing machines[END_REF] and then [START_REF] Pavlotskaya | Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T'juring[END_REF] to Σ 2 and Σ 3 gives cases (0, 1, 1, 1) and

(1, 0, 1, 1) respectively. We have now shown that 9 of the 10 possible Σ values not given in Table 1 are regular equivalent to cases in the table, and now the only case not covered is (0, 1, 0, 1). For Σ = (0, 1, 0, 1) the read symbol is the same as the write symbol for each transition rule and so it never changes the tape contents. It follows that if machines for the case (0, 1, 0, 1) enter the same cell more than twice they enter a loop and so computations for this case either loop or scan in one direction only never making 2 consecutive moves in the opposite direction and are thus covered by Comment 2. 1. The 16 possible cases for the 4 read symbols in (7) reduced to 6 cases. 2. The 16 possible cases for the 4 move values in (7) reduced to 7 cases. Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 q1 = qa q b qa qa q b q b q b q b q b q2 = q b qa q b q b qa qa q b q b q b q3 = qa qa qa q b qa q b qa qa q b q4 = qa qa q b qa q b qa qa q b qa Table 3. The 16 possible cases for the 4 next state values in [START_REF] Neary | Small weakly universal Turing machines[END_REF] reduced to 9 cases.

Σ1 Σ2 Σ3 Σ4 Σ5 Σ6 σ1 = 0 0 0 0 0 1 σ2 = 0 0 0 0 1 0 σ3 = 0 0 1 1 1 1 σ4 = 0 1 0 1 0 0 Table
D1 D2 D3 D4 D5 D6 D7 d1 = L L L R L L L d2 = L L R L L R R d3 = L R L L R L R d4 = R L L L R R L Table
Applying the mapping in [START_REF] Neary | The complexity of small universal Turing machines: a survey[END_REF] to cases D 1 to D 7 in Table 2 gives 7 regular equivalent cases. The remaining cases, (R, R, R, R) and (L, L, L, L), need not be included in Table 2 as they are covered by Comment 2.

The 16 possible cases for Q are reduced to the 9 given in Table 3 by omitting the 7 cases where q 1 = q 2 = q a or q 3 = q 4 = q b . These 7 cases are not included in Table 3 as the behaviour for these cases is easily explained. To see this note that when we have q 1 = q 2 = q a state q a is a trap state where if we enter q a we never again enter state q b and so from that point on the computation is essentially that of a 1-state 2-symbol Turing machine. Taking the case q 1 = q 2 = q a , if the pair of transition rules for q a both have the same write symbol (i.e. σ 1 = σ 2 ) or shift direction (i.e. d 1 = d 2 ), or if the write symbol is the same as the read symbol for both rules (i.e. σ 1 = 0, σ 2 = 1) then when the machine enters q a the computation is periodic and from Lemma 1 this means that the set of reachable configurations is regular. For the remaining cases of q 1 = q 2 = q a we need only consider machines with the rules q a , 0, 1, R, q a and q a , 1, 0, L, q a as such machines are regular equivalent to all remaining cases for q 1 = q 2 = q a . When in state q a this machine scans right changing 0's to 1's until it reads a 1, and then it scans An overview of the 378 cases given by Tables 1 to 3, which were obtained from the reduction in the number of cases given in Section 3. Each small square in the above figure represents a Turing machine. There is a 3 × 3 block of small squares for each (Σi, Dj) pair which gives the 9 possible values for Qi. Letter A indicates a reduction to a symmetric case, B is for machines that have periodic computations, C is for machines that give semi-periodic computations, and E is for machines that are binary counters.

left changing 1's to 0's until it reads a 0, and this left scan right scan behaviour is repeated ad infinitum giving a semi-periodic computation. So from Lemma 3 the set of reachable configurations for machines with q 1 = q 2 = q a is regular. The same argument is applicable to the case q 3 = q 4 = q b .

4 Solving Cases in Figure 1 4

.1 Case A: Reduce the Number of Cases Using Symmetries

From Comment 3 we know that if a pair of machines M and M are regular equivalent we need only consider one of the two machines in our list of open cases. Table 4 shows that if the square in Figure 1 for a machine (Σ i , D j , Q k ) contains an A then it is regular equivalent to another machine in the figure whose square does not contain an A. This means that we need not consider Case A machines because by solving the remaining cases each machine in Case A will be regular equivalent to a case that has been solved.

f s-flip (Σ1, D3, Q ) (Σ1, D4, Q ) (Σ6, D3, Q ) (Σ6, D6, Q l ) f b-flip (Σ 5 , D 2 , Q ) (Σ 5 , D 4 , Q ) (Σ 5 , D 5 , Q m ) (Σ 6 , D 2 , Q ) (Σ 6 , D 5 , Q 5 ) f s-flip , f b-flip (Σ4, D3, Q ) (Σ4, D4, Q ) (Σ4, D7, Qp) (Σ6, D4, Q ) f s-flip , f d-flip (Σ6, D5, Q l ) (Σ6, D7, Q l ) f b-flip , f d-flip (Σ5, D6, Qm) (Σ5, D7, Qm) (Σ6, D6, Q5) (Σ6, D7, Q5) f s-flip , f b-flip , f d-flip (Σ 4 , D 5 , Q p ) (Σ 4 , D 6 , Q p )
Table 4. Lemma 4 mappings that map each A case in Figure 1 to a non-A case in Figure 1. The mappings given on the left of each row are applied to the cases in that row to show that each case is regular equivalent to another case in Figure 1. Here Q ∈ {Q1, Q2, . . . Q9}, Qm ∈ {Q2, Q5, Q6, Q9}, Q l ∈ {Q6, Q8, Q9}, and Qp ∈ {Q5, Q8, Q9}. Keep in mind Footnote 1 when applying f b-flip .

Cases B: Machines That Give Periodic Computations

In Figure 1, if the square for a machine (Σ i , D j , Q k ) contains a B then the machine's computation is periodic. From Lemma 2 and Comment 1, periodicity can be proved by showing that a machine eventually scans right never again visiting cell i-m after it visits cell i, or alternatively that the head scans left never again visiting cell i + m after cell i. To achieve this we consider what happens after the tape head attempts to scan in the opposite direction after either 2 consecutive right moves or 2 consecutive left moves. Comment 2 allows us to consider only machines that make consecutive left moves and consecutive right moves. As an example of the above technique we show that after machine (Σ 5 , D 6 , Q 8 ) (given in [START_REF] Rogozhin | Small universal Turing machines[END_REF]) makes 2 or more consecutive left moves it scans left for the rest of the computation never again visiting cell i + 3 after it visits cell i. q a , 0, 0, L, q b q a , 1, 1, R, q b q b , 0, 1, L, q a q b , 1, 0, R, q b (11)

If the tape head is about to make a right move that follows 2 consecutive left moves then either the configuration has the form given on the left of [START_REF] Wagner | Universelle Turingmaschinen mit n-dimensionale band[END_REF] or it has the form given on the left of (13) (where σ i , σ -i ∈ {0, 1}). On the right of [START_REF] Wagner | Universelle Turingmaschinen mit n-dimensionale band[END_REF] we see that after 4 time steps the configuration has the same form as the configuration on the left side of (13) (so we need consider only the case in ( 13)).

On the right of ( 13) we see that after 3 time steps the tape head is now reading σ -1 , one cell to the left of its original position. If σ -1 = 0 the tape head will move left again to make its second consecutive left move and so if we wish to make a right move in the future it will follow 2 consecutive left moves and we will repeat the entire sequence of steps we have just described. Alternatively, if σ -1 = 1 then we have the same case as the left side of (13) and the 3 steps in (13) are repeated. For both cases ( 12) and ( 13) the process repeats with the tape head moving left never visiting cell i + 3 after it has entered cell i, and so from Comment 1 the computation is periodic. The technique given here can be applied to all B cases in Figure 1 to show that they have periodic computations.

. . . σ -2 σ -1 q a 1 10σ 1 σ 2 σ 3 . . .

. . . σ -2 σ -1 q b 1 01σ 1 σ 2 σ 3 . . . (12)
. . . σ -2 σ -1 q b 1 01σ 1 σ 2 σ 3 . . .

. . . σ -4 q b σ -1 011σ 1 σ 2 σ 3 . . . (13)

Cases C: Machines That Give Semi-Periodic Computation

From the proof of Lemma 3 a semi-periodic machine operates by scanning right using a repeating sequence of rules that print a repeating pattern until some sequence of symbols is met on the tape that causes the machine to end the scan right, and following this the machine scans left printing out another repeating pattern until it meets another sequence of symbols on the tape that causes the scan left to end. The entire process is then repeated. The behaviour of the machine when ending a rightward scan depends on the sequence of symbols it reads when it ends the scan right. The scan length increases with each subsequent pass and the sequence of symbols that ends each scan is provided by the blank word that is repeated to the right of the input. Since there is only a finite number of positions at which a scan right can end in relation to the right blank word the behaviour of the machine at the end of scans to the right becomes periodic over time. This can be seen in Definition 4 and Lemma 3 where the first scan right ends with e 1 , the second scan ends with e 2 , the third with e 3 , and so on until scan x which ends with e x . Following scan x the process is repeated with e 1 ending the next scan right. The same is true for scans left with the sequence h 1 , h 2 , . . . h x being repeated once for every x scans to the left. When a 2-state 2symbol machine is executing a semi-periodic computation the patterns it prints during leftward and rightward scans have length 2 and the behaviour at the end of left and right scans are repeated periodically as described above. For this reason it is straightforward to determine when a 2-state 2-symbol machine is executing a semi-periodic computation.

As an example let us consider the machine (Σ 6 , D 6 , Q 3 ) given in (14). It is easy to determine the behaviour of this machine just by looking at its instructions. The machine scans left in state q a reading 0's and printing 1's to the tape until it reads a 1, then it scans right in state q b reading 1's and printing 0's until it reads a 0, and then it begins another scan left in q a . We now show how this behaviour matches the behaviour of the sequence S given in Definition 4. In the scans mentioned above the growth to the left depends on the position of 1s in the left blank word as each 1 terminates a scan left, and similarly the growth to the right depends on the position of 0s in the right blank word. Since the left and right blank words are repeated periodically the growth is periodic for some constant number of scans right, this constant is the x value in sequence S. We set sequences s r and s l so that f (s r ) = m and f (s l ) = -m (see Definition 4) where m is the growth over the x scans left and right during an iteration of S, and this means that during iteration i of S, scans right have the form (s r ) i+1 and scans left have the form (s l ) i+1 . To account for the growth between successive left and right scans during a single iteration of S, we define each e j and h j so that the extra distance traveled between each successive execution of (s r ) i+1 or (s l ) i+1 during S is considered part of e j or h j . This completes our explanation of how to give the 2x+2 sequence that define S in Definition 4. All the machines for Case C can be shown to be semi-periodic using similar analysis to that given above. q a , 0, 1, L, q a q a , 1, 0, R, q b q b , 0, 1, L, q a q b , 1, 0, R, q b (14)

Cases E: Binary counters

The two binary machines in Figure 1 compute in a similar manner and so we will just look at machine (Σ 5 , D 6 , Q 3 ) given in (15). Below we show (Σ 5 , D 6 , Q 3 ) incrementing from 4 to 8. The left most 1 is not part of the number and the most significant bit is on the right. To increment a number the machine scans right in q b changing 1's to 0's until it reads a 0 which it changes to a 1 and it then scans left in q a until it reads a 1, which signals the beginning of the next increment.

It is easy to see that when started on any configuration the set of configurations generated by this machine is regular as it generates all possible strings and the scans left and right that increment the number have a simple form. If the machine has periodic support then the set of reachable configurations remains regular.

The repeated words on the left have no effect on the computation as the tape head can not move left over a 1. On the right when each blank words becomes part of the computation it effects the form of only a constant number of bits at the right end of the number and so the set of reachable configurations is regular.

q a 1 0010 2 q a 1 1010 4 q a 1 0110 2 q a 1 1110 8 q a 1 0001 q a , 0, 0, L, q a q a , 1, 1, R, q b q b , 0, 1, L, q a q b , 1, 0, R, q b (15)

  Fig.1. An overview of the 378 cases given by Tables1 to 3, which were obtained from the reduction in the number of cases given in Section 3. Each small square in the above figure represents a Turing machine. There is a 3 × 3 block of small squares for each (Σi, Dj) pair which gives the 9 possible values for Qi. Letter A indicates a reduction to a symmetric case, B is for machines that have periodic computations, C is for machines that give semi-periodic computations, and E is for machines that are binary counters.

4

 4

3

 3

Note that applying mapping[START_REF] Pavlotskaya | Solvability of the halting problem for certain classes of Turing machines[END_REF] to machines of the form given by Equation (7) also flips the read symbols and so applying it to Σ = (σ1, σ2, σ3, σ4) gives (σ2, σ1, σ4, σ3) instead of (σ1, σ2, σ3, σ4).

This work is supported by Swiss National Science Foundation grant numbers 200021-153295 and 200021-166231. The author thanks the anonymous reviewers for their careful reading of the paper and their helpful comments.

Location of each Qi case within each (Σi, Dj) 3 × 3 block below


Sabine Broda

António Machiavelo

Nelma Moreira

Rogério Reis

On the Average Complexity of Strong Star Normal Form

For regular expressions in (strong) star normal form a large set of efficient algorithms is known, from conversions into finite automata to characterisations of unambiguity. In this paper we study the average complexity of this class of expressions using analytic combinatorics. As it is not always feasible to obtain explicit expressions for the generating functions involved, here we show how to get the required information for the asymptotic estimates with an indirect use of the existence of Puiseux expansions at singularities. We study, asymptotically and on average, the alphabetic size, the size of the ε-follow automaton and the ratio of these expressions to standard regular expressions.

Introduction

A regular expression α is in strong star normal form (ssnf) if for any subexpression of the form β or β + ε the language represented by β does not include the empty word, ε. The star normal form was introduced by Brüggemann-Klein [START_REF] Brüggemann-Klein | Regular expressions into finite automata[END_REF] as a step to improve the construction of the position automaton from a regular expression from cubic to quadratic time. Transforming a regular expression into this normal form can be achieved in linear time, and moreover the position automaton resulting from that normal form coincides with the one of the original expression. In the same paper, the star normal form was also used to characterize certain types of unambiguous expressions. The position automaton construction [START_REF] Glushkov | The abstract theory of automata[END_REF] is a basic conversion between regular expressions and ε-free nondeterministic finite automata (NFA), and several other constructions are known to be its quotients. This is the case for the partial derivative automaton [START_REF] Antimirov | Partial derivatives of regular expressions and finite automaton constructions[END_REF][START_REF] Champarnaud | Canonical derivatives, partial derivatives and finite automaton constructions[END_REF] and the follow automaton [START_REF] Ilie | Follow automata[END_REF]. Champarnaud et al. [START_REF] Champarnaud | Normalized expressions and finite automata[END_REF] showed that if a regular expression is in star normal form and is normalised modulo some regular expression equivalences, the partial derivative automaton is a quotient of the follow automaton. Many conversions from regular expressions to equivalent NFAs consider automata with transitions labelled by the empty word (ε-NFA). Although the most used of these conversions is the Thompson construction (implemented in many UNIX-like string search commands) [START_REF] Thompson | Regular expression search algorithm[END_REF], an older and more thrifty construction in the use of ε-transitions was presented by Ott and Feinstein in 1961 [START_REF] Ott | Design of sequential machines from their regular expressions[END_REF]. An improved version of this construction was redefined by Ilie and Yu, and called the ε-follow automaton. Gulan, Fernau and Gruber [START_REF] Gulan | Local elimination-strategies in automata for shorter regular expressions[END_REF][START_REF] Gruber | Simplifying regular expressions[END_REF][START_REF] Gulan | On the Relative Descriptional Complexity of Regular Expressions and Finite Automata[END_REF] studied the optimal (worst-case) size for all known constructions from regular expressions to ε-NFAs. It turns out that the optimal construction corresponds to the conversion of a regular expression in strong star normal form into an ε-follow automaton.

All this motivated us to study the average-case complexity of regular expressions in strong star normal form, as well as their conversions to NFAs. In previous work, we studied the asymptotic average complexity for some of the above mentioned conversions from regular expressions using the framework of analytic combinatorics [START_REF] Broda | On the average state complexity of partial derivative automata: an analytic combinatorics approach[END_REF][START_REF] Broda | A hitchhiker's guide to descriptional complexity through analytic combinatorics[END_REF][START_REF] Broda | Average size of automata constructions from regular expressions[END_REF], which relates the enumeration of combinatorial objects to the algebraic and complex analytic properties of generating functions. In particular, generating functions can be seen as complex analytic functions, and the study of their behaviour around their dominant singularities gives access to the asymptotic form of their coefficients. Starting with an unambiguous grammar for the set of regular expressions over a given alphabet, and a non-negative measure, the symbolic method allows to obtain a generating function associated with the sequence of the (finite) number of expressions of measure n. Multivariate generating functions can be used to analyse different measures apart from the size of combinatorial objects, e.g. the number of states of the automaton resulting from a given conversion method applied to a regular expression of given size, and thus allow to obtain estimates for the average values of those measures.

While in previous work we were able to get explicit expressions for the generating functions involved, here that would be unmanageable. Using the existence of a Puiseux expansion at a singularity, we show how to get the required information for the asymptotic estimates from an algebraic equation satisfied by the generating function, without actually computing that expansion. We note that the technique here presented allows to find, for the combinatorial classes considered, the form of the function without knowing beforehand the explicit value of the singularity. This provides a very useful method, at least for some combinatorial classes, that circumvents some of the more cumbersome steps of the Algebraic Coefficient Asymptotics algorithm presented by Flajolet and Sedgewick [8, pp. 504-505], as well as the need to know a priori the type of the singularity.

We use this method to derive the asymptotic estimates for the number of regular expressions in ssnf of a given size, as well as a parametric function of several related measures, which can give us, in particular, the alphabetic size or the size of the ε-follow automaton, on average. In the next section, we review some basics on regular expressions and ε-NFAs. In Section 3, we consider the transformation into strong star normal form and give some characterisations of expressions in this form. Section 4 describes a shortcut to obtain asymptotic estimates of the coefficients of generating functions. This is used in Section 5 to obtain the estimates mentioned before. Some experiments corroborating those estimates are presented in Section 6. Conclusions are drawn in Section 7.

Regular Expressions and ε-NFAs

We consider the grammar for regular expressions proposed by Gruber and Gulan in [START_REF] Gruber | Simplifying regular expressions[END_REF][START_REF] Gulan | On the Relative Descriptional Complexity of Regular Expressions and Finite Automata[END_REF], which has the major advantage of avoiding many redundant expressions built with the symbols ε and ∅. Given an alphabet Σ = {σ 1 , . . . , σ k } of size k, the set R k of regular expressions, α, over Σ is defined by the following grammar,

α := ∅ | ε | β, β := σ 1 | • • • | σ k | (β + β) | (β • β) | β ? | β ,
where the operator • (concatenation) is often omitted. The language associated with α is denoted by L(α) and is defined as usual, with L(β ? ) = L(β) ∪ {ε}. It is clear that α ? is equivalent to the standard regular expression α + ε.

For the size of a regular expression α, denoted by |α|, we will consider reverse polish notation length, i.e., the number of symbols in α, not counting parentheses. The number of letters in α is denoted by |α| Σ , and usually called alphabetic size. The number of occurrences of each operator c ∈ {+, •, , ?} is denoted by |α| c .

A nondeterministic finite automaton is a tuple

N = Q, Σ, δ, q 0 , F , where Q is a finite set of states, Σ is the alphabet, δ ⊆ Q × (Σ ∪ {ε}) × Q is the transition relation, q 0 ∈ Q is the initial state,
(N ) = { w ∈ Σ | δ(q 0 , w) ∩ F = ∅ },
where δ is naturally extended to sets of states and words.

Conversion of a regular expression into an equivalent NFA can be defined by induction on the structure of the regular expression. Let N α denote the automaton corresponding to a regular expression α. In Figure 1 we present the construction of the ε-follow automaton, A εf (α) [START_REF] Ilie | Follow automata[END_REF]. The size of the A εf (α) for the atomic expressions ∅, ε, and σ ∈ Σ is 2, 3 and 3, respectively. For the remaining constructions, the size of the resulting automaton equals the sum of the sizes of its constituents plus some constant. For instance, for the operator + one has c ,c ? ) that define functions that can be used to compute several interesting measures. For example, using (2, 2, 2, -2, -1, 1, 0) one gets the number of states; the number of transitions are computed using (0, 1, 1, 0, 0, 2, 1), and the combined size corresponds to (2, 3, 3, -2, -1, 3, 1).

|N β1+β2 | Q = |N β1 | Q + |N β2 | Q -2, |N β1+β2 | δ = |N β1 | δ + |N β2 | δ , and thus |N β1+β2 | = |N β1 | + |N β2 | -2. This can be generalised by considering constants (c ∅ , c ε , c σ , c + , c • ,
We note that the worst-case complexity for this conversion can be reached for expressions with only one letter and n -1 stars. For such an expression of size n, the corresponding A εf automaton has size 3n.

N ∅ : Nε : ε Nσ : σ N β 1 +β 2 : N β 1 N β 2 N β 1 β 2 : N β 1 N β 2 N β : ε ε N β N β ? : N β ε Fig. 1. The ε-follow construction, A εf .

Strong Star Normal Form

A regular expression α is in star normal form if for any subexpression of the form β , ε / ∈ L(β) [START_REF] Brüggemann-Klein | Regular expressions into finite automata[END_REF]. The original notion of star normal form makes use of two operators on regular expressions. Gulan and Gruber simplified that definition and adapted it to forbid that subexpressions of the form β ? could have ε ∈ L(β). The resulting form was called strong star normal form. Definition 1. The operators • and • are inductively defined as follows. Let

ε • = ∅ • = ∅ , σ • = σ for σ ∈ Σ, (β 1 + β 2 ) • = β • 1 + β • 2 , β ? • = β • , β • = β • ; finally (β 1 β 2 ) • = β • 1 + β • 2 if ε ∈ L(β 1 β 2 ) and (β 1 β 2 ) • = β 1 β 2 , otherwise. Let ∅ • = ∅, ε • = ε, σ • = σ for σ ∈ Σ, (β 1 + β 2 ) • = β • 1 + β • 2 , (β 1 β 2 ) • = β • 1 β • 2 , β • = β •• ; finally β ? • = β • if ε ∈ L(β), and β ? • = (β • ) ? , otherwise.
The expression α • is the strong star normal form (ssnf) of α.

For a regular expression α, L(α Using this theorem it is possible to write a context-free grammar for regular expressions in ssnf, i.e., in which every subexpression of the form α or α ? , satisfies ε / ∈ L(α). The set S k of regular expressions in ssnf over Σ is defined by:

α := ε | ∅ | α ε | α ε α ε := α ε α ε | α ε + α ε | α ε + α ε | α ε + α ε | α ε | α ? ε α ε := σ 1 | • • • | σ k | α ε α ε | α ε α ε | α ε α ε | α ε + α ε , (1)
where α ε are regular expressions whose language includes ε, while for α ε , ε / ∈ L(α ε ). The following theorem summarizes the results by Gruber and Gulan [10, Theorems 4 and 6] (see also Gulan [11]).

Theorem 2. Let α be in ssnf of size n and alphabetic size m. Then, A εf (α) has size at most min( 2215 (n + 1) + 1, 22 5 m + 1).

Let A(z) = n a n z n be the generating function associated with some combinatorial class A (cf. [START_REF] Flajolet | Analytic Combinatorics[END_REF]). Given some measure of the objects of the class, the coefficient a n represents the sum of the values of this measure for all objects of size n. We will use the notation [z n ]A(z) for a n . The generating function A(z) can be seen as a complex analytic function, and the study of its behaviour around its dominant singularity ρ (when unique) gives us access to the asymptotic form of its coefficients. In particular, if A(z) is analytic in some indented disc neighbourhood of ρ, then one has the following [START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Broda | A hitchhiker's guide to descriptional complexity through analytic combinatorics[END_REF]:

1. if A(z) = a -b 1 -z/ρ + o 1 -z/ρ , with a, b ∈ R, b = 0, then [z n ]A(z) ∼ b 2 √ π ρ -n n -3/2 ; (2) 2. if A(z) = c √ 1-z/ρ + o 1 √ 1-z/ρ , with c ∈ R * , then [z n ]A(z) ∼ c √ π ρ -n n -1/2 . (3)
Applying this result for the generating function R k (z), corresponding to the number of expressions in R k of size n, the following asymptotic values were obtained in Broda et al. [START_REF] Broda | A hitchhiker's guide to descriptional complexity through analytic combinatorics[END_REF]:

[z n ]R k (z) ∼ 4 √ 2k √ ρ k 4 √ π ρ -(n+1) k (n + 1) -3/2 , with ρ k = 1 2( √ 2k + 1) . (4)
In the same paper, the average size of the ε-follow automata construction was studied, and it was shown that, as the alphabet grows, the size of A εf approaches 0.75n, asymptotically and on average. Let us now give a generic description of the method used for the combinatorial classes that show up within the present paper. From a grammar one obtains, by the symbolic method expounded in [START_REF] Flajolet | Analytic Combinatorics[END_REF], a set of polynomial equations involving the generating function of whose coefficients we want to have an asymptotic estimate. Computing a Gröbner basis for the ideal generated by those polynomials, one gets an algebraic equation for that generating function w = w(z), i.e., an equation of the form G(z, w) = 0, where G(z, w) is a polynomial in Z[z][w], of which w(z) is a root. Since w(z) is the generating function of a combinatorial class, thus a series with non-negative integer coefficients, which is not a polynomial, it must have, by Pringsheim's Theorem [8, Thm IV.6], a real positive singularity, ρ, smaller than 1. At this singularity two cases may occur: either lim z→ρ w(z) = a, a positive real number, or lim z→ρ w(z) = +∞.

In the first case, after making the change of variable s = 1 -z/ρ, one knows that w = w(s) has a Puiseux series expansion at the singularity s = 0, i.e., there exists a slit neighbourhood of that point in which w(s) has a representation as a power series with fractional powers [START_REF] Hille | Analytic Function Theory[END_REF]Chap. 12]. In particular, w must have the form

w(s) = a -g(s)s α , (5)
for some a ∈ R, α ∈ Q + , the first positive exponent of that expansion, and g(s) such that g(s) = b + h(s)s β , h(0) = 0, β ∈ Q + , and b ∈ R * . We will show that, under some generic conditions that happen to be satisfied in all the cases treated below, one has α = 1 2 or α = -1 2 . One then needs to find the values of ρ and of b or c, depending on the case, to use either ( 2) or (3) to obtain the sought-after asymptotic estimates of the coefficients of w(z).

Using Taylor expansion of G(z, w) at (ρ, a),

G(z, w) =G(ρ, a) + ∂G ∂z (ρ, a)(z -ρ) + ∂G ∂w (ρ, a)(w -a)+ + 1 2 ∂ 2 G ∂z 2 (ρ, a)(z -ρ) 2 + 1 2 ∂ 2 G ∂w 2 (ρ, a)(w -a) 2 + + ∂ 2 G ∂z ∂w (ρ, a)(z -ρ)(w -a) + • • • ,
and noticing that G(z, w(z)) = 0, that G(ρ, a) = 0, and using Equation ( 5), one has,

0 = - ∂G ∂z (ρ, a)ρs - ∂G ∂w (ρ, a)g(s)s α + 1 2 ∂ 2 G ∂z 2 (ρ, a)ρ 2 s 2 + + 1 2 ∂ 2 G ∂w 2 (ρ, a)g(s) 2 s 2α - ∂ 2 G ∂z ∂w (ρ, a)ρg(s)s 1+α + Q(s)s 3α , (6)
for some function Q(s), a Puiseux series with non-negative exponents.

In the case under study, the curve defined by G has a shape similar to the one depicted in Fig. 2, and therefore

∂G ∂w (ρ, a) = 0. (7)
This, together with the fact that G(ρ, a) = 0, shows that ρ is a root of the discriminant polynomial of G with respect to variable w, which is a polynomial in z (cf. [15, p. 204]). In all the cases studied here, this polynomial has only one root in ]0, 1[, a fact that allows to numerically get an approximation for the value of ρ. The minimum polynomial in Q[z] of ρ can be obtained by analysing the greatest common divisor of the polynomials G(z, w) and ∂ ∂w G(z, w) with respect to w: gcd w (G(z, w), ∂ ∂w G(z, w)). We will denote this polynomial by m ρ (z). Using now the gcd z (G(z, w), ∂ ∂w G(z, w)) one can get a polynomial that has a as a root. One can then numerically compute all the real roots of that polynomial, and then check which one is an approximation for the value of a by means of a numerical study of the curve G(z, w). Using ( 7) in ( 6), and dividing it through by s α , one gets 0 = -∂G ∂z (ρ, a)ρs 1-α + 1 2

∂ 2 G ∂z 2 (ρ, a)ρ 2 s 2-α + 1 2
∂ 2 G ∂w 2 (ρ, a)g(s) 2 s α + + ∂ 2 G ∂z ∂w (ρ, a)ρg(s)s + Q(s)s 2α . ( 8
)
Now, in all cases studied in this paper, one has ∂G ∂z (ρ, a) = 0, and

∂ 2 G ∂w 2 (ρ, a) = 0. ( 9
)
This was checked by computing

p 1 (z) = gcd w (G(z, w), ∂ ∂z G(z, w)), p 2 (z) = gcd w (G(z, w), ∂ 2 ∂w 2 G(z, w)),
gcd(p 1 (z), m ρ (z)) and gcd(p 2 (z), m ρ (z)), obtaining a constant depending only on k, that is non-zero for all k = 54 in all cases dealt with in this paper. The case k = 54 was dealt separately. Using the explicit value for ρ, the validity of ( 9) for this value of k was verified. It now follows from [START_REF] Flajolet | Analytic Combinatorics[END_REF], by noticing that the first and third summands have the smallest degrees in s, that they must have the same degree and cancel each other. Dividing, then, by s α and letting s → 0, one obtains

α = 1 2
, and b = g(0) = 2ρ ∂G ∂z (ρ, a)

∂ 2 G ∂w 2 (ρ, a)
.

In conclusion, for the case where lim z→ρ w(z) = a, using (2), one has

[z n ]w(z) ∼ b 2 √ π ρ -n n -3/2 .
For the case where lim z→ρ w(z) = +∞, making v = 1/w one concludes as above that v = cs α -g(s)s α+β , for some 0 < α < 1, β > 0, and for some Puiseux series g(s), with non-negative exponents. The polynomial satisfied by v is then

H(z, v) = v n G z, 1 v , (10)
which is the reciprocal polynomial of G(z, w) with respect to the variable w.

Using the same procedure as above, one computes ρ, and checking that the corresponding derivatives are non-zero, i.e.

∂H ∂z (ρ, 0) = 0, and

∂ 2 H ∂w 2 (ρ, 0) = 0,
one gets in the same way that

α = 1 2
, and c = 2ρ ∂H ∂z (ρ, 0)

∂ 2 H ∂w 2 (ρ, 0) . (11)
Since

w = 1 cs α -g(s)s α+β = 1 c s -α 1 1 -g(s) c s β = 1 c s -α 1 + g(s) c s β + g(s) 2 c 2 s 2β + • • • , one sees, using (3), that [z n ]w(z) ∼ 1 c √ π ρ -n n -1/2 . ( 12
)

Average Sizes: Concrete Results

Let A k (z) and B k (z) be the generating functions for α ε and α ε , respectively. They satisfy the following equations

A k (z) = 2zA k (z) 2 + 2zA k (z)B k (z) + 2zB k (z) (13)
B k (z) = kz + 2zA k (z)B k (z) + 2zB k (z) 2 . (14)
From ( 13) one gets

B k (z) = A k (z)(1 2zA k (z)) 2z(A k (z) + 1) ,
and then substituting B k (z) in ( 14) one obtains, after clearing up denominators,

4z 2 A k (z) 3 -(2kz 2 + 4z)A k (z) 2 -(4kz 2 -1)A k (z) -2kz 2 = 0, i.e., A k (z) is an algebraic function that is a root of G(z, w) = 4z 2 w 3 -(2kz 2 + 4z)w 2 -(4kz 2 -1)w -2kz 2 .
Using now [START_REF] Ilie | Follow automata[END_REF] to get A k (z) as a function of B k (z), and then substituting that into [START_REF] Hille | Analytic Function Theory[END_REF], one easily sees that B k (z) is a root of

H(z, w) = 4zw 3 + 2kzw 2 -kw + k 2 z.
Using the technique described in the previous section, one sees that A k (z) and B k (z) have the same singularity, namely the only root in the interval ]0, 1[ of the polynomial

m ρ (z) = z 3 + 9z 2 2k + 27 - z 8k + 108 - 1 k(2k + 27) . (15)
Also one gets that α = 1 2 , and that the values of a A = A k (ρ) and of a B = B k (ρ) are roots of the polynomials 8z 3 -kz 2 +2kz -k, and 8z 3 +2kz 2 -k 2 , respectively. With all this, and writing S k (z) = A k (z) + B k (z) one then gets that Using these results and the one mentioned in (4), the ratio of regular expressions in ssnf,

[z n ]S k (z) ∼ b k 2 √ π ρ -n k n -3/2 , (16) where
r (k,n) = [z n ]S k (n) [z n ]R k (n)
, can now be computed for any k and n. In particular, one finds that, for example, r (2,1000) = 4.427117336 × 10 -59 , r (10,1000) = 2.562752010 × 10 -19 , r (50,1000) = 1.517513555 × 10 -4 .

Counting Letters

To obtain the asymptotic average value of several measures for regular expressions of a given size, we consider bivariate generating functions parametrized by weights of the form c o , with o ∈ {∅, ε, σ, +, •, , ?}, associated to each regular expression element. Considering the grammar (1), let A k (u, z) and B k (u, z) be the bivariate generating functions associated to α ε and α ε , respectively. Then

A k (u, z) = (u c• + u c+ )zA k (u, z) 2 + 2u c+ zA k (u, z)B k (u, z) + (u c ? + u c )zB k (u, z), B k (u, z) = ku cσ z + (u c• + u c+ )zB k (u, z) 2 + 2u c• zA k (u, z)B k (u, z).
Note that A and B depend on the parameters (c ∅ , c ε , c σ , c + , c • , c , c ? ), but for sake of simplicity we choose to omit them. For computing the average number of letters those parameters are (0, 0, 1, 0, 0, 0, 0), and analogously for each operator.

The generating function L k (z) for the number of letters is given by

L k (z) = ∂ ∂u u=1 (A k (u, z) + B k (u, z)) . Setting A = A k (1, z), B = B k (1, z), A 1 = ∂ ∂u u=1 A k (u, z), B 1 = ∂ ∂u u=1 B k (u, z), so that L k = A 1 + B 1 , one has: A = 2A 2 z + 2ABz + 2Bz, B = 2ABz + 2B 2 z + kz, A 1 = 4AA 1 z + 2AB 1 z + 2BA 1 z + 2B 1 z, B 1 = 2AB 1 z + 2BA 1 z + 4BB 1 z + kz, L k = A 1 + B 1 .
Using Gröbner basis, as mentioned above, one gets the following polynomial for w = L k :

G(z, w) = 8 k 2 + 108 k z 3 + 36 kz 2 -kz -4 w 3 + + k 3 + 12 k 2 z 3 + 4 k 2 z 2 + kz w -2 k 2 z 3 -k 2 z 2 .
It turns out that, from this, one can deduce that the singularity for this algebraic function w has the same minimal polynomial as in [START_REF] Lang | Algebra. No. 211[END_REF], and so it is the same as for the number of regular expressions there considered. One then finds that, in this case, α = -1 2 , and that

[z n ]L k (z) ∼ 1 c k √ π ρ -n k n -1/2 , (17)
where, for example, From this one gets, for any given k, the density of letters in expressions of size

n, k = [z n ]L k (n) n[z n ]S k (n)
, which is independent of n since the singularities of L k and S k are the same. In particular, one finds that, for example, 2 = 0.4172563448, 10 = 0.4432524170, 50 = 0.4657465002.

Size of ε-Follow Automata

Considering the parameters (2, 3, 3, -2, -1, 3, 1), as defined in Section 2, the generating function F k (z) for the size of the A εf automaton is given by

F k (z) = ∂ ∂u u=1 (A k (u, z) + B k (u, z)) .
Using the same abbreviations as above, one has:

A = 2A 2 z + 2ABz + 2Bz B = 2ABz + 2B 2 z + kz A 1 = -3A 2 z -4ABz + 4AA 1 z + 2AA 2 z + 2BA 1 z + 4Bz + 2A 2 z A 2 = -2ABz + 2AA 2 z -3B 2 z + 2BA 1 z + 4BA 2 z + 3kz F k = A 1 + A 2 .
Proceeding as above, one can verify that the singularity for F k (z) still has the same minimal polynomial as in [START_REF] Lang | Algebra. No. 211[END_REF], that α = -1 2 , and that

[z n ]F k (z) ∼ 1 c k √ π ρ -n k n -1/2 , (18)
where, for example, For the average ratio,

f k = [z n ]F k (n) n[z n ]S k (n)
, between the size of the A εf and the size of the respective regular expression (also independent of n) one has, for example, f 2 = 0.9803566472, f 10 = 0.9034371711, f 50 = 0.8400260553.

Experimental Results

We ran some experiments, using the FAdo package [START_REF]Project FAdo: tools for formal languages manipulation[END_REF], to obtain average sizes of the measures studied above for small values of k and n. For the results to be statistically significant, regular expressions were uniformly random generated using a version of the grammar for S k in reverse polish notation. For each size n ∈ {200, 500, 1000}, and alphabet size k ∈ {2, 10, 50}, samples of 10000 expressions were generated. This is sufficient to ensure a 95% confidence level within a 1% error margin. The results are presented in Table 1, together with the values of k and f k calculated in the previous section. The last column, labeled wc, presents the worst case size of A εf as given in Theorem 2, for expressions of size n.

Conclusions

The average complexity results obtained for expressions in ssnf are only slightly smaller than the ones obtained for general regular expressions. Indeed, for the size of A εf , and the same values of k, the asymptotic values obtained in [START_REF] Broda | A hitchhiker's guide to descriptional complexity through analytic combinatorics[END_REF], were f 2 = 1.2, f 10 = 1, and f 50 = 0.9. In that study, we got an explicit expression, depending on k, for the asymptotic size of A εf , allowing us to compute its limit of 0.75 as k goes to ∞. Here we were not able to obtain such an expression, but we conjecture that the limit is the same. This would mean that the average size is half the worst-case one. This is corroborated by the experimental results. Furthermore, the ratio between the number of ssnf expressions and the number of general expressions, of a certain size, tends to zero.

  and F ⊆ Q is the set of final states. The size of an NFA N is |N | = |Q| + |δ|, the number of states |N | Q = |Q|, and the number of transitions |N | δ = |δ|. An NFA that has transitions labelled with ε is an ε-NFA. The language accepted by an automaton N is L

Fig. 2 .

 2 Fig. 2. Generic shape of G(z, w) near its dominant singularity.

, for example, b 2

 2 = 1.089338906 , ρ 2 = 0.1915181504 b 10 = 2.313181803 , ρ 10 = 0.09581011247 b 50 = 5.054983041 , ρ 50 = 0.4606805763.

c 2

 2 = 2.725255757, ρ 2 = 0.1915181504, c 10 = 1.271387537, ρ 10 = 0.09581011247, c 50 = 0.5749569245, ρ 50 = 0.04606805763.

c 2 = 1 .

 21 159914873, ρ 2 = 0.1915181504, c 10 = 0.6237795132, ρ 10 = 0.09581011247, c 50 = 0.3187807970, ρ 50 = 0.4606805763.

  The following theorem characterizes the regular expressions in strong star normal form.Theorem 1. [11, Theorem 3.2.8] A regular expression α is in strong star normal form, i.e. α = α • , if and only if for every subexpression β or β

• ) = L(α) and |α • | ≤ |α|. ? of α, one has ε / ∈ L(β).

Table 1 .

 1 Results for regular expressions in ssnf

	k	|α| |α|Σ	|δ εf | |Q εf |	|εf| |α| Σ |α|	k	|εf| |α|	f k	wc
		200 83.86 112.20 52.86 165.06 0.42 0.417 0.83 0.98 1.479
	2	500 208.99 279.97 129.74 409.71 0.42		0.82		1.472
		1000 417.70 559.04 257.85 816.89 0.42		0.82		1.469
		200 89.13 111.98 51.80 163.78 0.45 0.443 0.82 0.90 1.479
	10	500 222.09 279.11 126.91 406.02 0.44		0.81		1.472
		1000 443.77 557.72 252.30 810.02 0.44		0.81		1.469
		200 93.63 108.53 51.29 159.82 0.47 0.466 0.80 0.84 1.479
	50	500 233.34 270.66 125.80 396.46 0.47		0.79		1.472
		1000 466.20 540.84 249.94 790.78 0.47		0.79		1.469

This work was partially supported by CMUP (UID/MAT/00144/2013), which is funded by FCT (Portugal) with national (MEC) and European structural funds through the programs FEDER, under the partnership agreement PT2020.


Rudolf Freund

Vladimir Rogojin
email: vladimir.rogojin@abo.fi

Sergey Verlan
email: verlan@u-pec.fr

Computational Completeness of Networks of Evolutionary Processors with Elementary Polarizations and a Small Number of Processors

We improve previous results obtained for networks of evolutionary processors with elementary polarizations -1, 0, 1 by showing that only the very small number of seven processors is needed to obtain computational completeness. In the case of not requiring a special output node even only five processors are shown to be sufficient.

Introduction

Networks of evolutionary processors (NEPs) consist of cells (processors) each of them allowing for specific operations on strings. Computations in such a network consist of alternatingly performing two steps -an evolution step where in each cell all possible operations on all strings currently present in the cell are performed, and a communication step in which strings are sent from one cell to another cell provided specific conditions are fulfilled. Examples of such conditions are (output and input) filters which have to be passed, and these (output and input) filters can be specific types of regular languages or permitting and forbidden context conditions. The set of strings obtained as results of computations by the NEP is defined as the set of objects which appear in some distinguished node in the course of a computation. In networks of evolutionary processors with polarizations each symbol has assigned a fixed integer value; the polarization of a string is computed according to a given evaluation function, and in the communication step copies of strings are moved to all cells having the same polarization. As in [START_REF] Popescu | Networks of polarized evolutionary processors with elementary polarization of symbols[END_REF], in this paper we only consider the elementary polarizations -1, 0, 1 for the symbols as well as for the cells.

Seen from a biological point of view, networks of evolutionary processors are a collection of cells communicating via membrane channels which makes them to be seen as tissue-like P systems (see [START_REF] Martín-Vide | A new class of symbolic abstract neural nets: Tissue P systems[END_REF]) considered in the area of membrane computing (see [START_REF]The Oxford Handbook of Membrane Computing[END_REF]); as in membrane computing, the computations are carried out in a parallel and synchronized way in all cells The operations considered for the processors (cells) in networks of evolutionary processors usually are the point mutations insertion, deletion, and substitution, well-known from biology as operations on DNA.

Networks of Evolutionary Processors (NEPs) were introduced in [START_REF] Castellanos | Solving NP-complete problems with networks of evolutionary processors[END_REF] and [START_REF] Castellanos | Networks of evolutionary processors[END_REF] as a model of string processing devices distributed over a graph, with the processors carrying out the operations insertion, deletion, and substitution. NEPs with a very small number of nodes are very powerful computational devices: already with two nodes, they are as powerful as Turing machines, e.g., see [START_REF] Alhazov | On the number of nodes in universal networks of evolutionary processors[END_REF][START_REF] Alhazov | Networks of evolutionary processors with two nodes are unpredictable[END_REF]. For a survey of the main results regarding NEPs the interested reader is referred to [START_REF] Manea | Accepting networks of evolutionary word and picture processors: A survey[END_REF].

In hybrid networks of evolutionary processors (HNEPs), each language processor performs only one of these operations on a certain position of the strings. Furthermore, the filters are defined by some variants of random-context conditions, i.e., they check the presence and the absence of certain symbols in the strings. For an overview on HNEPs and the so far known best results, we refer the reader to [START_REF] Alhazov | Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors[END_REF].

Networks of polarized evolutionary processors were considered in [START_REF] Arroyo | Networks of polarized evolutionary processors are computationally complete[END_REF] (a new version of that paper is going to appear, [START_REF] Arroyo | On the computational power of networks of polarized evolutionary processors[END_REF]), and networks of evolutionary processors with elementary polarizations -1, 0, 1 were investigated in [START_REF] Popescu | Networks of polarized evolutionary processors with elementary polarization of symbols[END_REF]. In this paper we consider the same model of networks of evolutionary processors with elementary polarizations -1, 0, 1 as in [START_REF] Popescu | Networks of polarized evolutionary processors with elementary polarization of symbols[END_REF], yet we considerably improve the number of processors (cells) needed to obtain computational completeness from 35 to 7, which makes these results already comparable with those obtained in [START_REF] Alhazov | Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors[END_REF] for hybrid networks of evolutionary processors using permitting and forbidden contexts as filters for the communication of strings between cells.

The rest of the paper is structured as follows: In Section 2 we give the definitions of the model of a network of evolutionary processors with elementary polarizations -1, 0, 1 (NePEP for short) and of the variant of a circular Post machine we are going to simulate by the NePEP. In Section 3 we show our main result proving that any circular Post machine can be simulated by an NePEP with only seven processors (cells), and in the case of not requiring a special output processor even only five processors are needed. A summary of the results and an outlook to future research conclude the paper.

Prerequisites

We start by recalling some basic notions of formal language theory. An alphabet is a non-empty finite set. A finite sequence of symbols from an alphabet V is called a string over V . The set of all strings over V is denoted by V * ; the empty string is denoted by λ; moreover, we define V + = V * \ {λ}. The length of a string x is denoted by |x|, and by |x| a we denote the number of occurrences of a letter a in a string x. For a string x, alph(x) denotes the smallest alphabet Σ such that x ∈ Σ * . For more details of formal language theory the reader is referred to the monographs and handbooks in this area, such as [START_REF]Handbook of Formal Languages[END_REF].

We only remark that in this paper, string rewriting systems as Turing machines, Post systems, etc. are called computationally complete if these systems are able to compute any partial recursive relation R on strings over any alphabet U . Computational completeness in the usual sense with respect to acceptance and generation directly follows from this general kind of computational completeness; for more details we refer to [START_REF] Alhazov | Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors[END_REF]. The definitions of the succeeding subsections are mainly taken from [START_REF] Alhazov | Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors[END_REF] and [START_REF] Popescu | Networks of polarized evolutionary processors with elementary polarization of symbols[END_REF].

Insertion, Deletion, and Substitution

For an alphabet V , let a → b be a rewriting rule with a, b ∈ V ∪ {λ}, and ab = λ; we call such a rule a substitution rule if both a and b are different from λ; such a rule is called a deletion rule if a = λ and b = λ, and it is called an insertion rule if a = λ and b = λ. The set of all substitution rules, deletion rules, and insertion rules over an alphabet V is denoted by Sub V , Del V , and Ins V , respectively.

Given such rules π ≡ a → b ∈ Sub V , ρ ≡ a → λ ∈ Del V , and σ ≡ λ → a ∈ Ins V as well as a string w ∈ V * , we define the following actions of π, ρ, and σ on w:

-If π ≡ a → b ∈ Sub V , then π(w) = {ubv : ∃u, v ∈ V * (w = uav)}, if | w | a > 0, {w}, otherwise. -If ρ ≡ a → λ ∈ Del V , then ρ r (w) = {u : ∃u ∈ V * (w = ua)}, if | w | a > 0, {w}, otherwise. ρ l (w) = {v : ∃v ∈ V * (w = av)}, if | w | a > 0, {w}, otherwise. -If σ ≡ λ → a ∈ Ins V , then σ r (w) = {wa} and σ l (w) = {aw}.
The symbol α ∈ { * , l, r} denotes the mode of applying a substitution, insertion or deletion rule to a string, namely, at any position (α = * ), on the left-hand end (α = l), or on the right-hand end (α = r) of the string, respectively.

For any rule β, β ∈ {π, ρ, σ}, any mode α ∈ { * , l, r}, and any L ⊆ V * , we define the α-action of β on L by β α (L) = w∈L β α (w). For a given finite set of rules M , we define the α-action of M on a string w and on a language L by M α (w) = β∈M β α (w) and M α (L) = w∈L M α (w), respectively. In the following, substitutions will only be used at arbitrary positions, i.e., with α = * , which will be omitted in the description of the rule.

Post Systems and Circular Post Machines

The left and right insertion, deletion, and substitution rules defined in the preceding subsection are special cases of string rewriting rules only working at the ends of a string; they can be seen as restricted variants of Post rewriting rules as already introduced by Emil Post in [START_REF] Post | Formal reductions of the general combinatorial decision problem[END_REF]: for a simple Post rewriting rule Π s ≡ u$x → y$v, where u, v, x, y ∈ V * , for an alphabet V , we define

π s (w) = {yzv | w = uzx, z ∈ V * }.
A normal Post rewriting rule π n ≡ $x → y$ is a special case of a simple Post rewriting rule u$x → y$v with u = v = λ (we also assume xy = λ); this normal Post rewriting rule $x → y$ is the mirror version of the normal form rules u$ → $v as originally considered in [START_REF] Post | Formal reductions of the general combinatorial decision problem[END_REF] for Post canonical systems; yet this variant has already been used several times for proving specific results in the area of membrane computing, e.g., see [START_REF] Freund | Generating and accepting P systems with minimal left and right insertion and deletion[END_REF]. A Post system of type X is a construct (V, T, A, P ) where V is a (finite) set of symbols, T ⊆ V is a set of terminal symbols, A ∈ V * is the axiom, and P is a finite set of Post rewriting rules of type X; for example, X can mean simple or normal Post rewriting rules. In both cases it is folklore that these Post systems of type X are computationally complete.

The basic idea of the computational completeness proofs for Post systems is the "rotate-and-simulate"-technique, i.e., the string is rotated until the string x to be rewritten appears on the right-hand side, where it can be erased and replaced by the string y on the left-hand side, which in total can be accomplished by the rule $x → y$. By rules of the form $a → a$ for each symbol a the string can be rotated. In order to indicate the beginning of the string in all its rotated versions, a special symbol B (different from all others) is used; B is to be erased at the end of a successful computation.

Circular Post machines are machine-like variants of Post systems using specific variants of simple Post rewriting rules; the variant of CPM 5 we use in this paper was investigated in [START_REF] Alhazov | Circular Post machines and P systems with exo-insertion and deletion[END_REF].

Definition 1. A (non-deterministic) CPM5 is a construct M = (Σ, T, Q, q 1 , q 0 , R),
where Σ is a finite alphabet, T ⊆ Σ is the set of terminal symbols, Q is the set of states, q 1 ∈ Q is the initial state, q 0 ∈ Q is the only terminal state, and R is a set of simple Post rewriting rules of the following types (we use the notation

Q = Q \ {q 0 }): -px$ → q$ ( deletion rule) with p ∈ Q , q ∈ Q, x ∈ Σ; we also write px → q
and, for any w ∈ Σ * , the corresponding computation step is pxw px→q -→ qw; p$ → q$y ( insertion rule) with p ∈ Q , q ∈ Q, y ∈ Σ; we also write p → yq and, for any w ∈ Σ * , the corresponding computation step is pw p→yq -→ qwy.

The CPM5 is called deterministic if for any two deletion rules px → q 1 and px → q 2 we have q 1 = q 2 and for any two insertion rules p → q 1 y 1 and p → q 2 y 2 we have q 1 y 1 = q 2 y 2 .

The name circular Post machine comes up from the idea of interpreting the machines to work on circular strings where both deletion and insertion rules have local effects, as for circular strings the effect of the insertion rule p$ → q$y is the same as the effect of p → yq directly applied to a circular string, which also justifies writing p$ → q$y as p → yq.

For a given input string w, w ∈ T * , the CPM5 M starts with q 1 w and applies rules from R until it eventually reaches a configuration q 0 v for some v ∈ T * ; in this case we say that (w, v) is in the relation computed by M .

Definition 2. A CPM5 M = (Σ, T, Q, q 1 , q 0 , R) is said to be in normal form if -Q \ {q 0 } = Q 1 ∪ Q 2 where Q 1 ∩ Q 2 = ∅;
for every p ∈ Q 1 and every x ∈ Σ, there exactly one instruction of the form px → q, i.e., Q 1 is the set of states for deletion rules; for every insertion rule p → yq we have p ∈ Q 2 , i.e., Q 2 is the set of states for insertion rules, and moreover, if p → y 1 q 1 and p → y 2 q 2 are two different rules in R, then y 1 = y 2 .

Theorem 1. (see [START_REF] Alhazov | Circular Post machines and P systems with exo-insertion and deletion[END_REF]) CPM5s in normal form are computationally complete.

Networks of Evolutionary Processors with Elementary Polarizations

Definition 3. A polarized evolutionary processor over V is a triple (M, α, π) where -M is a set of substitution, deletion or insertion rules over the alphabet V , i.e., (M ⊆ Sub V ) or (M ⊆ Del V ) or (M ⊆ Ins V ); α gives the action mode of the rules of the node; π ∈ {-1, 0, +1} is the polarization of the node (negative, neutral, positive).

The set M represents the set of evolutionary rules of the processor. It is important to note that a processor is "specialized" in one type of evolutionary operation only as in HNEPs. The set of evolutionary processors over V is denoted by EP

V . Definition 4. A network of polarized evolutionary processors (NPEP for short) is a 7-tuple Γ = (V, T, H, R, ϕ, n in , n out ) where -V is the alphabet of the network; -T is the input/output alphabet, T ⊆ V ; T ⊆ V ; -H = (X H , E H
) is an undirected graph (without loops) with the set of vertices (nodes) X H and the set of (undirected) edges E H ; H is called the underlying communication graph of the network; -R : X H -→ EP V is a mapping which with each node x ∈ X H associates the polarized evolutionary processor R(x) = (M x , α x , π x ); ϕ is an evaluation function from V * into the set of integers; n in , n out ∈ X H are the input and the output node, respectively.

The number of nodes in X H , card(X H ), is called the size of Γ . If the evaluation mapping ϕ takes values in the set {-1, 0, 1} only, the network is said to be with elementary polarization of symbols (an NePEP for short).

A configuration of an NPEP Γ , as defined above, is a mapping C : X H -→ 2 V * which associates a set of strings over V with each node x of the graph. A component C(x) of a configuration C is the set of that can be found in the node x of this configuration, hence, a configuration can be considered as a list of the sets of strings which are present in the nodes of the network at a given moment.

A computation of Γ consists of alternatingly applying an evolutionary step and a communication step. When changing by an evolutionary step, each component C(x) of the configuration C is changed in accordance with the set of evolutionary rules M x associated with the node x thus yielding the new configuration C , and we write C =⇒ C if and only if

C (x) = M αx x (C(x)) for all x ∈ X H .
In a communication step, each node processor x ∈ X H sends out copies of all its strings, but keeping a local copy of the strings having the same polarization to that of x only, to all the node processors connected to x, and receives a copy of each word sent by any node processor connected with x providing that it has the same polarization as that of x, thus yielding the new configuration C from configuration C, and we write C C ,

C (x) = (C(x) \ {w ∈ C(x) | sign(ϕ(w)) = π x }) ∪ {x,y}∈E G ({w ∈ C(y) | sign(ϕ(w)) = π x }),
for all x ∈ X H . Here sign(m) is the sign function which returns +1, 0, -1, provided that m is a positive integer, is 0, or is a negative integer, respectively. Note that all strings with a different polarization than that of x are expelled. Further, each expelled word from a node x that cannot enter any node connected to x is lost.

In the following, we will only use the evaluation function ϕ with ϕ(λ) = 0 and ϕ(aw) = ϕ(a) + ϕ(w) for all a ∈ V and w ∈ V * , i.e., the value a string is the sum of the values of the symbols contained in it; we write ϕ s for this function.

Given an input word w ∈ T * , the initial configuration C 0 of Γ for w is defined by C 2i+2 , for all i ≥ 0. As results we take all terminal strings appearing in the output cell n out during a computation of Γ . In fact, in [START_REF] Alhazov | Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors[END_REF] this variant was called with terminal extraction. On the other hand, we may require a special output where only the terminal strings appear, which we will consider as the standard variant.

Main result

In this section we now show our main result how a given CPM5 can be simulated by an NePEP (with terminal extraction) with only 7 (5) cells provided that for a given input string w ∈ T * we start with the initial string q 1 w in the input cell, where q 1 is the initial state of the CPM5. In order to start with the input string w directly we would have to add two more nodes to carry out this initial procedure of adding the initial state q 1 . Theorem 2. For any CPM5 M = (Σ, T, Q, q 1 , q 0 , R) in normal form there exists a standard NePEP with only seven cells Γ = (V, T, H, R, φ s , i 1 , i 0 ) being able to simulate the computations of M .

Proof. Let n = |T |, m = |Q|, 0 ≤ i ≤ m and 0 ≤ k ≤ n. We define V = T ∪ {q 0 i , q+ i , q- i , X - i , D 0 i , D + i , D+ i | 0 ≤ i ≤ m} ∪ {q - k,i , q0 k,i | 0 ≤ k ≤ n, 0 ≤ i ≤ m} ∪ {A - i,k , A 0 i,k | 0 ≤ k ≤ n, 0 ≤ i ≤ m} ∪ {A 0 k , A + k , Â+ k , Ǎ+ k | 0 ≤ k ≤ n} ∪ {ε -}
The evaluation φ s for the symbols in V corresponds to the superscript of the symbol, i.e., for α z ∈ V with z ∈ {+, 0, -} we define φ s (α 0 ) = 0, φ s (α + ) = +1, φ s (α -) = -1, and, moreover, for a ∈ T , we take φ s (a) = 0.

The communication graph H consists of the set of nodes {1, 2, 3, 4, 5, 6, 7} and of the following set of undirected edges: {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {4, 5}, {4, 6}, {6, 7}}.

Node 1 is the input and node 7 is the output node.

For the seven nodes i, 1 ≤ i ≤ 7, the corresponding evolutionary processors N (i) are defined as follows:

α(1) = α(3) = α(4) = α(7) = * , α(2) = r and α(5) = α(6) = l. π(1) = π(7) = 0, π(2) = π(4) = π(5) = -and π(3) = π(6) = +.
For the types of rules in the rule sets

M i we have M 1 , M 3 , M 4 ⊂ SU B V , M 2 ⊂ IN S V , M 5 , M 6 ⊂ DEL V ,
and M 7 = ∅, i.e., M 7 could be assumed to be any type of rules.

Processor 1 has polarization (charge) 0 and uses substitution rules to contribute to the simulation of insertion and deletion rules of M :

Insertion: q s → q j a k (1 ≤ l ≤ k) Deletion: q s a k → q j (1 ≤ i ≤ s) 1.1: q 0 s → q - k,j 1.7: q 0 s → X - s 1.2: q - l,j → q 0 l-1,j 1.8: A - i,l → A 0 i+1,l 1.3: A 0 l → Â+ l 1.9: A 0 i,l → Â0 i,l 1.4: A 0 l → Ǎ+ l 1.10: D 0 i → D+ i 1.5: q 0 l,j → q0 l,j 1.11: D+ i → D + i 1.6: Â+ l → A + l 1.12: A - i,l → q+ j 1.13: q+ j → q- j
Processor 3 has polarization (charge) +1 and uses substitution rules to contribute to the simulation of insertion and deletion rules of M :

Insertion: q s → q j a k (1 ≤ l ≤ k) Deletion: q s a k → q j (1 ≤ i ≤ s) 3.1: A + l → A 0 l+1 3.5 : D + i → D 0 i-1 , i > 0 3.2: q0 l,j → q - l,j , l > 0 3.6: Â0 i,l → A - i,l
3.3: q0 0,j → q 0 j 3.7 :

D + 0 → ε - 3.4: Ǎ+ l → a 0 l
Processor 4 has polarization (charge) -1 and uses substitution rules to contribute to the simulation of deletion rules of M only:

Deletion: q s a k → q j 4.1: a 0 l → A - 0,l 4.2: X - s → D + s 4.3: q- j → q 0 j , j > 0 4.4: q- 0 → q + 0
Processor 2 has polarization (charge) -1 and only contains the single insertion rule 2.1: λ → A + 0 . Processor 5 has polarization (charge) -1 and only contains the single deletion rule 5.1: ε -→ λ. Processor 6 has polarization (charge) +1 and only contains the single deletion rule 6.1: q + 0 → λ. The proof closely follows the idea from [1] (Theorem 2), which is itself based on the rotate-and-simulate method. We recall the main steps of that proof below.

The configuration of M is represented as q s w, s ≥ 0, where q s is the current state. Suppose that q s → q j a k is the associated instruction. Then the following evolution is performed in Γ (for readability, we omit the superscripts (charges) of the symbols): q s w ⇒ * q k,j wA 0 ⇒ * q k-1,j wA 1 ⇒ * q k-t,j wA t ⇒ * q 0,j wA k ⇒ * q j wa k As in the classical rotate-and-simulate method, A 0 is appended to the string and then the indices of q k,j (respectively A 0 ) are decreased (respectively increased) simultaneously. When the first index of q k,j reaches zero, its initial value is stored as an index of A k , allowing to produce the right symbol a k afterwards. The instruction q s a k → q j is simulated in the following way:

q s a k w ⇒ * D s A 0,k w ⇒ * D i-1 A 1,k w ⇒ * D i-t A i,k wA ⇒ * ⇒ * D 0 A s,k w ⇒ * εA s,k w ⇒ * εq j w ⇒ q j w
Here the state symbol q s is replaced by D s and the first symbol a k by A 0,k . Then in a loop the index of D decreases, while the first index of A increases. At the end of this loop the string D 0 A s,k w is obtained, hence the information about the state s has been transferred to the symbol A, so it now encodes the state and the current symbol of the machine M . Based on this information, the new state q j is chosen. Finally, symbol D 0 is transformed to symbol ε, which is further deleted.

We remark that it could be possible that another symbol from the string is transformed to A 0,k (not necessarily the first one). In this case the computation will not yield a valid result because the state symbol will not be present in the first position and the corresponding symbol ε will never be erased, see [START_REF] Alhazov | Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors[END_REF] for more details. Now we explain the simulation in more details. We start with the remark that in each step only one symbol of a string w can be changed (by substitution, insertion or deletion) yielding w . This implies that |φ(w) -φ(w )| ≤ 2. In many cases this allows us to predict the change in the polarization (and thus the communication to another node), based on the above difference and the current node polarization.

Assume that the string q 0 s w is present in node 1. First, we suppose that there is an instruction q s → q j a k in M . Then, only the rule 1.1 is applicable, producing the string q - k,j w. Since the initial string had neutral polarization, this rule application changes the polarization of the string to negative and during the communication step this string is sent to nodes 2, 4 and 5. In node 5 there is no rule applicable to this string, so it will never exit this node. In node 4, rule 4.1 can be applied several times, but this will further decrease the value of the string, which will remain negative, so it will never be able to get out of nodes 4 and 5.

In node 2 the insertion rule 2.1 is applied yielding q - k,j wA + 0 . Clearly, this string has a neutral polarization, so it will return back to node 1. Next, we discuss the evolution of strings of form q - k-t,j wA + t , 0 ≤ t ≤ k -2 in node 1:

q - k-t,j wA + t ⇒ 1.2 q 0 k-t-1,j wA + t ⇒ 3.1 q 0 k-t-1,j wA 0 t+1 ⇒ 1.5 ⇒ 1.5 q0 k-t-1,j wA 0 t+1 ⇒ 1.3 q0 k-t-1,j w Â0 t+1 ⇒ 3.2 ⇒ 3.2 q - k-t-1,j w Â+ t+1 ⇒ 1.6 q - k-t-1,j wA + t+1
During first two steps only rules 1.2 and 3.1 are applicable (and they change the polarization of the string). Next, rules 1.3, 1.4 and 1.5 are applicable. It can be easily seen that if 1.3 is applied yielding the string q 0 k-t-1,j w Â+ t+1 , then no more applicable rule is present in node 3. If rule 1.4 is applied then the only possible continuation is the application of the sequence of rules 3.4 and 1.5 yielding the string q0 k-t-1,j wa 0 t+1 in node 1. Clearly, there are no more applicable rules and this string cannot evolve anymore.

So, rule 1.5 has to be applied. Next, there is a choice between the application of 1.3 and 1.4. In case of the application of 1.4, either 3.4 or 3.2 is applicable. The first application yields to the case discussed before, while the second application produces the following evolution not yielding any result:

q0 k-t-1,j w Ǎ+ t+1 ⇒ 3.2 q - k-t-1,j w Ǎ+ t+1 ⇒ 1.2 q 0 k-t-2,j w Ǎ+ t+1 ⇒ 3.4 ⇒ 3.4 q 0 k-t-2,j wa 0 t+1 ⇒ 1.5 q0 k-t-2,j wa 0 t+1
So, on the fourth step rule 1.3 should be applied. Then the only applicable rule is 3.2. Now, if rule 1.6 is not applied, then on the next step (after the application of 1.2) no more rules will be applicable to the corresponding string in node 3.

Hence, the procedure described above permits to evolve the string q - k,j wA + 0 into q - 1,j wA + k-1 . Now, the sequence described above produces the string q - 0,j wA + k , which cannot evolve anymore. However, another evolution now becomes possible (by choosing 1.4 instead of 1.3):

q - 1,j wA + k-1 ⇒ 1.2 q 0 0,j wA + k-1 ⇒ 3.1 q 0 0,j wA 0 k ⇒ 1.5 q0 0,j wA 0 t+1 ⇒ 1.4 ⇒ 1.4 q0 0,j w Ǎ0 k ⇒ 3.3 q 0 j w Ǎ+ k ⇒ 3.4 q 0 j wa 0 k
We remark that if rule 3.4 is applied instead of 3.3, then corresponding string cannot evolve. This concludes the discussion of the simulation of the rule q s → q j a k of M . Now consider that there is an instruction q s a k → q j in M to be simulated. Then, only rule 1.7 is applicable, producing the string X - s w. Since the initial string had neutral polarization, this rule application changes the polarization of the string to negative and during the communication step this string is sent to the nodes 2, 4 and 5. In node 5 there is no rule applicable to this string, so it will never exit this node. In node 2, rule 2.1 can be applied yielding X - s wA + 0 in node 1 to which no further rule is applicable.

In node 4 rules 4.1 and 4.2 are applicable. If 4.2 is applied, then the polarization of the resulting string is positive and the string will be lost. Hence 4.1 should be applied, yielding X - s A - 0,k w (w = a k w). Now again both rules 4.1 and 4.2 are applicable. This time using rule 4.2 allows to obtain the neutral string D + s A - 0,k w which further goes to node 1. In the other case, the corresponding string will always be negative. Now let us consider the evolution of strings of type D + s-t A - t,k w , 0 ≤ t ≤ s -1 being in node 1. Using the same technique as in the case above the decrement of the index of D and the increment of the index of A is performed, with the rules 1.8, 1.9, 1.10, 1.11, 2.5, and 2.6 now having a similar function as the rules 1.2, 1.5, 1.3, 1.6, 2.1, and 2.2. Hence, we obtain:

D + s-t A - t,k w ⇒ 1.8 D + s-t A 0 t+1,k w ⇒ 2.5 D 0 s-t-1 A 0 t+1,k w ⇒ 1.9 ⇒ 1.9 D 0 s-t-1 Â0 t+1,k w ⇒ 1.10 D+ s-t-1 Â0 t+1,k w ⇒ 2.6 ⇒ 2.6 D+ s-t-1 A - t+1,k w ⇒ 1.6 D+ s-t-1 A - t+1,k w ⇒ 1.11 D + s-t-1 A - t+1,k w
It can easily be verified that the few possible variations of the computation above (not using rule 1.9 or using 1.12 instead of 1.9) immediately yield strings that cannot evolve anymore. Hence, we obtain that from D + s A - 0,k w only the string D + 0 A - s,k w can be obtained (in node 1). At this point two rules are applicable: 1.8 and 1.12. Using rule 1.8 yields D + 0 A 0 s+1,k w in node 3, where only rule 3.7 is applicable, yielding ε -A 0 s+1,k w . However, the last string is negative, so it is lost during the communication step. The other possibility gives the following evolution:

D + 0 A - s,k w ⇒ 1.
12 D + 0 q+ j w ⇒ 3.7 ε -q+ j w ⇒ 1.13 ε -qj w ⇒ 4.3 ε -q 0 j w ⇒ 5.1 q 0 j w

We remark that last two operations can be done in a reverse order (if the string first travels to node 5 and then to node 4). The additional application of rule 4.1 traps the string in nodes 4 and 5.

Finally, we show how a terminal string is obtained as a result. We can assume that the last instruction of M is an instruction of type q s a k → q 0 . Then rule 4.4 produces the word q + 0 w , which being positive is sent to node 6, where rule 6.1 is applied producing a neutral string w , which further arrives in node 7.

Corollary 1. For any CPM5 M = (Σ, T, Q, q 1 , q 0 , R) in normal form there exists a NePEP with terminal extraction with five cells Γ = (V, T, H, R, φ s , i 1 , i 0 ) being able to simulate the computations of M .

Proof. The assertion can be easily proved by deleting nodes 6 and 7 from the previous construction, as well as by adding the rule q 0 0 → ε -to processor 1.

Conclusion and Future Research

In this paper we have improved the number of cells necessary to obtain computational completeness with networks of polarized evolutionary processors with elementary polarizations -1, 0, 1 of symbols to seven. In the case of not requiring a special output node and just taking all terminal strings as results even only five nodes have been shown to be sufficient. The construction given in this paper, like the previous ones for networks of polarized evolutionary processors makes intensive use of the control given by the structure of the communication graph. On the other hand, in [START_REF] Alhazov | Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors[END_REF] the results were obtained for several specific regular graph structures as complete graphs, star-like and even linear graphs. Hence, an interesting question for future research arises when asking for the ingredients and the number of cells needed to obtain computational completeness for variants of networks of polarized evolutionary processors based on such specific graph structures. Finally, we also may look for reducing the number seven (five for the case of terminal extraction) of cells needed to obtain computational completeness with networks of polarized evolutionary processors with elementary polarizations -1, 0, 1 of symbols.

  in ) = {w} and C (w) 0 (n) = ∅ for all other nodes x ∈ X H \ {n in }.The computation of Γ on the input word w ∈ V * is a sequence of configurations C