Galina Jirásková
email: jiraskov@saske.sk

Self-Verifying Finite Automata and Descriptional Complexity ⋆

We survey recent results on the descriptional complexity of self-verifying finite automata. In particular, we discuss the cost of simulation of self-verifying finite automata by deterministic finite automata, and the complexity of basic regular operations on languages represented by self-verifying finite automata.

Introduction

A self-verifying finite automaton is a nondeterministic automaton whose state set consists of three disjoint groups of states: accepting states, rejecting states, and neutral states. On every input string, at least one computation must end in either an accepting or in a rejecting state. Moreover, there is no input string with both accepting and rejecting computations.

The existence of an accepting computation on an input string proves the membership of the string to the language. This is the same as in a nondeterministic finite automaton (NFA). However, in a self-verifying finite automaton (SVFA), the existence of a rejecting computation definitely proves that the input is not in the language. This is in contrast with NFAs, where the existence of a non-final computation leaves open the possibility that the input may be accepted by a different computation. Thus, even if the transitions are nondeterministic, when a computation of an SVFA ends in an accepting or in a rejecting state, the automaton "can trust" the outcome of that computation, and accept or reject the input. The name "self-verifying" comes from this property. SVFAs were introduced in [START_REF] Ďuriš | Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations[END_REF], and were considered mainly in connection with probabilistic Las Vegas computations. However, as pointed in [START_REF] Hromkovič | On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata[END_REF], they are also interesting per se.

Every SVFA can be converted to an equivalent deterministic finite automaton (DFA) by the standard subset construction [START_REF] Rabin | Finite automata and their decision problems[END_REF]. On the other hand, every complete DFA may be viewed as a self-verifying finite automaton with all the final states being accepting, and all the non-final states being rejecting. Hence SVFAs recognize exactly the class of regular languages.

From the descriptional point of view, every n-state NFA can be simulated by a DFA of at most 2 n states [START_REF] Rabin | Finite automata and their decision problems[END_REF]. This bound is known to be tight in the binary case [START_REF] Ershov | On a conjecture of W.U. Uspenskii[END_REF][START_REF] Lupanov | A comparison of two types of finite automata[END_REF][START_REF] Moore | On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata[END_REF]. However, Assent and Seibert [START_REF] Assent | An upper bound for transforming self-verifying automata into deterministic ones[END_REF] proved that in the DFA obtained by applying the subset construction to an SVFA some states must be equivalent. As a consequence, they obtained an upper bound for the conversion of self-verifying automata to deterministic automata in O(2 n / √ n). Later this result was strengthened in [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF], where the tight bound for such a conversion was given by a function g(n) which grows like 3 n/3 . The witness languages meeting the bound g(n) were defined over a binary alphabet.

The investigation of self-verifying automata was further deepened by Jirásek et al. [START_REF] Jirásek | Operations on self-verifying finite automata[END_REF]. Using the tight bound g(n) from [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF], it was shown that a minimal SVFA for a regular language may not be unique. Then the authors introduced an sv-fooling set lower bound technique for the number of states in SVFAs. Using this technique, they obtained tight upper bounds on the complexity of reversal, boolean operations, star, left and right quotients, and asymptotically tight upper bound for concatenation of languages represented by SVFAs.

Here we survey these results. We deal with SVFA-to-DFA conversion in Section 2, and discuss the complexity of basic regular operations on SVFAs in Section 3. To conclude this introduction, let us recall some basic notions and preliminary results. For further details, the reader may refer to [START_REF] Sipser | Introduction to the theory of computation[END_REF].

All DFAs in this paper are assumed to be complete, and NFAs have a unique initial state. Sometimes we also consider NNFAs -nondeterministic finite automata with a nondeterministic choice of the initial state [START_REF] Yu | Chapter 2: Regular languages[END_REF] -where we admit multiple initial states.

A self-verifying finite automaton (SVFA) is a tuple A = (Q, Σ, δ, s, F a , F r ), where Q, Σ, δ, and s are the same as in an NFA, F a is the set of accepting states, F r is the set of rejecting states, and F a ∩ F r = ∅; the remaining states in Q are called neutral. It is required that for each input string w in Σ * , there exists at least one computation ending in an accepting or in a rejecting state, and there are no strings w such that both δ(s, w) ∩ F a and δ(s, w) ∩ F r are nonempty.

The language accepted by the SVFA A, denoted as L a (A), is the set of all input strings having a computation ending in an accepting state, while the language rejected by A, denoted as L r (A), is the set of all input strings having a computation ending in a rejecting state. It follows directly from the definition that L a (A) = (L r (A)) c for each SVFA A. Hence, when we say that an SVFA A accepts a language L, we mean that L = L a (A) and L c = L r (A).

The state complexity of a regular language L, sc(L), is defined as the smallest number of states in any DFA for L. The state complexity of a regular operation is the maximal state complexity of languages resulting from the operation, considered as a function of the state complexities of the operands. Similarly, the nondeterministic state complexity and self-verifying state complexity of a regular language L, denoted by nsc(L) and svsc(L), is defined as the smallest number of states in any NFA (with a unique initial state) and SVFA, respectively, for L.

Every NNFA A = (Q, Σ, δ, I, F ) can be converted to an equivalent DFA [START_REF] Rabin | Finite automata and their decision problems[END_REF]. The DFA A ′ is called the subset automaton of the NFA A. Let us recall two observations from [START_REF] Hromkovič | On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata[END_REF][START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF].

A ′ = (2 Q , Σ, •, I, F ′ ), where R • a = δ(R, a) for each R in 2 Q and each a in Σ, and F ′ = {R ∈ 2 Q | R ∩ F ̸ = ∅}

Proposition 1 ([8, 11]

). Let a language L be accepted by an n-state SVFA. Then the languages L and L c are accepted by n-state NFAs.

⊓ ⊔

Proof. Let L be accepted by an SVFA A = (Q, Σ, δ, s, F a , F r ). Then L is accepted by NFA (Q, Σ, δ, s, F a ), while L c is accepted by NFA (Q, Σ, δ, s, F r ). ⊓ ⊔ Proposition 2 ( [START_REF] Hromkovič | On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata[END_REF][START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF]). Let languages L and L c be accepted by an m-state and n-state NNFAs, respectively. Then svsc(L) ≤ m + n + 1.

⊓ ⊔

Proof. Let L be accepted by an m-state NNFA N = (Q, Σ, δ, I, F ) and L c be accepted by an n-state

NNFA N ′ = (Q ′ , Σ, δ ′ , I ′ , F ′ ).

SVFA-to-DFA Conversion and Minimal SVFAs

The SVFA-to-DFA conversion was first studied by Assent and Seibert [START_REF] Assent | An upper bound for transforming self-verifying automata into deterministic ones[END_REF]. Then Jirásková and Pighizzini [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF] obtained a tight upper bound for such a conversion.

g(n) =          1 + 3 (n-1)/3 , if n mod 3 = 1 and n 4, 1 + 4 • 3 (n-5)/3 , if n mod 3 = 2 and n 5, 1 + 2 • 3 (n-3)/3 , if n mod 3 = 0 and n 3, n, if n 2.
(1)

Moreover, the bound g(n) is tight, and can be met by a binary n-state SVFA.

Proof (Proof Idea). To an n-state SVFA A, we assign an undirected graph G(A) whose vertex set is Q, and which contains an edge {p, q} if and only if two computations starting from p and q cannot give contradictory answers on the same string. Then each reachable subset in the subset automaton of A is represented by a clique in G(A). Moreover, if S and T are two subsets such that S ∪ T is a clique in G(A), then S and T are equivalent [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF]Lemma 4]. Hence the number of states in the minimal DFA for L(A) is given by the number of maximal cliques in G(A). Next, in G(A) there is exactly one maximal clique containing the initial state of A. This results in at most 1 + f (n -1) states, where f (n) denotes the

(n) = 3 n/3 if n mod 3 = 0, f (n) = 4 • 3 ⌊n/3⌋-1 if n mod 3 = 1, and f (n) = 2 • 3 ⌊n/3⌋ if n mod 3 = 2.
This gives the upper bound. For tightness, let A = (Q, {a, b}, δ, q 0 , F a , F r ), where n = 1 + 3m and m 2, see Fig. 1 (left) for m = 13, be an automaton defined by

Q = {q 0 } ∪ {(i, j) | 0 i 2, 1 j m}, δ(q 0 , a) = δ(q 0 , b) = {(0, 1)
, (0, 2), . . . , (0, m)}, and for all i, j with 0 i 2 and 1 j m,

δ((i, j), a) = { {(i, j + 1)}, if j < m, {(0, 1)}, otherwise, δ((i, j), b) = {((i + 1) mod 3, j)}, F a = {q 0 , (0, m)}, and F r = {(1, m), (2, m)}.
It is shown in [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF]Lemma 8] that A is an SVFA whose minimal DFAs requires g(n) states. To get witnesses for n = 3k or n = 3k + 2, we modify the SVFA A as shown in Fig. 1 (middle and right).

⊓ ⊔

Thus if we know that the minimal DFA for a language L has more then g(n) states, then by Theorem 4, every SVFA for L must have at least n + 1 states. We use this result to show that a minimal SVFA may not be unique.

Example 5. Consider the two 7-state non-isomorphic SVFAs shown in Fig. 2. Apply the subset construction to both of them. In both cases, the subset automata restricted to the reachable states are the same. These subset automata, and therefore also the two SVFAs, accept the language (a + b) * a(a + b) 2 , the minimal DFA for which has 8 states. Since we have g(6) = 7, every SVFA for this language has at least 7 states. Hence both SVFAs in Fig. 2

Lower Bound Methods and Operations on SVFAs

To prove that a DFA is minimal, we only need to show that all its states are reachable from the initial state, and that no two distinct states are equivalent. To prove minimality of NFAs, a fooling set lower bound method may be used [START_REF] Birget | Partial orders on words, minimal elements of regular languages, and state complexity[END_REF][START_REF] Glaister | A lower bound technique for the size of nondeterministic finite automata[END_REF].

A fooling set for a language L is a set of pairs of strings

{(u 1 , v 1 ), . . . , (u n , v n )} satisfying two conditions: (i) for each i, u i v i ∈ L, and (ii) if i ̸ = j, then u i v j / ∈ L or u j v i / ∈ L.
In the case of SVFAs, we change the two conditions. The first condition can be removed since we have either an accepting or rejecting computation on every string. Before modifying the second condition, consider the following example. Example 6. Let L be accepted by the 3-state NFA shown in Fig. 3. Let A be an SVFA for L. Let us show that A has at least 6 states. Consider the following pairs of strings:

(u 1 , v 1 ) = (a 2 , a 2 ) Acc (u 4 , v 4 ) = (a 2 ba, a 2 ) Rej (u 2 , v 2 ) = (a 2 b, a) Acc (u 5 , v 5 ) = (a, a) Rej (u 3 , v 3 ) = (a 2 b 2 , ε) Acc (u 6 , v 6 ) = (ab, ε) Rej
The strings u 1 v 1 , u 2 v 2 , and u 3 v 3 are in L, while u 4 v 4 , u 5 v 5 , and u 6 v 6 are not in L, so we must have accepting and rejecting computations in A on these strings:

s u1 -→ p 1 v1 -→ f 1 ∈ F a , s u4 -→ p 4 v4 -→ f 4 ∈ F r , s u2 -→ p 2 v2 -→ f 2 ∈ F a , s u5 -→ p 5 v5 -→ f 5 ∈ F r , s u3 -→ p 3 v3 -→ f 3 ∈ F a , s u6 -→ p 6 v6 -→ f 6 ∈ F r . Since u 1 v 2 = a 3 , and a 3 is not in L, we must have p 1 ̸ = p 2 because otherwise s u1 -→ p 1 = p 2 v2
-→ f 2 would be an accepting computation on u 1 u 2 . Similarly, u 1 v 3 and u 2 v 3 are not in L, so p 1 , p 2 , and p 3 must be pairwise distinct. On the other hand, the strings u 4 v 5 , u 4 v 6 , and u 5 v 6 are in L, and therefore the states p 4 , p 5 , p 6 must be pairwise distinct. Next, let 1 ≤ i ≤ 3 and 1 ≤ j ≤ 3. If i ≤ j, then u j v i is not in L, and therefore p i ̸ = p j because otherwise s uj -→ p j = p i vi -→ f i would be an accepting computation on u j v i . Finally, if i > j, then u i v j is in L, and therefore p i ̸ = p j . Thus all the state p i are pairwise distinct, so the SVFA A has at least 6 states.

⊓ ⊔

Notice that in the previous example, we were able to interchange the right sides of two pairs (u i , v i ) and (u j , v j ) so that at least one of the resulting strings u i v j and u j v i had a "different finality" than the concatenations u j v j and u i v i , respectively. We formalize this in the following definition.

Definition 7. A set of pairs of strings

F = {(u 1 , v 1 ), (u 2 , v 2 ), . . . , (u n , v n )}
is called an sv-fooling set for a language L if for all i, j with i ̸ = j at least one of the following two conditions holds: (i) exactly one of the strings u i v j and u j v j is in L, or (ii) exactly one of the strings u j v i and u i v i is in L.

Lemma 8 (Lower Bound Method for SVFAs). Let F be an sv-fooling set for a language L. Then every SVFA for the language L has at least |F| states.

Proof. Let A be an SVFA for the language L with the initial state s. Then for each u i v i , there is an accepting or a rejecting computation of SVFA A on u i v i . Fix such a computation for each u i v i . Let p i be the state in this computation that is reached after reading u i , and let f i be the final state reached after reading v i .

Let us show that the states p 1 , p 2 , . . . , p n must be pairwise distinct. Assume for contradiction that there are i and j with i ̸ = j such that p i = p j . Then we have

s ui -→ p i = p j vj -→ f j and s uj -→ p j vj -→ f j ; and s uj -→ p j = p i vi -→ f i and s ui -→ p i vi -→ f i .
It follows that there are computations on u i v j and on u j v j that end in state f j . Thus either both this strings are in L, or both of them are in L c . Moreover, there are computations on u j v i and u i v i that end in state f i , so either both these strings are in L, or both of them are in L c . Hence neither (i) nor (ii) in the definition of an sv-fooling set holds, which is a contradiction.

⊓ ⊔

Notice that the lemma above may also be applied to a model of SVFAs with multiple initial states [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF]Section 5]. Hence if a language L is accepted by an n-state SVFA with multiple initial states, we cannot have an sv-fooling set of size more than n. In such a case, we can use the following observation to prove that an SVFA with a unique initial state needs one more state. Lemma 9. Let F = {(u 1 , v 1 ), (u 2 , v 2 ), . . . , (u n , v n )} be an sv-fooling set for L. For each i, let there exist a string w i such that {(u i , v i )} ∪ {(ε, w i )} is an svfooling set for L. Then every SVFA for L has at least |F| + 1 states.

Proof. For each pair in F, fix an accepting or a rejecting computation as in Lemma 8. Then the unique initial state, reached after reading ε, must be different from all the states reached after reading the left part of any pair in F. It follows that the SVFA has at least |F| + 1 pairwise distinct states.

⊓ ⊔ Example 10. Let us continue our previous example. Define w 1 = w 2 = w 3 = a 2 , w 4 = w 5 = ε, and w 6 = a. Notice that we have

u i • a 2 ∈ L and ε • a 2 / ∈ L for i = 1, 2, 3, u i • ε ∈ L and ε • ε / ∈ L for i = 4, 5, u 6 • a /
∈ L and ε • a ∈ L. By Lemma 9, every SVFA for L has at least 7 states.

⊓ ⊔

In what follows we use this simple methods to get tight upper bounds on the self-verifying complexity of reversal, boolean operations, star, and left and right quotients. In the case of concatenation, we get an asymptotically tight upper bound.

Reversal

If a language L is accepted by an n-state DFA A, then the language L R is accepted by an n-state NNFA A R obtained from A by swapping the role of the initial and final states of A, and by reversing all the transitions. By applying the subset construction to NNFA A R , we get a DFA for L R of at most 2 n states. The bound 2 n is known to be tight [START_REF] Lupanov | A comparison of two types of finite automata[END_REF][START_REF] Mirkin | On dual automata[END_REF], and the witness languages can be defined over a binary alphabet [START_REF] Jirásková | Reversal of binary regular languages[END_REF][START_REF] Leiss | Succinct representation of regular languages by Boolean automata[END_REF].

If a language L is represented by an n-state NFA A, then we can construct an NNFA A R for L R in the same way as for DFAs. An equivalent NFA may require one more state. The upper bound n + 1 is known to be tight, with worst-case examples defined over a binary alphabet [START_REF] Holzer | Nondeterministic descriptional complexity of regular languages[END_REF][START_REF] Jirásková | State complexity of some operations on binary regular languages[END_REF]. Our next result shows that the self-verifying state complexity of the reversal operation is given by the function 2n + 1. Notice that the reverse of our worst-case example is a generalization of our NFA language in Example 6.

Theorem 11 ([9]

). Let n ≥ 3. Let L be a regular language over an alphabet Σ with svsc(L) = n. Then svsc(L R ) ≤ 2n + 1, and the bound is tight if |Σ| ≥ 2.

Proof. Let A = (Q, Σ, δ, s, F a , F r ) be an SVFA for L. Then L is accepted by the n-state NFA N = (Q, Σ, δ, s, F a ), and L c is accepted by the n-state NFA N ′ = (Q, Σ, δ, s, F r ) by Proposition 1. By swapping the role of initial and final states in NFAs N and N ′ , and by reversing all the transitions, we get n-state NNFAs for languages L R and (L c ) R = (L R ) c . By Proposition 2, we have svsc(L R ) ≤ 2n + 1. This proves the upper bound.

For tightness, let L be the language accepted by the DFA A shown in Fig. 4. Construct an NFA A R for the language L R as described above. Denote by [i, j] the set of integers {k | i ≤ k ≤ j}; notice that [i, j] = ∅ if i > j. Consider the following family of 2n subsets

R = { [1, i] | 1 ≤ i ≤ n } ∪ { [i + 1, n] | 1 ≤ i ≤ n } .
Notice that each set in R is reachable in the subset automaton of the NFA A R from the initial subset {n -1}. Thus for each subset S in R, there is a string u S by which the initial state {n -1} of the subset automaton of A R goes to S. Consider the following set of 2n pairs of strings:

F = {(u [1,i] , a n-i ) | 1 ≤ i ≤ n} ∪ {(u [j+1,n] , a n-j ) | 1 ≤ j ≤ n}.
Let us show that the set F is an sv-fooling set for the language L R . First, notice that the string a n-i is accepted by the NFA A R from a subset S of [1, n] if and only if the state i is in the subset S. To show that F is an sv-fooling set for L, we have three cases to consider:

(1) Let 1 ≤ i < k ≤ n. Then u [1,i] • a n-k / ∈ L R and u [1,k] • a n-k ∈ L R .
(

) Let 1 ≤ j < ℓ ≤ n. Then u [j+1,n] • a n-ℓ ∈ L R and u [ℓ+1,n] • a n-ℓ / ∈ L R . 2
(3) Let 1 ≤ i ≤ n and 1 ≤ j ≤ n. Here we have two subcases:

(3a) If i ≤ j, then u [j+1,n] • a n-i / ∈ L R and u [1,i] • a n-i ∈ L R . (3b) If i > j, then u [1,i] • a n-j ∈ L R and u [j+1,n] • a n-j / ∈ L R .
Hence we have shown that F is an sv-fooling set for the language L R . Now, we use Lemma 9 to show that one more state is necessary for an SVFA to accept L R . To this aim, let w i = a n-1 for i = 1, 2, . . . , n, w n+j = ε for j = 1, 2 . . . , n -1, and w 2n = a. Then we have

ε • a n-1 / ∈ L R while u [1,i] • a n-1 ∈ L R if 1 ≤ i ≤ n and n ≥ 3, ε • ε / ∈ L R while u [j+1,n] • ε ∈ L R if 1 ≤ j ≤ n -1. ε • a ∈ L R while u ∅ • a / ∈ L R since n ≥ 3
. By Lemma 9, every SVFA for L R has at least 2n + 1 states. ⊓ ⊔

Boolean Operations

To get a DFA for the complement of a given regular language, we only need to interchange the final and non-final states in a DFA for the given language. Formally, if a regular language L is accepted by a DFA A = (Q, Σ, δ, s, F ), then the language L c is accepted by the DFA A ′ = (Q, Σ, δ, s, Q \ F ). Moreover, if A is minimal, then A ′ is minimal as well. It follows that the state complexities of a regular language and its complement are the same.

On the other hand, if a language is represented by an NFA, we first apply the subset construction to this NFA, and only after that we can interchange the final and non-final states. This gives an upper bound 2 n . This upper bound is known to be tight [START_REF] Birget | Partial orders on words, minimal elements of regular languages, and state complexity[END_REF][START_REF] Sakoda | Nondeterminism and the size of two-way finite automata[END_REF], and witness languages can be defined over a binary alphabet [START_REF] Jirásková | State complexity of some operations on binary regular languages[END_REF]. Our first observation shows that the self-verifying complexity of a language and its complement are the same.

Then we consider the following four Boolean operations: intersection, union, difference, and symmetric difference. In the general case of all regular languages, the state complexity of all four operations is given by the function mn, and the worst-case examples are defined over a binary alphabet [START_REF] Brzozowski | Quotient complexity of regular languages[END_REF][START_REF] Maslov | Estimates of the number of states of finite automata[END_REF][START_REF] Rabin | Finite automata and their decision problems[END_REF][START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF]. The nondeterministic state complexity of intersection and union is mn and m+n+1, respectively, with witness languages defined over a binary alphabet [START_REF] Holzer | Nondeterministic descriptional complexity of regular languages[END_REF].

The difference and symmetric difference on languages represented by NFAs have not been studied yet. Since both these operations require complementation, the nondeterministic state complexities m•2 n and m•2 n +n•2 m of difference and symmetric difference, respectively, could be expected. In the case of self-verifying state complexity, we obtain a tight upper bound mn for all four operations, with worst-case examples defined over a binary alphabet.

Theorem 12 ([9]

). Let K and L be languages over an alphabet Σ with svsc(K) = m and svsc(L) = n. Then (i) svsc(L c ) = n, (ii) svsc(K ∩ L), svsc(K ∪ L), svsc(K \ L), svsc(K ⊕ L) ≤ mn, and all the bounds are tight if |Σ| ≥ 2.

⊓ ⊔

Proof. (i) Let L be accepted by an SVFA A. To get an SVFA A ′ for the language L c , we only need to interchange the accepting and rejecting states in the SVFA A. Moreover, if A is minimal, then A ′ is minimal as well.

(ii) Now we consider intersection. Let K and L be accepted by

SVFAs A = (Q A , Σ, δ A , s A , F a A , F r A ) and B = (Q B , Σ, δ B , s B , F a B , F r B ) of m and n states. Construct the product automaton A × B = (Q, Σ, δ, s, F a , F r ), where Q = Q A × Q B ; s = (s A , s B ); F a = {(p, q) | p ∈ F a A and q ∈ F a B } and F r = {(p, q) | p ∈ F r A or q ∈ F r B }; δ((p, q), a) = δ A (p, a) × δ B (
q, a) for each (p, q) in Q and each a in Σ. The product automaton A × B accepts K ∩ L, and it is self-verifying.

For tightness, consider languages K = {w ∈ {a, b} * | # a (w) ≡ 0 mod m} and L = {w ∈ {a, b} * | # b (w) ≡ 0 mod n} accepted by an m-state and n-state DFAs, so also SVFAs, respectively. Then the set of pairs

F = {(a i b j , a m-i b n-j ) | 0 ≤ i ≤ m -1 and 0 ≤ j ≤ n -1} is an sv-fooling set of size mn for K ∩ L.
Let us continue with union and difference. Since K ∪L = (K c ∩L c ) c , and selfverifying state complexity of a language and its complement are the same, we can get an SVFA for the union of K and L as follows. We first construct SVFAs for K c and L c . Then we construct an SVFA for K c ∩ L c . Finally, we take an SVFA for the complement of the resulting language. As witness languages, we can take the complements of the witnesses for intersection. Similar considerations can be done also for difference since

K \ L = K ∩ L c .
Finally, we consider symmetric difference. To get the upper bound, we construct a product automaton for symmetric difference in a similar way as for intersection. However, now the sets of accepting and rejecting states are

F a = {(p, q) | p ∈ F a A and q ∈ F r B } ∪ {(p, q) | p ∈ F r A and q ∈ F a B }; F r = {(p, q) | p ∈ F a A and q ∈ F a B } ∪ {(p, q) | p ∈ F r
A and q ∈ F r B }. This is an mn-state SVFA for the symmetric difference of given languages.

For tightness, let K and L be languages accepted by DFAs A and B shown in Fig. 5. Construct a product automaton for K ⊕ L as described above, and notice that the set

F = {(a i b j , a m-1-i b n-1-j ) | 0 ≤ i ≤ m -1 and 0 ≤ j ≤ n -1} is an sv-fooling set for the language K ⊕ L. ⊓ ⊔ 0 1 . . . m-2 m-

Star

The state complexity of the star operation is 3/4 • 2 n with binary witness languages [START_REF] Jirásková | State complexity of some operations on binary regular languages[END_REF][START_REF] Maslov | Estimates of the number of states of finite automata[END_REF][START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF]. In the unary case, the tight bound on the state complexity of star is (n-1) 2 +1 [START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF][START_REF] Čevorová | Kleene star on unary regular languages[END_REF]. The nondeterministic state complexity of star is n+1, with witnesses defined over a unary alphabet [START_REF] Holzer | Nondeterministic descriptional complexity of regular languages[END_REF]. In this section we show that the self-verifying state complexity of star is 3/4 • 2 n . Our worst-case examples are defined over an alphabet which grows exponentially with n. However, for a four-letter alphabet, we still get an exponential lower bound 2 n-1 -1.

Theorem 13 ([9]

). Let L be a language over Σ with svsc(L) = n.

Then (i) svsc(L * ) ≤ 3/4 • 2 n , and the bound is tight if |Σ| ≥ 3/4 • 2 n + 1;
(ii) the bound 2 n-1 -1 can be met by a quaternary language.

Proof. (i) Let A = (Q, Σ, δ, s, F a , F r ) be an SVFA for L. If only the initial state s is accepting, then L * = L. Assume that A has k accepting states that are different from s. Construct an NFA A * for L * from A as follows. First, add a new initial and final state q 0 and for each symbol a in Σ, add a transition from q 0 to δ(s, a) if δ(s, a) ∩ F a = ∅, and to {s} ∪ δ(s, a) otherwise. Next, for each state q in Q and each symbol a, add a transition from q to s on a whenever δ(q, a)∩F a ̸ = ∅. The initial state of A * is q 0 , and the set of final states is {q 0 } ∪ F a . Now consider the subset automaton of A * . Notice that no set containing a state in F a and not containing s is reachable in the subset automaton. Next, we can show that the empty set is unreachable. Hence the subset automaton has at most 2 n-1 +2 n-1-k reachable subsets. The maximum is attained if k = 1, and it is equal to 3/4 • 2 n . To prove tightness, consider the following family of 3/4 • 2 n -1 subsets:

R = { S | S ⊆ {0, 1, . . . , n -1} and 0 ∈ S } ∪ { S | ∅ ̸ = S ⊆ {1, 2, . . . , n -2} } . Let Σ = {a, b} ∪ {c S | S ∈ R} be an alphabet consisting of 3/4 • 2 n + 1 symbols.
Let L be accepted by an n-state DFA A = ({0, 1, . . . , n -1}, Σ, δ, 0, {n -1}), where the transitions are defined as follows: δ(i, a)

= (i + 1) mod n; δ(0, b) = 0, δ(i, b) = i + 1 if 1 ≤ i ≤ n -2, and δ(n -1, b) = n -1; and for each set S in R, δ(i, c S ) = { 0, if i ∈ S, n -1, if i / ∈ S.
The transitions on a and b in A are shown in Fig. 6 (top-left), and the transitions on the symbol c {1,3} in the case of n = 5 are shown in Fig. 6 (bottom-right). Construct an NFA A * for the language L * as described above. Notice that each subset in R is reachable in the subset automaton of A * , that is, for each subset S in R, there is a string u S , by which {q 0 } goes to the subset S. Then the set

0 1 . . . m-2 m-1 a b a, b a, b a, b a b 0 1 2 3 4 c {1,3} c {1,3} c {1,3} c {1,3} c {1,3}
F = {(u S , c S ) | S ∈ R} is an sv-fooling set of size 3/4 • 2 n -1 for L * . Finally, by setting w S = ε if n -1 /
∈ S and w S = b otherwise, we use Lemma 9 to show that one more state is necessary in every SVFA for the language L * .

(ii) Consider the language L accepted by the quaternary DFA B shown in Fig. 7. Notice that the transitions on symbols a and b are the same as in the DFA A above. It follows that all the subsets of {0, 1, . . . , n -1}, that have been shown to be reachable in the subset automaton of A * , are reachable in the subset automaton of B * as well. In particular, all the non-empty subsets of {0, 1, . . . , n -2} are reachable. Similarly as in the proof above, let u S be a string over {a, b} by which the initial subset {q 0 } goes to S in the subset automaton. Our aim is to describe an sv-fooling set for L * of size 2 n-1 -1. To this aim, for every non-empty subset S of {0, 1, . . . , n-2}, define the string

v S = v 0 v 1 • • • v n-2 of length n -1 over {c, d} as follows: v n-2-i = { c, if i ∈ S, d, if i /
∈ S, that is, the string v S somehow describes the set S, however, in a reversed order: we can assign the symbol σ(i) = c to each state i in S and the symbol σ(i) = d to each state i outside the set S, and then we have v S = σ(n-2)σ(n-3) • • • σ(1)σ(0). Then, for every set S, the string v S is accepted by B * from every state outside the set S, while v S is rejected by B * from every state in S. It follows that

{(u S , v S ) | ∅ ̸ = S ⊆ {0, 1, . . . , n -2}} is an sv-fooling set for L * . ⊓ ⊔

Left and Right Quotients

The left quotient of a language L by a string w is w\L = {x | w x ∈ L}, and the left quotient of a language L by a language K is the language K\L = ∪ w∈K w\L. The state complexity of the left quotient operation is 2 n -1 [START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF], and its nondeterministic state complexity is n + 1 [START_REF] Jirásková | State complexity of some operations on binary regular languages[END_REF]. In both cases, the worst-case examples are defined over a binary alphabet.

The right quotient of a language L by a string w is L/w = {x | x w ∈ L}, and the right quotient of a language L by a language K is L/K = ∪ w∈K L/w. If a language L is accepted by an n-state DFA A = (Q, Σ, •, s, F ), then the language L/K is accepted by a DFA that is exactly the same as the DFA A, except for the set of final states that consists of all the states q of A, such that there exists a string w in K with q • w ∈ F [START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF]. Thus sc(L/K) ≤ n. The tightness of this upper bound has been shown using binary languages in [START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF].

Here we show that the self-verifying complexity of the left quotient operation is 2 n -1. To prove tightness, we use an exponential alphabet. Then, using a four letter alphabet, we get a lower bound 2 n-1 -1. Finally, we show that the selfverifying state complexity of right quotient is given by the function g(n), where g(n) is the tight upper bound for SVFA-to-DFA conversion given in (1) on page 3. Proof. (i) Let L be accepted by an SVFA A = (Q, Σ, δ, s, F a , F b ). Then the language K\L is accepted by an NNFA N = (Q, Σ, δ, I, F a ), where a state q is in I if it can be reached from the initial state of A by a string in K. After applying the subset construction to the NNFA N , we get a DFA for K\L, in which the empty set is unreachable. This gives the upper bound.

To prove tightness, consider the family R of all non-empty subsets of {0, 1, . . . , n -1}. Let Σ = {a, b} ∪ {c S | S ∈ R} be an alphabet consisting of 2 n + 1 symbols. Let K = a * ∪ a * b m-2 be a language over Σ. Then K is accepted by an m-state DFA, and the set Construct an NNFA N for the language K\L from the DFA B by making all the states of B initial. Each subset S in R is reachable in the subset automaton of the NNFA N by a string u S . Now, in the same way as in the proof of Theorem 13, we can prove that the set of pairs {(u S , c S ) | S ∈ R} is an sv-fooling set of size 2 n -1 for the language K\L.

{(b i , b m-2-i ) | 0 ≤ i ≤ m -2} ∪ {(b m-1 a, ε)} is an sv-fooling
(ii) The language K over {a, b, c, d} is the same as in (i). The language L is accepted by the DFA B ′ , in which the transitions on a and b are the same as in the DFA B above, and the transitions on c and d are the same as in Fig. 7. In a similar way as in the proof of Theorem 13 (ii), we can describe an sv-fooling set

{ (u S , v S ) | ∅ ̸ = S ⊆ {0, 1, . . . , n -2} } of size 2 n-1 -1 for K\L. ⊓ ⊔ Theorem 15 ([9]). Let K, L ⊆ Σ, svsc(K) = m, and svsc(L) = n. Then (i) svsc(L/K) ≤ g(n)
, and the bound is tight if |Σ| ≥ g(n) + 2;

(ii) the bound Ω(2 n/3 ) can be met by quaternary languages.

⊓ ⊔

Proof. (i) Let a language L be accepted by an n-state SVFA. First, convert this SVFA to an equivalent minimal DFA. By Theorem 4, this DFA has at most g(n) states. By making certain states final based on the language K, we get a DFA for L/K of at most g(n) states. For tightness, let n = 1 + 3k and k 2; the arguments can be extended to the other values of n in a straightforward way. Consider the grid Q = {(i, j) | 0 ≤ i ≤ 2 and 1 ≤ j ≤ k} of 3k nodes. Let R be the following family of 3

k subsets R = { {(i 1 , 1), (i 2 , 2), . . . , (i k , k)} | i 1 , i 2 , . . . , i k ∈ {0, 1, 2} } , that is, each
subset in R corresponds to a choice of one element in each column of the grid Q.

Let Σ = {a, b, c} ∪ {d S | S ∈ R} be an alphabet consisting of 3 + 3 k symbols. Let K = {c ℓ | ℓ ≥ m -2} be the language over Σ that contains all the strings in c * of length at least m -2. We have svsc(K) = m. Let L be accepted by a (3k + 1)-state SVFA B, in which the transitions on a, b are the same as in the binary witness for SVFA-to-DFA conversion in Theorem 4. Next, symbol c performs the cyclic permutation on each row of the grid Q, and maps the initial state to each state in the first row. Finally, for each set S in R, symbol d S maps every state (i, j) of S to the state (1, j), and it maps every state (i, j) outside S to (0, j). Then we can show that svsc(L/K) = g(n).

(ii) Let Σ = {a, b, c, d}. Let K = {c ℓ | ℓ ≥ m -2} be a language over Σ with svsc(K) = m. Let L be accepted by an n-state SVFA B ′ in which the transitions on a, b are the same as in the SVFA B in case (i). By c and d, the state q 0 goes to {(0, 1), . . . , (0, k)}, and each state (i, j) with j ≤ k -1 goes to {(i, j + 1)}. The state (0, k) goes to {(1, 1)} on both c, d. The state (1, k) goes to {(0, 1)} on c, and it goes to {(2, 1)} on d. The state (2, k) goes to {(2, 1)} on both c, d. Then we get svsc(L/K) ∈ Ω(2 n/3 ). ⊓ ⊔

Concatenation

The state complexity of concatenation is m2 n -2 n-1 , and its nondeterministic state complexity is m + n. In both cases, the worst-case examples can be defined over a binary alphabet [START_REF] Holzer | Nondeterministic descriptional complexity of regular languages[END_REF][START_REF] Jirásková | State complexity of some operations on binary regular languages[END_REF][START_REF] Maslov | Estimates of the number of states of finite automata[END_REF][START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF]. The aim of this subsection is to get asymptotically tight bound Θ(3 m/3 • 2 n ) on the self-verifying state complexity of the concatenation operation. Recall that g(n) is the tight upper bound for SVFA-to-DFA conversion given in (1) on page 3.

Theorem 16 ([9]

). Let K, L ⊆ Σ, svsc(K) = m, and svsc(L) = n. Then

(i) svsc(KL) ≤ g(m) • 2 n ; (ii) the bound 1/2 • g(m) • 2 n can be met if |Σ| ≥ g(m) + 2 n + 4; (iii) the bound Ω(2 m/3 • 2 n ) can be met if |Σ| ≥ 8.
Proof. (i) Let K and L be accepted by SVFAs A and B, respectively. First, convert the SVFA A to a minimal DFA A ′ . Then, construct an NNFA N for the language KL from automata A ′ and B in a usual way. Next, apply the subset construction to N . In the subset automaton of N , every reachable subset can be expressed as {q} ∪ T , where q is a state of A ′ and T is a subset of the state set of B. +2 n symbols. Let K be the language over Σ accepted by m-state SVFA A = (Q ∪ {q 0 }, Σ, δ, q 0 , F a , F r ), where the transitions on a, b, c are the same as in the case of right quotient, the symbols d, e, g T are ignored, and transitions on f S are defined by δ((i, j), f S ) =

{

{(1, j)}, if (i, j) ∈ S, {(0, j)}, if (i, j) / ∈ S; Let L be the language accepted by DFA B = ({0, 1, . . . , n -1}, Σ, •, 0, {0}), (iii) The idea of the proof is to define strings v S and v T over an eight-letter alphabet for some sets S in R, namely, for those that consist only of the states in the first and second row of the grid Q, and for each subset T of {1, . . . , n-2}. As a result, we get an sv-fooling set {(u S∪T , v T • v S • c 2k ) | S ∈ R ′ , T ⊆ {1, . . . , n -2}}, where R ′ contains all the sets in R which only have states in the the first or second row of the grid Q. This gives a lower bound in Ω(2 m/3 • 2 n ).

where i • a = i • b = i • c = i • f S = i; i • d = (i + 1) mod n; 0 • e = 0, i • b = i + 1 if 1 ≤ i ≤ n -2,
⊓ ⊔

Conclusions

Table 1 summarizes the results on the self-verifying state complexity of considered operations, and compares them to the known results on their state complexity and nondeterministic state complexity. The last column of the table displays the size of an alphabet which was used to define witness languages. For star and quotients, an exponential lower bound can be obtained by using a four-letter alphabet. In the case of concatenation, a lower bound in Ω(2 m/3 2 n ) is met by languages defined over an eight-letter alphabet. The tight upper bound for the concatenation operation remains open even in the case of a growing alphabet.

Fig. 1 .

 1 Fig. 1. The witnesses for SVFA-to-DFA conversion; n = 13, 12, and 14. maximum number of possible maximal cliques in a graph with n nodes and, as shown by Moon and Moser [17, Theorem 1], we have f(n) = 3 n/3 if n mod 3 = 0, f (n) = 4 • 3 ⌊n/3⌋-1 if n mod 3 = 1, and f (n) = 2 • 3 ⌊n/3⌋ if n mod 3 = 2.This gives the upper bound. For tightness, let A = (Q, {a, b}, δ, q 0 , F a , F r ), where n = 1 + 3m and m 2, see Fig.1(left) for m = 13, be an automaton defined by Q = {q 0 } ∪ {(i, j) | 0 i 2, 1 j m}, δ(q 0 , a) = δ(q 0 , b) = {(0, 1), (0, 2), . . . , (0, m)}, and for all i, j with 0 i 2 and 1 j m,

Fig. 2 .

 2 Fig. 2. Two non-isomorphic minimal SVFAs for the language (a + b) * a(a + b) 2 .

Fig. 3 .

 3 Fig. 3. An NFA for the language L in Example 6.

Fig. 4 .

 4 Fig. 4. The binary witness for reversal meeting the bound 2n + 1.

Fig. 5 .

 5 Fig. 5. The binary witnesses for symmetric difference meeting the bound mn.

Fig. 6 .Fig. 7 .

 67 Fig. 6. The witness for star; symbols a a b (top-left) and symbol c {1,3} for n = 5.

Theorem 14 (

 14 [START_REF] Jirásek | Operations on self-verifying finite automata[END_REF]). Let K, L ⊆ Σ, svsc(K) = m, and svsc(L) = n. Then (i) svsc(K\L) ≤ 2 n -1, and the bound is tight if |Σ| ≥ 2 n + 1;(ii) the bound 2 n-1 -1 can be met by quaternary languages.

  set of size m for the language K. Hence svsc(K) = m. Let L be accepted by an n-state DFA B = ({0, 1, . . . , n -1}, Σ, δ, 0, {n -1}), where the transitions are defined as follows:δ(i, a) = (i + 1) mod n; δ(0, b) = δ(1, b) = 0, and δ(i, b) = i if 2 ≤ i ≤ n-1;and for each subset S of {0, . . . , n-1}, we have δ(i, c S ) = 0 if i ∈ S, and δ(i, c S ) = n -1 otherwise.

  Since A is an SVFA, the DFA A ′ has at most g(m) states by Theorem 4. Thus the subset automaton of N has at most g(m) • 2 n reachable states.(ii) For the sake of simplicity, we consider the case ofm = 1 + 3k a k ≥ 2. Consider the grid Q = {(i, j) | 0 ≤ i ≤ 2 and 1 ≤ j ≤ k} of 3k nodes. Let R = { {(i 1 , 1), (i 2 , 2), . . . , (i k , k)} | i 1 , i 2 , . . . , i k ∈ {0, 1, 2} } . Let Σ = {a, b, c, d, e} ∪ {f S | S ∈ R} ∪ {g T | T ⊆ {0, 1, . .. , n -1}} be an alphabet consisting of 5+3m-1 3

  and (n -1)• b = 1; i • g T = { n -1, if i ∈ T , 0, if i / ∈ T . Construct an NFA N for KL and show that each set in the family R N = { S ∪ T | S ∈ R with (0, k) /∈ S, and T ⊆ {0, 1, . . . , n -1} } is reachable in the corresponding subset automaton. Then prove thatF = {(u S∪T , g T • f S • c k ) | S ∪ T ∈ R N }is an sv-fooling set for the language KL.

  Then we can get an SVFA A for L with m + n + 1 states from NFAs N and N ′ as follows. We add a new initial state s going to δ(I, a)∪δ ′ (I ′ , a) on each a in Σ. The state s is accepting if ε ∈ L, and it is rejecting otherwise. All the states in F are accepting in SVFA A, and all the states in F

′ are rejecting in A. ⊓ ⊔

Proposition 3 ([1, Theorem 2.1]). Every

	n-state SVFA can be converted to n) states. √ an equivalent DFA of at most O(2 n /
	Proof (Proof Idea). If S and T are two reachable subset of the subset automaton
	of an SVFA A such that S ⊆ T , then S and T are equivalent. This gives an upper bound ( n ⌊n/2⌋ ) ∈ O(2 n / √ n). ⊓ ⊔
	Theorem 4 (

[11, Theorem 9]). Every

	n-state SVFA can be converted to an
	equivalent DFA of at most g(n) states, where

Table 1 .

 1 The state complexity, nondeterministic, and self-verifying state complexity of basic regular operations.

		DFAs	NFAs	SVFAs	|Σ|
	complement	n	2 n	n	1
	intersection	mn	mn	mn	2
	union	mn	m + n + 1 mn	2
	difference	mn	?	mn	2
	symmetric difference mn	?	mn	2
	reversal	2 n	n + 1	2n + 1	2
	star	3/4 • 2 n	n + 1	3/4 • 2 n	3/4 • 2 n + 1
	left quotient	2 n -1	n + 1	2 n -1	2 n + 1
	right quotient	n	n	g(n)	g(n) + 2
	concatenation	(m -1 2 ) • 2 n m + n	Θ(3 m/3 • 2 n ) g(m) + 2 n + 4

⋆ Research supported by VEGA grant 2/0084/15.