Lila Kari
email: lila.kari@uwaterloo.ca

Timothy Ng

State Complexity of Simple Splicing

Splicing, as a binary word/language operation, was inspired by the DNA recombination under the action of restriction enzymes and ligases, and was first introduced by Tom Head in 1987. Splicing systems as generative mechanisms were defined as consisting of an initial starting set of words called an axiom set, and a set of splicing rules-each encoding a splicing operation-, as their computational engine to iteratively generate new strings starting from the axiom set. Since finite splicing systems (splicing systems with a finite axiom set and a finite set of splicing rules) generate a subclass of the family of regular languages, descriptional complexity questions about splicing systems can be answered in terms of the size of the minimal deterministic finite automata that recognize their languages. In this paper we focus on a particular type of splicing systems, called simple splicing systems, where the splicing rules are of a particular form. We prove a tight state complexity bound of 2 n -1 for (semi-)simple splicing systems with a regular initial language with state complexity n ≥ 3. We also show that the state complexity of a (semi-)simple splicing system with a finite initial language is at most 2 n-2 + 1, and that whether this bound is reachable or not depends on the size of the alphabet and the number of splicing rules.

Introduction

In [START_REF] Head | Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors[END_REF] Head described a language-theoretic operation, called splicing, which models DNA recombination, a cut-and-paste operation on DNA double-stranded molecules, under the action of restriction enzymes and ligases. A splicing system is a formal language model which consists of a set of initial words, I (representing double-stranded DNA strings), and a set of splicing rules R (representing restriction enzymes). The most commonly used definition for a splicing rule is a quadruplet of words r = (u 1 , v 1 ; u 2 , v 2 ). This rule splices two words x 1 u 1 v 1 y 1 and x 2 u 2 v 2 y 2 : the words are cut between the factors u 1 , v 1 , respectively u 2 , v 2 , and the prefix (the left segment) of the first word is recombined by catenation with the suffix (the right segment) of the second word; see Figure 1 and also [START_REF] Pȃun | On the splicing operation[END_REF]. The words u 1 v 1 and u 2 v 2 are the restriction sites in the rule r. A splicing system generates a language which contains every word that can be obtained by successively applying rules to axioms and the intermediately produced words. The most natural variant of splicing systems, often referred to as finite splicing systems, is to consider a finite set of axioms and a finite set of rules.

Several different types of splicing systems have been proposed in the literature, and Bonizzoni et al. [START_REF] Bonizzoni | Separating some splicing models[END_REF] showed that the classes of languages they generate are related. Shortly after the introduction of splicing in formal language theory, Culik II and Harju [START_REF] Culik | Splicing semigroups of dominoes and DNA[END_REF] proved that finite splicing systems can only generate regular languages; see also [START_REF] Head | Splicing and regularity[END_REF][START_REF] Pixton | Regularity of splicing languages[END_REF]. Gatterdam [START_REF] Gatterdam | Splicing systems and regularity[END_REF] gave (aa) * as an example of a regular language which cannot be generated by a finite splicing system; thus, the class of languages generated by finite splicing systems is strictly included in the class of regular languages. Descriptional complexity considers the complexity of a language in terms of the size of a computational device (in this case splicing system) that generates or recognizes it. For instance, Mateescu et al. [START_REF] Mateescu | Simple splicing systems[END_REF] consider a number of descriptional complexity measures for simple splicing systems, such as the number of rules, the number of words in the initial language, the maximum length of a word in the initial language, and the sum of the lengths of all words in the initial language. Loos et al. [START_REF] Loos | Descriptional complexity of splicing systems[END_REF] consider the descriptional complexity of finite splicing systems by using the number of rules, the length of the rules, and the size of the initial language as complexity measures. Pȃun [START_REF] Pȃun | On the splicing operation[END_REF] proposed using the radius, the largest u i in a rule, as a descriptional complexity measure.

As the class of languages generated by splicing systems forms a subclass of the family of regular languages, their descriptional complexity can also be considered in terms of the finite automata that recognize them. For example, Loos et al. [START_REF] Loos | Descriptional complexity of splicing systems[END_REF] gave a bound on the number of states required for a nondeterministic finite automaton to recognize the language generated by an equivalent finite splicing system.

We focus our attention on simple splicing systems, that is, splicing systems where the rules (u 1 , v 1 ; u 2 , v 2 ) are of a particular form: u 1 = u 2 = a, are singleton letters, and v 1 = v 2 = ε are the empty word. The descriptional complexity of simple splicing systems was considered by Mateescu et al. [START_REF] Mateescu | Simple splicing systems[END_REF] in terms of the size of a right linear grammar that generates a simple splicing language. Here we consider the descriptional complexity of simple splicing systems in terms of deterministic state complexity [START_REF] Gao | A survey on operational state complexity[END_REF]. In other words, we measure the descriptional complexity of a simple splicing system in terms of the size of the minimal deterministic finite automaton that recognizes the language generated by the splicing system.

In this paper, we prove tight state complexity bounds for simple and semisimple splicing systems with regular and finite initial languages. In Section 2, we fix notation and definitions for simple splicing systems. We consider the state complexity of simple splicing systems with regular and finite initial languages in Section 3. In Section 4, we give tight state complexity bounds for semi-simple splicing systems with finite initial languages. We consider the state complexity of the crossover operation related to simple splicing systems in Section 5.

Preliminaries

Let Σ be a finite alphabet. We denote by Σ * the set of all finite words over Σ, including the empty word, which we denote by ε. We denote the length of a word w by |w| = n. If w = xyz for x, y, z ∈ Σ * , we say that x is a prefix of w, y is a factor of w, and z is a suffix of w.

A deterministic finite automaton (DFA) is a tuple A = (Q, Σ, δ, q 0 , F ) where Q is a finite set of states, Σ is an alphabet, δ is a function δ : Q × Σ → Q, s ∈ Q is the initial state, and F ⊂ Q is a set of final states. We extend the transition function δ to a function Q × Σ * → Q in the usual way. A DFA A is complete if δ is defined for all q ∈ Q and a ∈ Σ. We will make use of the notation q w -→ q for δ(q, w) = q , where w ∈ Σ * and q, q ∈ Q. A state q ∈ Q is called a sink state if δ(q, a) = q for all a ∈ Σ and q ∈ F .

Each letter a ∈ Σ defines a transformation of the state set Q. Let δ a : Q → Q be the transformation on Q induced by a, defined by δ a (q) = δ(q, a). We extend this definition to words by composing the transformations

δ w = δ a1 • δ a2 • • • • • δ an for w = a 1 a 2 • • • a n . We denote by im δ a the image of δ a , defined im δ a = {δ(p, a) | p ∈ Q}.
The language recognized or accepted by A is L(A) = {w ∈ Σ * | δ(q 0 , w) ∈ F }. A state q is called reachable if there exists a string w ∈ Σ * such that δ(q 0 , w) = q. Two states p and q of A are said to be equivalent if δ(p, w) ∈ F if and only if δ(q, w) ∈ F for every word w ∈ Σ * . A DFA A is minimal if each state q ∈ Q is reachable from the initial state and no two states are equivalent. The state complexity of a regular language L is the number of states of the minimal complete DFA recognizing L [START_REF] Gao | A survey on operational state complexity[END_REF].

A nondeterministic finite automaton (NFA) is a tuple A = (Q, Σ, δ, I, F ) where Q is a finite set of states, Σ is an alphabet, δ is a function δ :

Q × Σ → 2 Q , I ⊆ Q is a set of initial
states, and F is a set of final states. The language recognized by an NFA A is L(A) = {w ∈ Σ * | q∈I δ(q, w) ∩ F = ∅}. As with DFAs, transitions of A can be viewed as transformations on the state set. Let δ a : Q → 2 Q be the transformation on Q induced by a, defined by δ a (q) = δ(q, a). The image of δ a is defined by im δ a = {δ(p, a) | p ∈ Q}. We make use of the notation P w -→ P for P = q∈P δ(q, w), where w ∈ Σ * and P, P ⊆ Q.

Simple Splicing Systems

In this paper we will use the notation of Pȃun [START_REF] Pȃun | On the splicing operation[END_REF], even though simple splicing systems can be defined using any of the three definitions of splicing. The splicing operation is defined via sets of quadruples r = (α 1 , α 2 ; α 3 , α 4 ) with α 1 , α 2 , α 3 , α 4 ∈ Σ * called splicing rules. For two strings x = x 1 α 1 α 2 x 2 and y = y 1 α 3 α 4 y 2 , applying the rule r = (α 1 , α 2 ; α 3 , α 4 ) produces a string z = x 1 α 1 α 4 y 2 , which we denote by (x, y) r z.

A splicing scheme is a pair σ = (Σ, R) where Σ is an alphabet and R is a set of splicing rules. For a splicing scheme σ = (Σ, R) and a language L ⊆ Σ * , we denote by σ(L) the language

σ(L) = L ∪ {z ∈ Σ * | (x, y) r z, where x, y ∈ L, r ∈ R}.
Then we define σ 0 (L) = L and σ i+1 (L) = σ(σ i (L)) for i ≥ 0 and

σ * (L) = lim i→∞ σ i (L) = i≥0 σ i (L).
For a splicing scheme σ = (Σ, R) and an initial language L ⊆ Σ * , we say the triple H = (Σ, R, L) is a splicing system. The language generated by H is defined by L(H) = σ * (L).

Mateescu et al. [START_REF] Mateescu | Simple splicing systems[END_REF] define a restricted class of splicing systems called simple splicing systems. A simple splicing system is a triple H = (Σ, M, I), where Σ is an alphabet, M ⊆ Σ is a set of markers, and I is a finite initial language over Σ. For a ∈ M , we have (x, y) a z if and only if x = x 1 ax 2 , y = y 1 ay 2 , and z = x 1 ay 2 for some

x 1 , x 2 , y 1 , y 2 ∈ Σ * .
In other words, a simple splicing system is a system in which the set of rules is M = {(a, ε; a, ε) | a ∈ M } and the initial language I is finite. Since the rules are determined solely by our choice of M ⊆ Σ, the set M is used in the definition of the simple splicing system rather than the set of rules M. Based on these properties, one can deduce that the class of languages generated by simple splicing systems is subregular [START_REF] Culik | Splicing semigroups of dominoes and DNA[END_REF][START_REF] Pixton | Regularity of splicing languages[END_REF]. Mateescu et al. [START_REF] Mateescu | Simple splicing systems[END_REF] show that these languages form a proper subclass of the extended star-free languages.

In this paper, we will relax the condition that the initial language of a simple splicing system must be a finite language. We will consider also simple splicing systems with regular initial languages. By [START_REF] Pȃun | On the splicing operation[END_REF], it is clear that such a splicing system will also produce a regular language. In the following, we will use the convention that I denotes a finite language and L denotes an infinite language.

State Complexity of Simple Splicing

In this section, we will give tight state complexity bounds for simple splicing systems with regular and finite initial languages. First, we will define an NFA that recognizes the language of a given simple splicing system. The construction follows a more general construction due to Loos et al. [START_REF] Loos | Descriptional complexity of splicing systems[END_REF] for finite splicing systems. This construction is a simplification of a construction by Pixton [START_REF] Pixton | Regularity of splicing languages[END_REF], which itself is a simplification of the original proof of regularity of finite splicing due to Culik and Harju [START_REF] Culik | Splicing semigroups of dominoes and DNA[END_REF].

Proposition 1. Let H = (Σ, M, L) be a simple splicing system with a regular initial language L and let L be recognized by a DFA with n states. Then there exists an NFA A H with n states such that L(A H ) = L(H).

Proof. Let H = (Σ, M, L) and let A = (Q, Σ, δ, q 0 , F ) be a DFA for L. We will define the NFA A H = (Q , Σ, δ , q 0 , F ), where

Q = Q ∪ Q M with Q M = {p a , p a | a ∈ M } and the transition function δ is defined -δ (q, a) = {δ(q, a)} if q ∈ Q and a ∈ Σ, -δ (q, ε) = {p a } if q ∈ Q, a ∈ M , and δ(q, a) is not the sink state, -δ (p a , a) = {p a } if p a ∈ Q M , -δ (p a , ε) = im δ a if p a ∈ Q M and a ∈ M
First, we describe the construction of [START_REF] Loos | Descriptional complexity of splicing systems[END_REF]. Let M = {(a, ε; a, ε) | a ∈ M } be the set of rules for H. For each rule (α 1 , α 2 ; α 3 , α 4 ) ∈ M, add new states and transitions corresponding to α 1 α 4 and α 3 α 2 . That is, if

α 1 = a 1 • • • a i , α 2 = b 1 • • • b j , α 3 = c 1 • • • c k , and α 4 = d 1 • • • d , then add states and transitions corresponding to a path r 0 a1 -→ r 1 a2 -→ • • • d -→ r i+ for α 1 α 4 and a path s 0 c1 -→ s 1 c2 -→ • • • bj -→ s j+k corresponding to α 3 α 2 . Now consider each path q α1α2 ---→ q in A
such that q is reachable from the initial state q 0 and a final state of A is reachable from q . We add an ε-transition from q to r 0 and from s j+k to q . Similarly, for each path t α3α4 ---→ t , add ε-transitions from t to s 0 and from r i+ to t . Now, since H is a simple splicing system, this construction can be simplified further. Since every rule of H is of the form (a, ε; a, ε), we only need to add states and transitions for p a a -→ p a for each rule. Then add ε-transitions from states q of A to p a if q has an outgoing transition on a to a non-sink state of A. From each state p a , add ε-transitions to each state of A with an incoming transition on a. Recall that im δ a is the image of the transformation of δ induced by a, and therefore it is the set of states of A with an incoming transition on a. Finally, we can simplify this NFA by removing ε-transitions in the usual way to obtain an NFA A H = (Q, Σ, δ , q 0 , F ), where

δ (q, a) =      {δ(q, a)} if δ(q, a) is the sink state, {δ(q, a)} if a ∈ M , im δ a if a ∈ M .
Figure 2 illustrates the new states and transitions added for a ∈ M before and after ε-removal. Observe that by removing the ε-transitions, we also remove the states that were initially added earlier in the construction of A H . Thus, the state set of A H is exactly the state set of the DFA A recognizing L.

Given a splicing system H = (Σ, M, L), one can obtain a DFA that recognizes L(H) by performing the subset construction on A H . As shown in Proposition 1, if L is recognized by a DFA with n states, then A H also has n states. By applying the subset construction and observing that the empty set is not reachable from any subset of Q in A H , this gives an upper bound of 2 n -1 states for a DFA equivalent to A H .

We will now show that there exists a family of regular languages L n with state complexity n such that a simple splicing system H = (Σ, M, L n ) with one marker requires 2 n -1 states for an equivalent DFA to recognize it. Proposition 2. For |Σ| ≥ 3 and n ≥ 3, there exists a simple splicing system with a regular initial language H = (Σ, M, L n ) with |M | = 1 where L n is a regular language with state complexity n such that the minimal DFA for L(H) requires at least 2 n -1 states.

Proposition 2 is proved via the family of languages L n accepted by DFAs A n , shown in Figure 3, with M = {c}. Together, Propositions 1 and 2 give the following result.

Theorem 3. For a simple splicing system with a regular initial language H = (Σ, M, L n ) where M ⊆ Σ and L n ⊆ Σ * has state complexity n, the state complexity of L(H) is at most 2 n -1 and this bound can be reached in the worst case.

We will now consider simple splicing systems with a finite initial language. We will show that the upper bound of Proposition 1 is not reachable in this case. Proposition 4. Let H = (Σ, M, I) be a simple splicing system with a finite initial language, where I is a finite language recognized by a DFA A with n states. Then a DFA recognizing L(H) requires at most 2 n-2 + 1 states.

We will show that this bound is reachable. We note that the lower bound witness used in the following lemma is defined over an alphabet with size exponential in the number of states of the DFA recognizing the initial language. Lemma 5. There exists a simple splicing system with a finite initial language H = (Σ, M, I n ) where I n is a finite language with state complexity n such that a DFA recognizing L(H) requires 2 n-2 + 1 states.

Together, Proposition 4 and Lemma 5 give the following result. Theorem 6. For a simple splicing system with a finite initial language H = (Σ, M, I n ) where M ⊆ Σ and I n ⊆ Σ * has state complexity n, the state complexity of L(H) is at most 2 n-2 + 1 and this bound can be reached in the worst case.

The bound of Lemma 5 is reached by a witness defined over an alphabet size of 2 n-3 + 1. An obvious question is whether this bound can be reached via a smaller alphabet. We will consider in the following the state complexity of simple splicing systems with a finite initial language for small, fixed alphabets. We begin with a general observation on the transition function of a DFA recognizing the language of a simple splicing system. Lemma 7. Let H = (Σ, M, L) be a simple splicing system with a regular initial language and let A H be an NFA recognizing L(H). If a ∈ M and δ is the

transition function of A H , then | im δ a | = 2.
First, we will consider simple splicing systems with a finite initial language defined over a unary alphabet. Proposition 8. Let H = ({a}, M, I) be a simple splicing system where M is nonempty and I is a finite language containing a word of length at least 2. Then the minimal DFA recognizing L(H) has exactly two states.

Next, we consider simple splicing systems with a finite initial language defined over a binary alphabet. We will show that the small size of the alphabet restricts the number of transformations that can be performed on the state set and that the upper bound on the number of states falls far below the upper bound of Proposition 4 as a result. Proposition 9. Let H = ({a, b}, M, I) be a simple splicing system where I is a finite language with state complexity n. Then the minimal DFA recognizing L(H) has at most 2n -3 states and this bound is reachable in the worst case.

We will now consider the state complexity of simple splicing systems with a finite initial language defined over a ternary alphabet. We will show that the upper bound of 2 n-2 + 1 from Proposition 4 cannot be reached with an alphabet of size 3.

Proposition 10. Let H = ({a, b, c}, M, I) be a simple splicing system where I is a finite language with state complexity n. Then the minimal DFA recognizing L(H) has at most

2 n 2 + 1 states if n is even and 3 • 2 n-3 2 + 1 states if n is odd.
We note that the upper bound of the previous lemma is similar to the state complexity of the reversal operation on finite languages [START_REF] Câmpeanu | State complexity of basic operations on finite languages[END_REF]. We will use this result as inspiration for a family of lower bound witnesses in the following lemma.

Lemma 11. There exists a family of finite languages I n ⊆ {a, b, c} * , for n ≥ 4, recognized by a DFA with n states such that the minimal DFA for a simple splicing system H = ({a, b, c}, M, I n ) requires at least

2 n 2 + 1 states if n is even and 3 • 2 n-3 2 + 1 states if n is odd.
The family of witness languages I n used to prove Lemma 11 is accepted by DFAs A n , shown in Figure 4, with M = {c}. + 1 states if n is odd and this bound can be reached in the worst case.

0 start 1 • • • n 2 -1 n 2 • • • n -2 n -1 a, b, c a,

State Complexity of Semi-simple Splicing

In this section, we will give tight state complexity bounds for semi-simple splicing systems with regular and finite initial languages. In particular, we will show that the upper bound is reachable for semi-simple splicing systems with a finite initial language defined over a fixed alphabet.

Goode and Pixton [START_REF] Goode | Semi-simple splicing systems[END_REF] generalize simple splicing systems by defining semisimple splicing systems. A splicing system is semi-simple if every rule is of the form (a, ε; b, ε) for a, b ∈ Σ. Again, rather than explicitly define a set of rules M, we refer instead to the set M (2) ⊆ Σ × Σ of pairs of symbols, which determines the set of rules. As with simple splicing systems, one can conclude that the class of languages generated by semi-simple splicing systems is subregular [START_REF] Culik | Splicing semigroups of dominoes and DNA[END_REF][START_REF] Pixton | Regularity of splicing languages[END_REF].

In the following, we will give a construction for an NFA that recognizes the language generated by a semi-simple splicing system. As with the NFA for simple splicing systems from Proposition 1, the construction will follow the more general construction for finite splicing systems of Loos et al. [START_REF] Loos | Descriptional complexity of splicing systems[END_REF].

Proposition 13. Let H = (Σ, M (2) , L) be a semi-simple splicing system with a regular initial language. Then there exists an NFA B H with n states such that L(B H ) = L(H).

It is clear from Proposition 13 that for a given regular language L, the language of a semi-simple splicing system H = (Σ, M (2) , L) can require 2 n -1 states in the worst case. Since a simple splicing system is also a semi-simple splicing system, the lower bound witness from Proposition 2 holds. Therefore, we can focus on the more interesting case of semi-simple splicing systems with finite initial languages. First, we observe that even with semi-simple splicing rules, the upper bound on the number of states for a DFA recognizing a semi-simple splicing system with a finite initial language remains the same. Proposition 14. Let H = (Σ, M (2) , I) be a semi-simple splicing system with a finite initial language where I is a finite language recognized by a DFA A with n states. Then a DFA recognizing L(H) requires at most 2 n-2 + 1 states.

The proof of this fact is identical to the proof of Proposition 4.

Recall from Lemma 5, that the lower bound witness for simple splicing systems with a finite initial language was defined over an alphabet with size exponential in the state complexity of the initial language. We will show in the following lemma that for semi-simple splicing systems with a finite initial language, a lower bound witness defined over an alphabet of size 3 exists. Lemma 15. Let n ≥ 4. Then there exists a semi-simple splicing system with a finite initial language H = (Σ, M (2) , I n ) where |Σ| = 3 and I n is a finite language with state complexity n such that L(H) is recognized by a DFA that requires at least 2 n-2 + 1 states.

The family of witness languages I n of Lemma 15 is accepted by DFAs A n , shown in Figure 5, with Σ = {a, b, c} and M (2) = {(a, c)}. From Proposition 14 and Lemma 15, we have the following result.

0 start 1 • • • n -3 n -2 n -1 c c a,
Theorem 16. For a semi-simple splicing system with a finite initial language H = (Σ, M (2) , I n ) where M ⊆ Σ and I n ⊆ Σ * has state complexity n, the state complexity of L(H) is at most 2 n-2 + 1 and this bound can be reached in the worst case.

State Complexity of the Crossover Operation

In this section, we will give tight state complexity bounds for the crossover operation [START_REF] Ceterchi | An algebraic characterization of semi-simple splicing[END_REF], which can be thought of as a single step of semi-simple splicing. Mateescu et al. [START_REF] Mateescu | Simple splicing systems[END_REF] gave an algebraic characterization of the class of languages generated by simple splicing systems based on the crossover operation therein. A similar such characterization for the class of languages generated by semi-simple splicing systems is given by Ceterchi [START_REF] Ceterchi | An algebraic characterization of semi-simple splicing[END_REF].

For M = M 1 × M 2 ⊆ Σ × Σ, define the operation M on two strings u, v ∈ Σ + by u M v = u av if u = u a, v = bv for (a, b) ∈ M , u , v ∈ Σ * , undefined otherwise.
Then for two languages L 1 , L 2 ⊆ Σ * , we have

L 1 M L 2 = {x M y | x ∈ L 1 , y ∈ L 2 }.
The operation M is a variant of the Latin product defined in [START_REF] Golan | Semirings and their Applications[END_REF]. Based on M , we define the crossover operation M for M ⊆ Σ × Σ and two languages

L 1 , L 2 ⊆ Σ * by L 1 M L 2 = pref(L 1 ) M suff(L 2 ),
where pref(L 1 ) is the set of prefixes of words in L 1 and suff(L 2 ) is the set of suffixes of words in L 2 . From this definition, the operation M can be viewed as a combination of operations under each of which the regular languages are closed. Therefore, it is easy to see that the regular languages are closed under M . Note that by restricting M to pairs (a, a) for a ∈ Σ, we get an operation that can be thought of as a single step of simple splicing. The operation M , when restricted to pairs of the form (a, a) has some similarities to many operations that have been studied in the literature, such as the chop operation [START_REF] Holzer | Descriptional and computational complexity of finite automata -A survey[END_REF] and the word blending operation [START_REF] Enaganti | Word blending in formal languages: The Brangelina effect[END_REF]. In fact, word blending can be seen as a special case of the crossover operation, taking M = {(a, a) | a ∈ Σ}.

We will now give a DFA construction for the crossover of two regular languages.

Proposition 17. Let A and B be two DFAs defined over Σ with m and n states, respectively. Then for any M ⊆ Σ × Σ, there exists a DFA C such that

L(C) = L(A) M L(B) and C has at most m • 2 n states. Proof. Let A = (Q A , Σ, δ A , s A , F A ) and B = (Q B , Σ, δ B , s B , F B ) be two DFAs. We will construct a DFA C = (Q C , Σ, δ C , s C , F C ) that recognizes A M B for some M ⊆ Σ × Σ, defined by -Q C = Q A × 2 Q B , -s C = s A , ∅ , -F C = { q, P ∈ Q A × 2 Q B | P ∩ F B = ∅},
and the transition function δ C is defined for q ∈ Q A , P ⊆ Q B , and a ∈ Σ by δ C ( q, P , a) = q , P , where q = δ A (q, a) and We will show that the bound of Proposition 17 is reachable, even when M is restricted to pairs of the form (a, a).

Conclusion

We have given tight bounds for the state complexity of simple and semi-simple splicing systems and the associated crossover operation. In almost all cases, the exponential upper bound was easily reached via splicing systems defined over a fixed-size alphabet with one rule. The exception is with simple splicing systems with a finite initial language, where a natural open problem to consider is the worst-case state complexity when the initial languages are defined over alphabets of size between 3 and 2 n-3 .

Fig. 1 .

 1 Fig. 1. Splicing of the words x1u1v1y1 and x2u2v2y2 by the rule r = (u1, v1; u2, v2).

Fig. 2 .

 2 Fig. 2. New states and transitions for a ∈ M (left), after ε-removal (right)

Fig. 3 .

 3 Fig. 3. The DFA An

Fig. 4 .Theorem 12 . 2 n 2 + 1

 412221 Fig. 4. The ternary witness DFA An

Fig. 5 .

 5 Fig. 5. The ternary witness DFA An

P

  = im(δ B ) b if (a, b) ∈ M and q is not a sink state, p∈P δ B (p, a) otherwise. Informally, the machine traces a computation of A and computations of B. For each pair (a, b) ∈ M , whenever a transition on a occurs in A, all states of B with incoming transitions on b are added to the computation. It is clear from the definition of C that L(C) = L(A) M L(B) and it has at most m • 2 n states.

Lemma 18 .Fig. 6 .

 186 Fig.6. The DFAs Am (above) and Bn (below)


Kitti Gelle
email: kgelle@inf.u-szeged.hu

Szabolcs Iván

The syntactic complexity of semi-flower languages

Semi-flower languages are those of the form L * for some finite maximal prefix code L, or equivalently, those recognizable by a so-called semi-flower automaton, in which all the cycles have a common state q0, which happens to be the initial state and the only accepting state. We show that the syntactic complexity of these languages is exactly n n -n! + n (where n stands for the state complexity as usual) and that this bound is reachable with an alphabet of size n.

Introduction

The state complexity of a regular language is the number of states of its minimal automaton, or equivalently, the number of classes of its syntactic rightcongruence. The syntactic complexity of a language is the number of classes of its syntactic congruence, or equivalently, the size of the transition monoid of its minimal automaton.

It is clear (and already observed by Maslov [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF]) that if a language has state complexity n, then it can have a syntactic complexity of at most n n as there are only so many transformations of an n-element set. Moreover, as three functions (an elementary swap, a circular permutation and a rank-(n -1) function) can generate all the transformations of a finite set, this maximal syntactic complexity can be reached by an automaton over a ternary alphabet. For the case of binary alphabets, Holzer and König [START_REF] Holzer | On deterministic finite automata and syntactic monoid size[END_REF] gave upper bounds for the maximal size of the transition monoid of an n-state minimal automaton while for the unary case and for the binary case for prime n, they determined a sharp bound.

When C is a class of regular languages, then its syntactic complexity is a function over the single integer variable n, namely it is the maximum possible syntactic complexity of a language belonging to C and having state complexity at most n. That is, for the whole class of the regular languages, this complexity is n n . In the recent years, there is a growing interest of determining the syntactic complexity of subregular classes of languages (proper subclasses of the regular languages), e.g. for ideal and prefix-or factor closed languages [START_REF] Brzozowski | Syntactic complexity of ideal and closed languages[END_REF], prefix-, suffix-, bifix-and factor-free languages [START_REF] Brzozowski | Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages[END_REF], several classes of star-free languages [START_REF] Brzozowski | Syntactic complexities of six classes of star-free languages[END_REF], Rand J-trivial languages [START_REF] Brzozowski | Syntactic complexity of R-and J-trivial regular languages[END_REF], regular ideals [START_REF] Brzozowski | Syntactic complexity of regular ideals[END_REF] amongst others.

It is also an interesting question to determine the alphabet size needed to reach the maximum possible syntactic complexity: for the whole class of regular languages, an alphabet of ternary size suffices, but e.g. for factor-closed languages an alphabet of size 6 is needed [START_REF] Brzozowski | Syntactic complexity of prefix-, suffix-, bifix-, and factor-free regular languages[END_REF], while for bifix-free languages (n -2) n-3 + (n -3)2 n-3 -1 generators are needed if n ≥ 6 [START_REF] Szyku La | Syntactic complexity of bifixfree regular languages[END_REF].

In the recent years, Singh and Krishna initiated the investigation of semiflower automata [START_REF] Singh | On syntactic complexity of circular semi-flower automata[END_REF][START_REF] Singh | The holonomy decomposition of some circular semiflower automata[END_REF][START_REF] Singh | Semi-Flower Automata[END_REF], which are the minimal automata of valid code words over a finite maximal prefix code. In particular, in [START_REF] Singh | On syntactic complexity of circular semi-flower automata[END_REF] they showed that if a circular semi-flower automaton over a binary alphabet has a single ,,branching point in", or bpi (a state q is called a bpi if there are at least two tuples (p, a) ∈ Q × Σ with pa = q), then it has a linear syntactic complexity, and if it possesses exactly two bpis, then 2n(n + 1) is a sharp bound on its syntactic complexity. Clearly, this is a serious restriction: it essentially restricts the elementary transformations to a circular permutation and some semi-flower transformation of rank at most 2 (for the definitions, see the Notation section). They also remark that over a ternary alphabet there exists a semi-flower automaton with two bpis having larger syntactic complexity than 2n(n + 1).

In this paper we determine that the syntactic complexity of languages recognizable by semi-flower automata (without placing any restriction on the number of their "branch points going in") is n n -n! + n and show that this bound is reachable by an alphabet of size n.

Notation and some facts

We assume the reader has some knowledge in automata and formal language theory (a standard resource is [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]). In this paper an automaton is a triple A = (Q, Σ, •) with Q and Σ being the finite sets of states and input symbols or letters, and • is an action Q × Σ → Q, written in infix notation: q • a for q ∈ Q and a ∈ Σ. The action is extended to words acting on the states in the usual unique way as q • ε = q for the empty word ε and q • (ua) = (q • u) • a for each word u ∈ Σ * and a ∈ Σ. The transformation q → q • u for the word u ∈ Σ * is denoted as u A . The action is also extended to sets of states as

Q • u = {q • u : q ∈ Q }.
When f : Q → Q is a transformation of some set Q, and q ∈ Q is a member of its domain, then we often write q • f for f (q), that is, writing the function application as a right action, moreover, for composing functions we define f • g as q → (q • f ) • g (note the order). This way it holds that (uv

) A = u A • v A .
We denote the transition monoid of an automaton

A = (Q, Σ, •) by T (A), that is, T (A) is the monoid over the set {u A : u ∈ Σ * } ⊆ Q Q , equipped by function composition where u A • v A = (uv) A . For a function f : Q → Q, let rank(f ) stand for |Qf |, the size of the image of f . The automaton B = (Q, ∆, •) is a renaming of the automaton A = (Q, Σ, •) if for each b ∈ ∆ there exists some b ∈ Σ with b B = (b ) A . Since in that case (b 1 . . . b k ) B = (b 1 . . . b k ) A for each k and b 1 , . . . , b k ∈ ∆, we get that T (B) is a submonoid of T (A). The automaton B = (Q , Σ, •) is a sub-automaton of A = (Q, Σ, •) if Q ⊆ Q
and the action of B is the restriction of the action of A: q • a = q • a for each q ∈ Q and a ∈ Σ. The automaton B is a homomorphic image or quotient of A if there exists some surjective mapping h : Q → Q such that h(q •a) = h(q)•a. If the mapping h is a bijection, then the two automata are isomorphic. An automaton which is a homomorphic image of a subautomaton of A is called a divisor of A.

An automaton A = (Q, Σ, •) is minimal with respect to some initial state q 0 ∈ Q and a set F ⊆ Q of final states if {q 0 • u : u ∈ Σ * } = Q and for each pair p = q of distinct states, there exists a word u ∈ Σ * with either pu ∈ F and qu / ∈ F or pu / ∈ F and qu ∈ F . The language recognized by A

= (Q, Σ, •) from q 0 ∈ Q with F ⊆ Q is the set L(A, q 0 , F ) = {u ∈ Σ * : q 0 • u ∈ F } of words. A language L ⊆ Σ * is recognizable or regular if L = L(A, q 0 ,
F ) for some finite automaton A, initial state q 0 and set F of final states. It is well-known that for any regular language L there exists a minimal automaton A L which recognizes L from some initial state with some set of final states, moreover, A L divides every automaton in which L can be recognized.

A is called a semi-flower automaton [START_REF] Singh | Semi-Flower Automata[END_REF] (in short, SFA) if all cycles in A have a common state. An automaton A is called circular if some letter acts as a circular permutation on the states of A, and is a circular semi-flower automaton, CSFA in short [START_REF] Singh | The holonomy decomposition of some circular semiflower automata[END_REF], if it is both circular and semi-flower.

Clearly, any circular automaton A = (Q, Σ, •) is minimal with respect to any initial state q 0 ∈ Q and the set F = {q 0 } of final states: if a induces a circular permutation in A, then we have Q = {q 0 • a k : 0 ≤ k < n} where n = |Q|. On the other hand, if p = q 0 • a k and q = q 0 • a t are distinct states, then p • a n-k = q 0 while q • a n-k = q 0 . Let [n] stand for the set {1, . . . , n}. We call a function f :

[n] → [n] a semi- flower transition over [n] if i < i • f for each 1 ≤ i < n.
We denote the rotation operation by +: for a state i ∈ [n] and an integer k, let i + k stand for (i + k -1) mod n + 1. In particular, n + 1 = 1, and the mapping i → i + 1 (which happens to be a circular permutation) is a semi-flower transition.

The following proposition relates circular semi-flower automata and semiflower transitions: → p k+1 = p 1 be a cycle in A. Then p i ≥ p i+1 for some i, which, as a i induces a semi-flower transition, can happen only if p i = n. Thus, A is semi-flower.

For the other direction, assume A = (Q, Σ, •) is an n-state semi-flower automaton and let q n ∈ Q be a common state of all the cycles of A. Then, considering the graph G with vertex set V = Q -{q n } and edge set {(p, pa) : a ∈ Σ, p, pa ∈ V } we get that G is a directed acyclic graph, hence its vertices can be ordered as q 1 < q 2 < . . . < q n-1 such that for each edge (p, q) of G we have p < q. Then, the mapping q i → i establishes an isomorphism between A and a semi-flower automaton in normal form.

Clearly, if A is a circular semi-flower automaton in normal form, then the letter a inducing a circular permutation of [n] has to induce the function i → i + 1 as this is the only semi-flower permutation over [n].

Minimal circular semi-flower automata and syntactic complexity

A language L is a semi-flower language if L = L(A, q 0 , {q 0 }) for some semiflower automaton A = (Q, Σ, •) and state q 0 ∈ Q, which is a common state of all cycles of A.

A language P ⊆ Σ + is a prefix code if there are no words u, v ∈ P with u being a proper prefix of v, and is a maximal prefix code if additionally, for any word w / ∈ P , the set P ∪ {w} is not prefix-free anymore. If P is a maximal prefix code, u ∈ Σ * is a proper prefix of some member of P and a ∈ Σ is a letter, then ua is still a (not necessarily proper) prefix of some member of P . A good reference on codes is [START_REF] Berstel | Codes and Automata (Encyclopedia of Mathematics and Its Applications)[END_REF].

It holds that semi-flower languages are exactly languages of the form P * for some finite maximal prefix code P ⊆ Σ + . Indeed, given L = L(A, q 0 , {q 0 }) for the semi-flower automaton A, we can take the language P = {u ∈ Σ * : q 0 u = q 0 , q 0 v = q 0 for any proper nonempty prefix v of u} which is a finite language since otherwise some cycle would avoid the initial-final state q 0 . For the other direction, for a finite maximal prefix-free language P one can take the state set as Q = {u ∈ Σ * : u is a proper prefix of some v ∈ P }, define the action as u • a = ε if ua ∈ P and ua otherwise, and pick ε as q 0 , the resulting semi-flower automaton recognizes the language P * .

The syntactic complexity of a class L of regular languages is a unary function over the single variable n: for each n, its value is defined as max |T (A L )| : L ∈ L and A L has at most n states .

Since up to isomorphism and renaming there is only a finite number of automata having at most n states, this notion is well-defined for any class L of regular languages.

In this paper we show that the syntactic complexity of semi-flower languages is exactly n n -n! + n by analyzing the size of T (A) for a particular (circular) semi-flower automaton A = A n for each n.

The transition monoid of semi-flower automata

If in an n-state automaton A, no letter acts as a permutation on the state set, then its transition monoid does not contain any nontrivial permutation, thus in that case,

|T (A)| ≤ n n -n! + 1.
Clearly, if some letter induces a permutation in a semi-flower automaton, then it has to be a circular permutation (otherwise there would be two disjoint cycles in its graph). So in the remaining part of the section we deal with the transition monoid of an n-state circular semi-flower automaton.

Let us begin by handling the permutations present in T (A) when A is a circular semi-flower automaton.

Proposition 2. If f : Q → Q is a permutation belonging to T (A) for some circular semi-flower automaton A over the state set Q, in which a induces a circular permutation, then f is induced by some word of the form a k where 0 ≤ k < n.

Proof. Let us assume A = ([n], Σ, •) is in the normal form specified by Proposition 1. Since the only permutation which is a semi-flower transition is the transformation i → i + 1, b A has to be this function for each letter b inducing a permutation.

Also, if f = (b 1 b 2 . . . b k ) A is a permutation, then each b A i has to be a permutation, thus f = (a k ) A in that case for some k and, as (a n ) A is the identity map, we get f = (a k ) A for some 0 ≤ k < n.

Note that there are n such permutations, so T (A) contains n permutations and all its other members have rank less than n. Hence, the absolute maximum syntactic complexity an n-state (circular) semi-flower automaton can have is n n -n! + n. In the rest of the paper we show that this bound is attainable.

Let us fix n ≥ 1, the state set Q = [n] and the n-state automaton A = (Q, Σ, •) for the rest of the section, where

Σ = {b i : i ∈ [n]}
where for each i ∈ [n], the action of b i is defined as

j • b i = j + 1 if j < n i otherwise.
Since all the functions b A i are semi-flower transitions over [n], A is a semi-flower automaton over n letters. Observe that b 1 induces the circular permutation i → i + 1, thus A is a circular semi-flower automaton. To make a visual distinction, we also refer to b 1 as a and to ease notation, we frequently identify the mapping b A with the letter b.

In the rest of the section we aim to show that T (A) contains all the transformations of [n] with rank less than n. Since the circular permutation induced by a is also present, we also have n permutations in T (A) by Proposition 2, so this yields |T (A)| = n n -n! + n ≥ n n -n! + 1, proving that the syntactic complexity of semi-flower languages is n n -n! + n as well (and this bound is attainable by a circular semi-flower automaton over n letters.)

In the following, we show that several fundamental transformations, as "merging" two states, or "swapping" two states of some proper subset of the state set, each belong to T (A).

Lemma 1. For all p, q ∈ Q, the function f p,q : Q → Q, where p • f = q and for all r = p we have r • f = r, belongs to T (A).

Proof. Let us consider the function f = a n-p •b q+n-p+1 •a p-1 . (Here q+(n-p+1) is understood with the rotation operation from the Notation section, so this value is a member of [n]).

Clearly, for p we have p•a n-p = n, n•b q+n-p+1 = q +n-p+1 (in the rotating sense) and (q + n -p + 1) • a p-1 = q + n = q, so that p • f = q. On the other hand, for any r = p we have r•a n-p = r+n-p = n so (r+n-p)•b q+n-p+1 = r+n-p+1 and (r + n -p + 1) • a p-1 = r + n = r. Thus indeed, r • f = r for each r = p.

For an example, see Figure 1. Fig. 1: The semi-flower transitions creating a function f p,q which merges two states (Here p = 2, q = 4)

As a corollary we can collapse the kernel of any transformation of Q, each kernel class to one member of the class. (Recall that the kernel of a function f :

Q 1 → Q 2 is the equivalence relation ∼ f over Q 1 defined as p ∼ f q ⇔ pf = qf .)
Corollary 1. For any transformation f : Q → Q, there exists some function g ∈ T (A) such that for each p, q ∈ Q, pf = qf if and only if pg = qg;

f p, f q,p f ,q
Fig. 2: Steps for building a swap function for two states (here p = 2, q = 4) from semi-flower transitions. The marked states belong to Q .

For the sets

Q ⊆ Q, let us call a mapping f : Q → Q monotone if i < j, i, j ∈ Q implies i • f < j • f .
Our next lemma states that all the monotone maps belong to T (A). Lemma 4. For each set Q ⊆ Q and monotone mapping f : Q → Q there exists some f ∈ T (A) extending f . Proof. The statement is vacuously satisfied when Q = ∅ so assume Q = ∅.

For two functions f, g : Q → Q, let us define d(f, g) as q∈Q |q •f -q •g|. We show that if for two monotone functions f, g : Q → Q we have d(f, g) > 0, and g has some extension g * ∈ T (A), then there also exists some monotone function g : Q → Q having an extension g * ∈ T (A) with d(f, g ) < d(f, g). As this distance can only have nonnegative integer values, and the identity function is a monotone function belonging to T (A) (so we can start the induction somewhere), this proves the statement.

So let us consider two monotone functions f, g : Q → Q with d(f, g) > 0. This means that there exists some state q ∈ Q with q • f = q • g. Let us choose q so that q • f = q • g for each q < q.

There are two cases: either q • f < q • g or q • g < q • f . If q • f < q • g, then no state r with q • f ≤ r < q • g can be in the image of g: by monotonicity, p • g = r < q • g would yield p < q but by the choice of q, p • g = p • f < q • f holds in that case. By Lemma 1, the function g 0 = f q•g,q•f belongs to T (A), and q • (g • g 0 ) = (q • g) • g 0 = q • f , and since g is injective, we have q • g = q • g if q = q, so that q • g • g 0 = q • g for each q ∈ Q . Observe also that g • g 0 is still a monotone function. As g • g 0 belongs to T (A) if so does g, and d(f, g • g 0 ) < d(f, g), this proves the claim in this subcase.

If q • g < q • f , then consider the following sequence q = q 0 < q 1 < . . . of members of Q : first, let us set q 0 = q, then for each t ≥ 0, if (q t • g) + 1 belongs to the image of g, say p • g = (q t • g) + 1 for the state p ∈ Q , then let us set q t+1 = p, otherwise let q t be the terminating element of the sequence.

As g is a monotone function, we get that q t < q t+1 holds for each t where the sequence is defined for q t+1 . Thus, the sequence has to be finite. Moreover, by construction, the sequence q 0 •g, q 1 •g, . . . contains consecutive states by definition for the states q 0 < q 1 < . . ., thus, by q 0 • g < q 0 • f , applying induction we get q t • g < q t • f for each valid index t. Hence, for the last state q t of the sequence we have by construction that q t • g < q t • f and that (q t • g) + 1 does not belong to the image of g. (Observe that being less than q t • f , the state q t • g cannot be n.) By Lemma 1, the function g 0 = f qt•g,(qt•g)+1 belongs to T (A) so again, for the monotone function g • g 0 we get q t • g • g 0 = (q t • g) + 1 and for any other member q of Q , q • g = q • g • g 0 . Again, g • g 0 belongs to T (A) if so does g, and d(f, g • g 0 < d(f, g), proving this subcase and the lemma as well.

Lemma 5. For each Q Q and injective mapping f : Q → Q there exists some g ∈ T (A) extending f . Proof. Let Q = {q 1 , . . . , q k } with q 1 < . . . < q k and let π : Q → Q be the unique permutation with

q i • π • f < q i+1 • π • f for each 1 ≤ i < k. (That is, q i • π is q j if and only if q i • f is the jth least element of Q • f ). Then f = π • f for the monotone map f : Q → Q with q i • f = (q i • π -1 )
• f , hence by Lemmas 3 and 4 there is some function g ∈ T (A) extending f . This bound can be reached by an alphabet of size n for each n.

Proof. Let f : Q → Q be a function with rank(f ) < n. By Corollary 1, there exists some function g ∈ T (A) mapping each state to a representative of its kernel class, that is, with some

Q Q, |Q | = rank(f ) such that Q • g = Q , satisfying q •g •f = q •f for each state q ∈ Q, moreover, with p•f = q •f implying p•g = q •g.
Then, let f denote the restriction of f to Q . Then, by construction, f is an injective mapping from Q to Q, thus it has an extension g ∈ T (A) by Lemma 5. Thus, for the mapping h = g • g we have q

• h = q • g • g = q • g • f = q • g • f = q • f for each state q ∈ Q, proving the theorem.

Conclusion

We showed that the syntactic complexity of semi-flower languages is exactly n n -n! + n and that in order to reach this complexity, an alphabet of linear size suffices. We left open the question whether n letters are needed to achieve this or maybe an even smaller alphabet suffices.

The authors wish to thank the reviewers for their careful work which improved the presentation of the paper. Reviewer 3 even sketched a proof showing that the minimal number of letters to achieve maximal syntactic complexity is n+1 2

, which we include here, slightly reformatted.

Theorem 2 (Reviewer 3). The maximal syntactic complexity n n -n! + n of an n-state semi-flower automaton can be reached by an alphabet of size n+1 2 and this bound is sharp.

Proof. One can observe that in A = ([n], Σ, •) studied in the previous section still contains redundant letters.

If 1 < k < n, then (n + 2 -k) • a k-2 • b k = k while i • a k-2 • b k = i + k -1 for each i = n + 2 -k.
In particular, the image of i = 1 is also k, so a k-2 b k merges 1 and n + 2 -k into k and permutes the (n -1)-element set {2, . . . , n} (as 1 does not belong to its image). Hence (a k-2 b k ) (n-1)! acts as the identity on {2, . . . , n} and maps 1 to n + 2 -k. Thus, a(a k-2 b k ) (n-1)! maps n to n + 2 -k and acts as i → i + 1 on the other states, so it induces the the same transformation as b n+2-k . Thus, with an appropriate composition of b 1 and b 2 one can induce the same transformation as b n+2-2 = b n , from b 1 and b 3 we get b n-1 and so on, thus the subset {b i : 1 ≤ i ≤ n+1 2 } of Σ generates the same transition monoid T (A), and so n+1 2 letters suffice. On the other hand, assume A = ([n], ∆, •) is a semi-flower automaton in normal form. Let us define the distance of two states p ≤ q ∈ [n] as d(p, q) = min{q -p, n + p -q}, that is, their "circular" distance and if p > q, then let d(p, q) = d(q, p). Clearly, d(p, q) = d(pa, qa) whenever a has rank n. Assume w = a 1 . . . a k induces a transformation of rank n -1. Then there is a least index i ∈ [k] such that a i induces a transformation of rank n -1 and each a j , j < i induces the permutation → +1. Let p = q be the states merged by a i and p , q be the states with p a 1 . . . a i-1 = p and q a 1 . . . a i-1 = q. Then, w merges the states p and q whose distance is d(p , q ) = d(p, q) depending only on a i . Hence, if T (A) contains all the transformations of rank n -1, then for each possible distance D > 0, the alphabet ∆ has to contain at least one letter of rank n -1 merging two states of distance D. Since there are n 2 possible distances on the cycle of length n, along with the letter inducing the circular permutation an alphabet of size at least n 2 + 1 = n+1 2 is needed in a circular semi-flower automaton to generate all the transformations of rank (n -1).

Proposition 1 . 1 a1 → p 2 a2→

 112 An automaton A over some alphabet Σ is a semi-flower automaton if and only if it is isomorphic to some automaton of the form ([n], Σ, •) such that each letter induces a semi-flower transition over [n]. This latter form is called a normal form of semi-flower automata. Proof. If each letter induces a semi-flower transition over [n] in A = ([n], Σ, •) then we claim that each cycle contains the state n. Indeed, let p . . . a k

Fig. 3 :Theorem 1 .

 31 Fig. 3: Example of the decomposition f = π •f . The marked states are belonging to Q .

Ministry of Human Capacities, Hungary grant 20391-3/2018/FEKUSTRAT is acknowledged. Szabolcs Iván was supported by the János Bolyai Scholarship of the Hungarian Academy of Sciences.

for each p ∈ Q, pgf = pf .

In other words, g associates to each state q ∈ Q a representative state of the class of q in the kernel of f . Proof. Lemma 1 states f p,q is a member of T (A) for each p, q ∈ Q.

Let C ⊆ Q be a nonempty set of states. We claim that there exists some function g C ∈ T (A) and a state p ∈ C such that C • g C = {p} and r • g C = r for each r / ∈ C. Indeed, let C = {q 1 , . . . , q k }. If C is a singleton, then the identity function trivially satisfies the conditions, so assume |C| > 1.

Then the function f q1,q k • f q2,q k • . . . • f q k-1 ,q k satisfies the claim with p = q k . Hence, for any transformation f :

if and only if p and q belong to the same C i ), then the function g = g C1 • . . . • g C k satisfies the conditions of the corollary.

The next lemma states that if we have some proper subset Q of the states, then we can swap two of these states and retain the other members of Q in their original place with some function from T (A):

Proof. If p = q, then the claim holds trivially as the identity belongs to T (A) so we can assume p = q.

By |Q | < n, there exists some state / ∈ Q . We claim that the function f = f p, • f q,p • f ,q satisfies the conditions of the Lemma. Indeed, if r / ∈ {p, q, }, then none of the functions involved moves r, so that r • f = r for each r ∈ Q -{p, q}; and clearly, p • f p, = , • f q,p = and • f ,q = q shows p • f = q and similarly q • f p, = q, q • f q,p = p and p • f ,q = p shows q • f = p.

So this f ∈ T (A) satisfies the conditions of the lemma.

For an example, see Figure 2. Now in order to show an arbitrary function f : Q → Q with rank less than n, we dissect f as f = f 1 • π • g where f 1 collapses the kernel classes of f into their representative elements (we can do that according to Corollary 1), π is an appropriate permutation on these representatives (Lemma 3 ensures the existence of such a suitable permutation in T (A)), and g is a "monotone" mapping (Lemma 4 will ensure that g ∈ T (A)).

Proof. By Lemma 2 we get that for any transposition t swapping two states of Q there exists some member belonging to T (A) which extends t. Since every permutation π can be written as a composition of transpositions, and T (A) is closed under composition, we get that each permutation of Q Q can be extended to some member of T (A).


Simon Beier

Markus Holzer

Nondeterministic Right One-Way Jumping Finite Automata (Extended

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Right one-way jumping finite automata (ROWJFAs) were introduced in [START_REF] Chigahara | One-way jumping finite automata. Internat[END_REF] as a deterministic variant of jumping finite automata [START_REF] Meduna | Jumping finite automata[END_REF], a machine model for discontinuous information processing, that is allowed to read letters from anywhere in the input string, not necessarily only from left of the remaining input. In a right one-way jumping finite automaton the device moves the input head deterministically from left-to-right starting from the leftmost letter in the input and when it reaches the end of the input word, it returns to the beginning and continues the computation. The language families induced by these two automata models are quite interesting since they have relations to semi-linear sets, see, e.g., [1-3, 5, 6, 11]. While languages that are accepted by jumping finite automata are permutation closed and semi-linear [START_REF] Meduna | Jumping finite automata[END_REF], the permutation closed languages that are accepted by ROWJFAs are exactly those languages with a finite number of positive Myhill-Nerode equivalence classes [START_REF] Beier | Properties of right one-way jumping finite automata[END_REF], that is, the permutation closed language under consideration can be written as the finite union of Myhill-Nerode classes. This is a nice transfer of a classical result on finite automata that states that a language is regular or accepted by a deterministic finite automaton if and only if the number of Myhill-Nerode equivalence classes is finite, to the case where the index (number of equivalence classes) of the Myhill-Nerode relation is not finite any more. Since many generalizations of finite automata such as, e.g., nondeterminism, multiple initial states, etc. do note change their accepting power, the question arises whether a similar result is valid for ROWJFAs, too? We answer this question for two types of generalizations, namely nondeterministic transitions and/or multiple initial states, for jumping finite automata and ROWJFAs.

For jumping finite automata the generalizations to nondeterministic transitions functions and/or multiple initial states do not change the computational power of these devices and leads to the language family JFA. This is in sharp contrast to ROWJFAs, where these generalizations increase the computational power of these devices and thus induce a mesh of language families and their permutation closed variants that are strictly included within each other (due to the trivial inclusion relations), subject to one exception. For the case of nondeterministic ROWJFAs and nondeterministic ROWJFAs with multiple initial states, we find that the induced languages families NROWJ and MNROWJ coincide in case we consider permutation closed languages. Then this language family is nothing other than JFA, the family of all languages accepted by jumping finite automata. The corresponding deterministic language families ROWJ and MROWJ of all languages accepted by ROWJFAs and those with multiple initial states satisfy ROWJ ⊂ MROWJ and pROWJ ⊂ pMROWJ, resp., where the prefix p refers to the permutation closed language family in question. By results in [START_REF] Beier | Semi-linear lattices and right one-way jumping finite automata (extended abstract)[END_REF], it was shown that the permutation closed languages over binary alphabets accepted by ROWJFAs with multiple initial states are those languages that are a finite union of permutation closed languages, where each language has a finite number of positive Myhill-Nerode equivalence classes. For arbitrary alphabets we have a characterization which is a bit more sophisticated and uses the quotient of a language by a word. Although the generalization of ROWJFAs to nondeterministic ROWJFAs with and without multiple initial states is straightforward, it is not clear how to describe the semantics of these machines in case of spontaneous or λ-transitions. This issue is discussed in detail and we give three different semantics, where it turns out that two of them are equivalent. The introduced generalizations nicely fit into the known landscape of the language families that were considered earlier. We further prove inclusion and incomparability results to classical language families such as the deterministic context-free languages, context-free languages, and context-sensitive languages. In some of our proofs a nice and tight relation between languages accepted by ROWJFAs and variants thereof to semi-linear sets and languages with finite positive Myhill-Nerode equivalence classes [START_REF] Beier | Properties of right one-way jumping finite automata[END_REF][START_REF] Beier | Semi-linear lattices and right one-way jumping finite automata (extended abstract)[END_REF] is exploited.

Because ROWJFAs share some features of finite automata with translucent letters [START_REF] Nagy | Finite-state acceptors with translucent letters[END_REF] since their input letter reading mechanism looks similar, it is natural to consider the relation of the language families given by these automata to ROWJFAs and generalizations thereof. In passing we solve an open problem on deterministic finite automata with translucent letters stated in [START_REF] Nagy | Finite-state acceptors with translucent letters[END_REF]. Due to space constraints all proofs are omitted and will be given in a journal version of this paper.

Preliminaries

We assume the reader to be familiar with the basics in automata and formal language theory as contained, for example, in [START_REF] Harrison | Introduction to Formal Language Theory[END_REF]. Let N = {0, 1, 2, . . .} be the set of non-negative integers. We use ⊆ for inclusion and ⊂ for proper inclusion of sets. We denote the powerset of a set S by 2 S . For a binary relation ∼ let ∼ + and ∼ * denote the transitive closure of ∼ and the transitive-reflexive closure of ∼, respectively. In the standard manner, ∼ is extended to ∼ n , where n ≥ 0. Let Σ be an alphabet. Then Σ * is the set of all words over Σ, including the empty word λ. For a language L ⊆ Σ * define the set perm(L) = ∪ w∈L perm(w), where perm(w

) = { v ∈ Σ * | v is a permutation of w }. A language L is called permutation closed if L = perm(L).
⊆ a * 1 a * 2 • • • a * k . For a vector c ∈ N k and a finite set P ⊂ N k let L(c, P ) denote the sub- set L(c, P ) = { c + xi∈P λ i • x i | λ i ∈ N } of N k .
Sets of the form L(c, P ), for a c ∈ N k and a finite P ⊂ N k , are called linear subsets of N k . A subset of N k is said to be semi-linear if it is a finite union of linear subsets. Moreover, a language L ⊆ Σ * is called semi-linear if its Parikh-image ψ(L) is semi-linear.

For an alphabet Σ and a language L ⊆ Σ * , let ∼ L be the Myhill-Nerode equivalence relation on Σ * . So, for v, w ∈ Σ * , we have v ∼ L w if and only if, for all u ∈ Σ * , the equivalence vu ∈ L ⇔ wu ∈ L holds. For w ∈ Σ * , we call the equivalence class [w] ∼ L positive if and only if w ∈ L.

We define a nondeterministic finite automaton with multiple start states and spontaneous or λ-transitions, a λ-MNFA for short, as a tuple A = (Q, Σ, R, S, F ), where Q is the finite set of states, Σ is the finite input alphabet, R is a function from Q × (Σ ∪ {λ}) to 2 Q , S ⊆ Q is the set of start states, and F ⊆ Q is the set of final states. The elements of R are referred to as rules of A and we simply write pa → q ∈ R instead of q ∈ R(p, a), for p, q ∈ Q and a ∈ Σ ∪ {λ}.

A configuration of A is a string in QΣ * . The automaton A makes a transition from configuration paw to configuration qw if pa → q ∈ R, where p, q ∈ Q, a ∈ Σ ∪ {λ}, and w ∈ Σ * . We denote this by paw A qw or just paw qw if it is clear which automaton we are referring to. The language accepted by A is

L(A) = { w ∈ Σ * | ∃s ∈ S, f ∈ F : sw * f } .
We say that A accepts w ∈ Σ * if w ∈ L(A) and that A rejects w otherwise.

The automaton A is called a nondeterministic finite automaton with multiple start states, an MNFA, if R(p, λ) = ∅ for all p ∈ Q. We call A a nondeterministic finite automaton with λ-transitions, a λ-NFA, if |S| = 1. If A is an MNFA and a λ-NFA, we say that A is a nondeterministic finite automaton, an NFA. The automaton A is said to be a deterministic finite automaton with multiple start states, an MDFA, if A is an MNFA and |R(p, a)| ≤ 1 for all p ∈ Q and a ∈ Σ. Finally, we call A a deterministic finite automaton, a DFA, if it is an MDFA and an NFA. It is well known that for all the aforementioned types of automata are computational equivalent and the family of languages accepted by any of these devices is referred to as the family of regular languages REG. Observe that these automata read the input in a symbol by symbol manner from left to right.

Besides the family of regular languages REG, we also use the following language families: let DCF, CF, and CS be the families of deterministic contextfree, context-free, and context-sensitive languages. Moreover, we are interested in families of permutation closed languages. These language families are referred to by a prefix p. For instance, pREG denotes the language family of all permutation closed regular languages.

Variants of Nondeterministic Jumping Finite Automata

We start our investigation with the generalization of jumping automata to variants of jumping automata with multiple initial states. Originally, jumping finite automata were introduced in [START_REF] Meduna | Jumping finite automata[END_REF] as deterministic or nondeterministic devices with a sole initial state. The idea behind a jumping finite automaton is that the device no longer reads the input from left to right, but is allowed to read letters from anywhere in the input string. For a λ-MNFA A = (Q, Σ, R, S, F ) this behaviour can be modelled by a binary relation, the jumping relation, which is symbolically denoted by A , over configurations from QΣ * and is defined as follows: consider an a ∈ Σ ∪ {λ}, words x, y ∈ Σ * , states p, q ∈ Q, and pa → q ∈ R. Then, we write pxay A qxy or just pxay qxy if it is clear which automaton we are referring to. The language accepted by A interpreted as a jumping finite automaton is

L J (A) = { w ∈ Σ * | ∃s ∈ S, f ∈ F : sw * f } .
We say that A interpreted as a jumping finite automaton accepts w ∈ Σ * if w ∈ L J (A), otherwise A interpreted as a jumping finite automaton rejects the word w.

Example 1. Let A be the DFAA = ({q 0 , q 1 , q 2 , q 3 }, {a, b}, R, q 0 , {q 3 }), where R consists of the rules q 0 b → q 1 , q 0 a → q 2 , q 2 b → q 3 , and q 3 a → q 2 . The automaton A is depicted in Figure 1. It holds

L(A) = (ab) + and L J (A) = perm (ab) + = w ∈ {a, b} + |w| a = |w| b .
Observe, that L J (A) is a permutation closed language that is non-regular but context-free.

It can easily be seen that L J (A) = perm(L(A)) holds in general. That is why, for X, Y ∈ {DFA, MDFA, NFA, MNFA, λ-NFA, λ-MNFA}, the family of languages accepted by automata of type X interpreted as jumping finite automata equals the family of languages accepted by automata of type Y interpreted as jumping finite automata. This language family is referred to as JFA. Clearly, we have JFA = pJFA and it obeys a nice characterization. Theorem 2. A language L is in JFA if and only if L is permutation closed and semi-linear.

q 0 q 1 q 2 q 3 b a b a
Moreover pCF ⊂ JFA ⊂ pCS and JFA strictly contains pROWJ; here ROWJ refers to the family of languages that are accepted by right one-way finite jumping automata, an automaton model introduced in the next subsection-in addition JFA is incomparable to the families REG, DCF, CF, ROWJ; for these results see, e.g., [START_REF] Beier | Properties of right one-way jumping finite automata[END_REF][START_REF] Chigahara | One-way jumping finite automata. Internat[END_REF][START_REF] Fernau | Jumping finite automata: Characterizations and complexity[END_REF][START_REF] Meduna | Jumping finite automata[END_REF].

Let us take a look at the descriptional complexity of these devices. It is obvious that the standard automata construction from the theory of finite state devices also applies to our setting whenever the underlying machine is interpreted as a jumping finite automaton. Hence, the conversion of a type X automaton, for X ∈ {MDFA, MNFA, λ-NFA, λ-MNFA}, to an equivalent NFA device (both machines interpreted as jumping automata) results in state complexity increase of at most one state, which is used to simulate the union of languages for automata of types from {MDFA, MNFA, λ-MNFA}. Removing spontaneous transitions does not increase the number of states at all. The remaining conversion from an NFA to a DFA is at most 2 n , where n is the number of states of the NFA, due to the powerset construction that can be successfully applied in our setting, too. Since the equivalence needs to be w.r.t. the Parikh image of the languages one can prove a better conversion bound. Namely, in [START_REF] Lavado | Operational state complexity under Parikh equivalence[END_REF] it was shown that for each NFA with n states a Parikh equivalent DFA with e O( √ n log n) states can be constructed and that this bound is asymptotically tight. Thus, in our setting this result reads as follows: Theorem 3. Let A be an n-state NFA. Then e O( √ n log n) states are sufficient and necessary in the worst for a DFA B to accept the language L J (A) if B is interpreted as a jumping finite automaton, that is, L J (B) = L J (A).

Right One-Way Jumping Finite Automata

We deal with a variant of jumping finite automata, namely so called right oneway jumping finite automata, which were introduced in [START_REF] Chigahara | One-way jumping finite automata. Internat[END_REF] in the deterministic case. We now generalize the definition of these devices to nondeterministic machines without λ-transitions. Their behaviour can be described as follows. The read head starts the computation at the leftmost symbol of the input and moves to the right. If R(p, a) = ∅ for the current state p and the next input symbol a, one of the possible transitions is executed, the symbol a is consumed, and the read head moves on to the next symbol. If, however, R(p, a) = ∅, the read head jumps over a, does not consume it, and moves on to the next symbol. When the head reaches the end of the input, it jumps back to the beginning and continues the computation, which goes on until no input symbol is left.

A formal definition is given in the following: let A = (Q, Σ, R, S, F ) be an MNFA. The right one-way jumping relation, symbolically denoted by A , over QΣ * is defined as follows. Let p, q ∈ Q, a ∈ Σ, w ∈ Σ * , and q ∈ R(p, a). Then, we have paw A qw. Now, let p ∈ Q, a ∈ Σ, and w ∈ Σ * with R(p, a) = ∅. In this case we get paw A pwa. We also write instead of A if it is clear which automaton we are referring to. The language accepted by A interpreted as a right one-way jumping finite automaton is

L R (A) = { w ∈ Σ * | ∃s ∈ S, f ∈ F : sw * f } .
In order to keep the presentation simple, we speak of a ROWJFA, MROWJFA, NROWJFA, and MNROWJFA, respectively, if we interpret a DFA, MDFA, NFA, and a MNFA as a right one-way device, respectively. The corresponding language families are referred to as ROWJ, MROWJ, NROWJ, and MNROWJ, resp. Clearly, for unary alphabets all these families correspond with REG.

Example 4. We continue our previous example. To show how ROWJFAs work, we give an example computation of A, interpreted as an ROWJFA, on the input word aabbba: q 0 aabbba q 2 abbba 2 q 3 bbaa 3 q 2 abb 2 q 3 ba 2 q 2 b q 3 That shows aabbba ∈ L R (A). Analogously, one can see that every word that contains the same number of a's and b's and that begins with an a is in L R (A). On the other hand, no other word can be accepted by A, interpreted as an ROWJFA. So, we get L R (A) = { w ∈ a{a, b} * | |w| a = |w| b }. Notice that this language is non-regular and not closed under permutation. Now the question arises how the right one-way jumping relation can be generalized to work on automata with λ-transitions? Sometimes we call these transitions also spontaneous transitions. To cope with spontaneous transitions we have three different interpretation possibilities for the right one-way jumping relation-as above we speak of λ-NROWJFAs (λ-MNROWJFAs, respectively), if λ-NFAs (λ-MNFAs, respectively) are interpreted as right one-way jumping devices:

Type 1. The first type of right one-way jumping finite automata is only allowed to jump over an input symbol, if A cannot perform a λ-transition in the current state. So, the right one-way jumping relation of type 1, symbolically denoted by A,1 , over QΣ * is defined as follows. Let p, q ∈ Q, a ∈ Σ ∪ {λ}, w ∈ Σ * , and q ∈ R(p, a). Then, we have paw A,1 qw. Now, let p ∈ Q, a ∈ Σ, and w ∈ Σ * with R(p, a) = ∅ = R(p, λ). In this case it holds paw A,1 pwa. Type 2. If the second type of right one-way jumping finite automata has no transition for the current state and the next input symbol, but can perform a λ-transition in the current state, the automaton is allowed to choose if it performs a jump or if it uses a λ-transition. However, if the automaton decides to jump, it has to jump over all the following input symbols that cannot be read in the current state and must read the next input symbol that can be read in the current state. Not until now, the automaton is allowed to perform a λ-transition again. So, we set

Σ R,p = { a ∈ Σ | R(p, a) = ∅ }
for p ∈ Q. Therefore the right one-way jumping relation of type 2, symbolically denoted by A,2 , over QΣ * is defined as follows. For p, q ∈ Q, w ∈ Σ * , and q ∈ R(p, λ) it holds pw A,2 qw. Now, let p, q ∈ Q, a ∈ Σ, v ∈ (Σ \ Σ R,p ) * , and w ∈ Σ * with q ∈ R(p, a). Then, we get pvaw A,2 qwv. Type 3. If the third type of right one-way jumping finite automata has no transition for the current state and the next input symbol, but can perform a λ-transition in the current state, the automaton is allowed to choose if it jumps over the next input symbol or if it uses a λ-transition. Thus, the right one-way jumping relation of type 3, symbolically denoted by A,3 , over QΣ * is defined as follows. Let p, q ∈ Q, a ∈ Σ ∪ {λ}, w ∈ Σ * , and q ∈ R(p, a).

In this case we have paw A,3 qw. For p ∈ Q, a ∈ Σ, and w ∈ Σ * with R(p, a) = ∅ it holds paw A,3 pwa.

Let i ∈ {1, 2, 3}. We also write i instead of A,i if it is clear which automaton we are referring to. The language accepted by A interpreted as a right one-way jumping finite automaton of type i is defined to be

L Ri (A) = { w ∈ Σ * | ∃s ∈ S, f ∈ F : sw * i f } .
This give rise to the language families λ i NROWJ (λ i MNROWJ, respectively) of all languages accepted by λ-NROWJFAs (λ-MNROWJFAs, respectively) of type i, for 1 ≤ i ≤ 3. Again, all these families correspond with REG for unary alphabets.

Example 5. Let A = ({q 0 , q 1 , . . . , q 5 }, {a, b, c}, R, {q 0 }, {q 5 }) be the λ-NROWJFA with R = {q 0 λ → q 1 , q 0 a → q 4 , q 1 a → q 2 , q 1 b → q 2 , q 1 c → q 3 , q 3 a → q 4 , q 4 b → q 5 , q 5 a → q 4 }.

The automaton A is depicted in Figure 2.

It is easy to see that that L(A) = {λ, c}(ab) + . Let L refer to the language { w ∈ {a, b} + | |w| a = |w| b }. For the three interpretations on how to cope with spontaneous transitions we get the following languages-let letter x ∈ {a, b}, words u, v ∈ {b, c} * , and w ∈ {a, b, c} * : -In type 1 we have the computations q 0 aw 1 q 4 w, q 0 xw 2 1 q 2 w, and q 0 cvaw 2 1 q 3 vaw |v|+1 1 q 4 wv. This implies

q 0 q 1 q 2 q 3 q 4 q 5 λ a
L R1 (A) = { w ∈ a{a, b} * | |w| a = |w| b } ∪ cL.
-For type 2 we get the behaviour q 0 vaw 2 q 4 wv, q 0 xw 2 2 q 2 w, and finally q 0 cvaw 2 2 q 3 vaw 2 q 4 wv. That gives us

L R2 (A) = {λ, c}L.
-In type 3 it holds q 0 vaw |v|+1 3 q 4 wv, q 0 vxw |v|+2 3 q 2 wv, and moreover q 0 vcuaw |v|+2 3 q 3 uawv |u|+1 3 q 4 wvu. Hence, we have

L R3 (A) = L ∪ b n cw n ≥ 0, w ∈ {a, b} + , |b n cw| a = |b n cw| b .
Furthermore, we get

L J (A) = perm(L(A)) = { w ∈ {a, b, c} * | |w| a = |w| b > 0, |w| c ∈ {0, 1} } . It follows L(A) ⊆ L R1 (A) ⊆ L R2 (A) ⊆ L R3 (A) ⊆ L J (A)
where the inclusions are strict. This inclusion chain is not a coincidence, as we will see next.

From our definitions, we can deduce: Lemma 6. Let A = (Q, Σ, R, S, F ) be a λ-MNROWJFA. Then, the following holds:

1. We have

L(A) ⊆ L R1 (A) ⊆ L R2 (A) ⊆ L R3 (A) ⊆ L J (A) and these languages are semi-linear. 2. If A is an MNROWJFA, then L R (A) = L Ri (A), for 1 ≤ i ≤ 3. Hence the inclusion chain L(A) ⊆ L R (A) ⊆ L J (A) applies. 3. If R(p, a) = ∅, for every state p ∈ Q and letter a ∈ Σ, then L(A) = L Ri (A), for 1 ≤ i ≤ 3.
Lemma 6 implies that every regular language is accepted by a ROWJFA, because every regular language is accepted by a DFA with total transition function. On the other hand, we have seen in our example that ROWJFAs can accept non-regular languages. Indeed, it was already shown in [START_REF] Chigahara | One-way jumping finite automata. Internat[END_REF] that REG ⊂ ROWJ.

Variants of Right One-Way Jumping Finite Automata Without Spontaneous Transitions

From the language families ROWJ, MROWJ, NROWJ, and MNROWJ and their permutation closed variants the former two were already investigated in the literature. For inclusion relations and incomparability results see, e.g., [START_REF] Beier | Properties of right one-way jumping finite automata[END_REF][START_REF] Beier | Semi-linear lattices and right one-way jumping finite automata (extended abstract)[END_REF]. Clearly, MROWJ consists exactly of the finite unions of languages from ROWJ. However, it is not clear that every language from pMROWJ is a finite union of languages from pROWJ. Nice characterizations for both language families were obtained. More precisely, a permutation closed language L is in ROWJ if and only if the Myhill-Nerode relation ∼ L has only a finite number of positive equivalence classes [START_REF] Beier | Properties of right one-way jumping finite automata[END_REF]. In [START_REF] Beier | Semi-linear lattices and right one-way jumping finite automata (extended abstract)[END_REF], concerning the language family MROWJ it was shown that for a permutation closed language L the following statements are equivalent: (1) For all w ∈ Σ * , the language L/ d w is in pMROWJ, where Before we investigate the hierarchy of permutation closed language families we first state a result that shows that whenever the underlying device is nondeterministic and accepts a permutation closed language it does not matter whether the automaton has multiple initial states or not. Moreover, we show that the induced language family coincides with JFA, the family of languages accepted by jumping finite automata.

L/ d w = { v ∈ Σ * | vw ∈ L
Theorem 9. We have pNROWJ = pMNROWJ = JFA.

From [START_REF] Beier | Semi-linear lattices and right one-way jumping finite automata (extended abstract)[END_REF], we know pROWJ ⊂ pMROWJ. Furthermore, the permutation closed language { w ∈ {a, b} * | |w| a = |w| b } is clearly in JFA, but was shown to be not in pMROWJ in [START_REF] Beier | Semi-linear lattices and right one-way jumping finite automata (extended abstract)[END_REF]. Hence, together with the previous theorem we get: Theorem 10. It holds pROWJ ⊂ pMROWJ ⊂ pNROWJ = pMNROWJ.

Variants of Right One-Way Jumping Finite Automata With Spontaneous Transitions

In this subsection we study λ-NROWJFAs and λ-MNROWJFAs under the three semantics introduced earlier. Observe that by definition we have the inclusions MNROWJ ⊆ λ i MNROWJ and NROWJ ⊆ λ i NROWJ ⊆ λ i MNROWJ, for every i ∈ {1, 2, 3}. First we show that λ-NROWJFAs and λ-MNROWJFAs have the same computational power, if we fix the semantics.

Lemma 11. For i ∈ {1, 2, 3}, we have λ i NROWJ = λ i MNROWJ.

Next we consider the case when the semantics on λ-MNROWJFAs varies. We show that λ-MNROWJFAs of type 1 are at most as powerful as those of type 2 and those of type 3: Lemma 12. We have λ 1 MNROWJ ⊆ λ 2 MNROWJ and λ 1 MNROWJ ⊆ λ 3 MNROWJ.

Our next result shows that MNROWJFAs have indeed the same power as λ-MNROWJFAs of type 2.

Lemma 13. We have MNROWJ = λ 2 MNROWJ.

By definition, it holds MNROWJ ⊆ λ 1 MNROWJ. Thus, the previous three Lemmas 11, 12, and 13 give us the following equalities of language families. Corollary 14. We have MNROWJ = λ i NROWJ = λ i MNROWJ, for i with i ∈ {1, 2}.

In contrast to the last result, λ-NROWJFAs of type 3 are more powerful than MNROWJFAs.

Theorem 15. It holds MNROWJ ⊂ λ 3 NROWJ.

Our language families are all included in the complexity classes NTIME(n 2 ) and in NSPACE(n): Theorem 16. For i ∈ {1, 2, 3}, the family λ i MNROWJ is properly included in NTIME(n 2 ) and in NSPACE(n).

For a λ-MNROWJFA A and i ∈ {1, 2, 3} the language L Ri (A) contains a Parikh-equivalent regular sublanguage, because of Lemma 6. The only Parikhequivalent sublanguage of a letter-bounded language is the language itself, so we get the following.

Corollary 17. The letter-bounded languages contained in λ 3 MNROWJ are exactly the regular letter-bounded languages.

As a consequence, the language { a n b n | n ≥ 0 } is not in λ 3 MNROWJ. On the other hand, it was shown in [START_REF] Chigahara | One-way jumping finite automata. Internat[END_REF] that ROWJ contains non-context-free languages. It follows:

Corollary 18. Let F ∈ {ROWJ, λ 3 MNROWJ} and G ∈ {DCF, CF}. Then, the language families F and G are incomparable.

Relations to Finite-State Acceptors With Translucent Letters

Finite-state acceptors with translucent letters were defined in [START_REF] Nagy | Finite-state acceptors with translucent letters[END_REF]. For these devices, depending on the current internal state, some letters of the input alphabet are translucent, which means that the automaton does not see them and reads the first letter which is not translucent. So, their behaviour is similar to ROWJFAs, which jump over some letters of the input alphabet, also depending on the current state of the automaton. We will investigate the inclusion relations between the language families induced by finite-state acceptors with translucent letters and those families which come from ROWJFAs and their nondeterministic variants.

A finite-state acceptor with translucent letters, a NFAwtl for short, is a tuple A = (Q, Σ, τ, S, F, δ), where Q is the finite set of states, Σ is the finite input alphabet, τ : Q → 2 Σ is the translucency mapping, S ⊆ Q is the set of start states, F ⊆ Q is the set of final states, and δ : Q × Σ → 2 Q is the transition function. For each state q ∈ Q the letters from τ (q) are translucent in state q. The automaton A is called deterministic, a DFAwtl for short, if |S| = 1 and |δ(q, a)| ≤ 1, for all (q, a) ∈ Q × Σ.

A configuration of A is a string in QΣ * . The automaton A makes a transition from configuration pvaw to configuration qvw if q ∈ δ(p, a), where p, q ∈ Q, v ∈ (τ (p)) * , a ∈ Σ \ τ (p), and w ∈ Σ * . We denote this by pvaw A qvw or just pvaw qvw if it is clear which automaton we are referring to. Then, the language accepted by A is L(A) = { w ∈ Σ * | ∃s ∈ S, f ∈ F, v ∈ (τ (f )) * : sw * f v } .

We say that A accepts w ∈ Σ * if w ∈ L(A) and that A rejects w otherwise. The family of all languages accepted by a NFAwtl (DFAwtl, respectively) will be denoted by NTRANS (DTRANS, respectively). These families are incomparable to the language families induced by ROWJFAs and their nondeterministic variants:

Theorem 19. Consider language families F ∈ {DTRANS, NTRANS} and G ∈ {ROWJ, λ 3 NROWJ}. Then, the families F and G are incomparable.

From [START_REF] Nagy | Finite-state acceptors with translucent letters[END_REF] it is known that pNTRANS = JFA. The family pDTRANS has the following inclusion relations to pROWJ and pMROWJ.

Theorem 20. We have pROWJ ⊂ pDTRANS. The families pDTRANS and pMROWJ are incomparable.

In [START_REF] Nagy | Finite-state acceptors with translucent letters[END_REF]

Conclusions

We have investigated nondeterministic variants of ROWJFAs and showed inclusion and incomparability results of the induced language families. In order to complete the picture of these new language families, it remains to study closure properties and decision problems for these devices. Since languages accepted by variants of jumping automata are all semi-linear, it is worth to consider their relation to Petri Nets, since a wide variety of them enjoy semi-linear reachability sets-see, e.g., [START_REF] Yen | Petri nets and semilinear sets (extended abstract)[END_REF].

Fig. 1 .

 1 Fig. 1. The DFA A with L(A) = (ab) + interpreted as a jumping finite automaton accepts the language LJ (A) = { w ∈ {a, b} + | |w|a = |w| b }.

Fig. 2 .

 2 Fig. 2. The λ-NROWJFA A with L(A) ⊂ LR1(A) ⊂ LR2(A) ⊂ LR3(A) ⊂ LJ (A).

Theorem 7 .

 7 and (|v| a = 0 ∨ |w| a = 0), for every a ∈ Σ } is the disjoint quotient of a language L ⊆ Σ * by a word w ∈ Σ * , and (2) there is an n ≥ 0 and permutation closed languages L 1 , L 2 , . . . , L n ⊆ Σ * such that L = n i=1 L i and for all i ∈ {1, 2, . . . , n} the language L i has only a finite number of positive Myhill-Nerode equivalence classes. Both characterization results are based on a relation between languages accepted by ROWJFAs and MROWJFAs and semi-linear sets. For our language families we find the following situation. The following strict inclusions of language families hold:1. ROWJ ⊂ MROWJ and ROWJ ⊂ NROWJ.2. MROWJ ⊂ MNROWJ and NROWJ ⊂ MNROWJ.The languages used in the proof of the previous theorem show that the language families MROWJ and NROWJ are incomparable.Corollary 8. The language families MROWJ and NROWJ are incomparable.

  it was shown that for each NFAwtl A there is an NFAwtl B = (Q, Σ, τ, S, F, δ) with L(A) = L(B) and for all w ∈ Σ * , s ∈ S, f ∈ F , and v ∈ (τ (f )) * with sw * B f v it holds v = λ. It was stated as an open problem if this property also holds for DFAswtl. We can solve this open problem: Corollary 21. There is a DFAwtl A such that there does not exist a DFAwtl B = (Q, Σ, τ, {s}, F, δ) with L(A) = L(B) and for all w ∈ Σ * , f ∈ F , and v ∈ (τ (f )) * with sw * B f v it holds v = λ.

  The length of a word w ∈ Σ * is denoted by |w|. For the number of occurrences of a symbol a in w we use the notation |w| a . If Σ is the ordered alphabet Σ = {a 1 , a 2 , . . . , a k }, the function ψ : Σ * → N k with w → (|w| a1 , |w| a2 , . . . , |w| a k ) is called the Parikh-mapping. The set ψ(L) is called the Parikh-image of L. Two languages over the same ordered alphabet are said to be Parikh-equivalent if and only if they have the same Parikh-image. The language L is called letter-bounded if and only if L