Rishat Ibrahimov
email: rishat.ibrahimov@yandex.ru

Kamil Khadiev

Krišjānis Prūsis
email: krisjanis.prusis@lu.lv

Abuzer Yakaryılmaz
email: abuzer@lu.lv

Error-Free Affine, Unitary, and Probabilistic OBDDs

Keywords: Error-Free Affine, Unitary, and Probabilistic OBDDs Rishat Ibrahimov, Kamil Khadiev, Krišjānis Prūsis, Abuzer Yakaryilmaz OBDDs, affine models, quantum and probabilistic computation, zero-error, Las Vegas computation, succinctness

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

Introduction

Using negative transition values (allowing interference between states and configurations) is unarguably the main distinguishing property of quantum computational models. In order to define a quantum-like classical system, one can also introduce "negative probabilities" but the system is no longer linear. In this direction, affine systems were introduced as an almost linear 4 generalization of probabilistic systems that can use negative transitions [START_REF] Díaz-Caro | Affine computation and affine automaton[END_REF], and, due to their simplicity, affine finite automata (AfAs) have been examined in a series of papers by comparing them with classical and quantum finite automata [START_REF] Díaz-Caro | Affine computation and affine automaton[END_REF][START_REF] Villagra | Language recognition power and succinctness of affine automata[END_REF][START_REF] Belovs | On a conjecture by Christian Choffrut[END_REF][START_REF] Hirvensalo | On the computational power of affine automata[END_REF][START_REF] Villagra | Language recognition power and succinctness of affine automata[END_REF]. Both bounded-and unbounded-error AfAs have been shown to be more powerful than their probabilistic and quantum counterparts and they are equivalent to quantum models in nondeterministic acceptance mode [START_REF] Díaz-Caro | Affine computation and affine automaton[END_REF]. AfAs can also be very succinct on languages and promise problems [START_REF] Villagra | Language recognition power and succinctness of affine automata[END_REF][START_REF] Belovs | On a conjecture by Christian Choffrut[END_REF]. In this paper, we compare the computational power of error-free affine OBDDs with their probabilistic and unitary counterparts on solving total functions and recognizing languages.

Ordered Binary Decision Diagrams (OBDD), also known as oblivious read once branching programs [START_REF] Wegener | Branching Programs and Binary Decision Diagrams: Theory and Applications[END_REF], are an important restriction of branching programs. It is a good model of data streaming algorithms. Since the length of an OBDD is fixed (linear), the main complexity measure is "width", analogous to the number of states for automata models (see [START_REF] Wegener | Branching Programs and Binary Decision Diagrams: Theory and Applications[END_REF]). OBDDs can also be seen as a variant of nonuniform automata that allow accessing the input in a predetermined order and using possibly different sets of instructions in each step (e.g. [START_REF] Ablayev | Complexity of quantum uniform and nonuniform automata[END_REF]). It is known that [START_REF] Ablayev | On the computational power of probabilistic and quantum branching program[END_REF][START_REF] Ablayev | On the power of randomized branching programs[END_REF][START_REF] Ablayev | Randomization and nondeterminism are incomparable for ordered read-once branching programs[END_REF][START_REF] Sauerhoff | Quantum branching programs and space-bounded nonuniform quantum complexity[END_REF][START_REF] Khadiev | Reordering method and hierarchies for quantum and classical ordered binary decision diagrams[END_REF] the gap between the width of the following OBDD models can be at most exponential on total functions: deterministic and bounded-error probabilistic, deterministic and bounded-error unitary, and bounded-error probabilistic and bounded-error unitary. Each exponential gap has also been shown to be tight by presenting witness functions. On partial functions, on the other hand, the gap (width) between deterministic and exact unitary OBDDs was shown not to be bounded [START_REF] Ablayev | Very narrow quantum OBDDs and width hierarchies for classical OBDDs[END_REF][START_REF] Gainutdinova | Comparative complexity of quantum and classical OBDDs for total and partial functions[END_REF][START_REF] Ablayev | Very narrow quantum OBDDs and width hierarchies for classical OBDDs[END_REF].

In this paper, we introduce affine OBDDs and then compare error-free (zeroerror or Las Vegas) affine, unitary, probabilistic, and deterministic OBDD models. Zero-error probabilistic OBDDs are identical to deterministic OBDDs. Zeroerror unitary OBDDs cannot be narrower than deterministic OBDDs. On the other hand, zero-error affine OBDDs can be exponentially narrower than not only deterministic OBDDs but also bounded-error probabilistic and unitary OBDDs. With success probability 1 2 , Las Vegas probabilistic and unitary OBDDs can be quadratically narrower than deterministic OBDDs. We give an example function that achieves this bound up to a logarithmic factor. Finally, we examine the automata counterpart of these models and obtain similar results.

The preliminaries and definitions are given in the next section. The generic lower bounds are given in Section 3. The results on zero-error affine OBDD are given in Section 4 and the results on Las Vegas OBDDs are given in Section 5. We close the paper with automata results in Section 6. The extended version of the paper can be accessible on arXiv (1703.07184 ).

Preliminaries

We assume the reader familiar with the basics of branching programs. An Ordered Binary Decision Diagram (OBDD) can be defined as a non-uniform automaton that can read the input symbols in a predetermined order (see [START_REF] Wegener | Branching Programs and Binary Decision Diagrams: Theory and Applications[END_REF]).

An OBDD P reads the variables in a specific order π = (j 1 , . . . , j n ), called the order of P , and it can trace its computation on a finite set of states S = {s 1 , . . . , s m } such that (i) m is the width of OBDD, (ii) the initial state is the initial node, and (iii) the accepting states are the accepting sink nodes. Thus, each node in any level can be easily associated with a state in S. An OBDD can also have a different transition function at each level.

A probabilistic OBDD (POBDD) P n of width m is formally defined as a 5-tuple: P n = (S, T, v 0 , S a , π), where S = {s 1 , . . . , s m } is the set of states corresponding to at most one node in each level5 , v 0 is the initial probabilistic state, which is a stochastic column vector of size m, S a is the set of accepting states corresponding to the accepting sink nodes in the last level, π is a permutation of {1, . . . , n} defining the order of the input variables, and, T = {T 0 i , T 1 i | 1 ≤ i ≤ n} is the set of (left) stochastic transition matrices. Let x ∈ {0, 1} n be the given input. At the beginning of the computation P n is in v 0 . Then the input bits are read in the order π(1), π(2), . . . , π(n) and the corresponding stochastic operators are applied. That is, at the j-th step, we have v j = T

x π(j) j v j-1 , where v j-1 and v j are the probabilistic states before and after the transition, respectively, π(j) represents the input bit read in this step, x π(j) is the value of this bit, and T

x π(j) j is the stochastic operator applied in this step. We represent the final state as

v f = v n . The input x is accepted (the value of 1 is returned) with probability f Pn (x) = si∈Sa v f [i].
If all stochastic elements of transition matrices of a POBDD are composed of only 0s and 1s, then it is a deterministic OBDD.

Quantum OBDDs (QOBDD) using superoperators are non-trivial generalizations of POBDDs [START_REF] Ablayev | Very narrow quantum OBDDs and width hierarchies for classical OBDDs[END_REF]. In this paper, we use the most restricted version of quantum OBDDs called unitary OBDDs (UOBDDs) [START_REF] Gainutdinova | Nondeterministic unitary OBDDs[END_REF]. Note that UOBDDs and POBDDs are incomparable [START_REF] Sauerhoff | Quantum branching programs and space-bounded nonuniform quantum complexity[END_REF]. (We refer the reader to [START_REF] Say | Quantum finite automata: A modern introduction[END_REF] for a basic introduction to the basics of quantum computation.)

A UOBDD with width m, say M n , is a 5-tuple M n = (Q, T, |v 0 , Q a , π), where Q = {q 1 , . . . , q m } is the set of states, |v 0 is the initial quantum state, Q a is the set of accepting states, π is a permutation of {1, . . . , n} defining the order of the variables, and T = {T 0 i , T 1 i | 1 ≤ i ≤ n} is the set of unitary transition function matrices such that at the i-th step T 0 i (T 1 i ) is applied if the corresponding input bit is 0 (1).

Let x ∈ {0, 1} n be the given input. At the beginning of the computation M n is in |v 0 . Then the input bits are read in the order π(1), π(2), . . . , π(n) and the corresponding unitary operators are applied: |v j = T

x π(j) j |v j-1 . This represents the transition at the j-th step, where |v j-1 and |v j are the quantum states before and after the transition, respectively, π(j) represents the input bit read in this step, x π(j) is the value of this bit, and T

x π(j) j is the unitary operator applied in this step. We represent the final state as |v f = |v n . At the end of the computation, the final state is measured in the computational basis and the input is accepted if the observed state is an accepting one. Thus, the input x is accepted with probability f Mn (x) = qi∈Qa | q i |v f | 2 , where |q i represents the basis state corresponding to state q i and q i |v f gives the amplitude of q i in the final state.

An m-state affine system [START_REF] Díaz-Caro | Affine computation and affine automaton[END_REF] can be represented by the space R m , where R is the set of real numbers. The set of (classical) states is denoted E = {e 1 , . . . , e m }. Any affine state (similar to a probabilistic state) is represented as a column vector

v = (α 1 , α 2 , . . . , α m ) T ∈ R m such that m i=1 α i = 1
. Each e i also corresponds to a standard basis vector of R m having value 1 in its i-th entry. An affine operator is an m × m matrix, each column of which is an affine state, where the (j, i)-th entry represents the transition from state e i to state e j . If we apply an affine operator A to the affine state v, we obtain the new affine state v = Av. To get information from the affine state, a non-linear operator called weighting is applied, which returns any state with probability equal to the weight of the corresponding vector element in the l 1 norm of the affine state. If it is applied to v, the state e i is observed with probability

|αi| n j=1 |αj | = |αi| |v| , where |v| is the l 1 norm of v.
Here we define affine OBDDs (AfOBDDs) as a model with both classical and affine states, which is similar to the quantum model having quantum and classical states [START_REF] Ambainis | Two-way finite automata with quantum and classical states[END_REF]. This addition does not change the computational power of the model, but helps in algorithm construction.

An AfOBDD, say M n , having m 1 classical and m 2 affine states is an 9-tuple M n = (S, E, δ, T, s I , v 0 , S a , E a , π), where S = {s 1 , . . . , s m1 } is the set of classical states, s I ∈ S is the initial classical state, S a ⊆ S is the set of classical accepting states, E = {e 1 , . . . , e m2 } is the set of affine states, v 0 ∈ R m2 is the initial affine state, E a ⊆ E is the set of affine accepting states, π is a permutation of {1, . . . , n} defining the order of the variables, δ = {δ i : S × {0, 1} → S | 1 ≤ i ≤ n} is the classical transition function such that at the i-th step the classical state is set to δ i (s, x π(i) ) when in state s ∈ S and corresponding input bit is x π(i) , and,

T = {T s,0 i , T s,1 i | s ∈ S and 1 ≤ i ≤ n} is the set of affine transition matrices such that at the i-th step T s,0 i is applied if the corresponding input bit is 0 (or T s,1 i if it is 1) and the current classical state is s. The width of M n is equal to m 1 • m 2 .
Let x ∈ {0, 1} n be the given input. At the beginning of the computation M n is (s I , v 0 ). Then the input bits are read in the order π(1), π(2), . . . , π(n). In each step, depending on the current input bit and classical state, the affine state is updated and then the classical state is updated based on the current input bit. Let (s, v j-1 ) be the classical-affine state pair at the beginning of the j-th step. Then the new affine state is updated as v j = T s,x π(j) j v j-1 . After that the new classical state is updated by δ j (s, x π(j) ). At the end of the computation we have (s F , v f ). If s F / ∈ S a , then the input is rejected. Otherwise, the weighting operator is applied to v f , and the input is accepted with probability f Mn (x) =

ei∈Ea |v f [i]| |v f | .
Note that if we use only non-negative numbers for an AfOBDD, then we obtain a POBDD.

Any OBDD with π = (1, . . . , n) is called an id-OBDD. If we use the same transitions at each level of an id-OBDD, then we obtain a finite automaton (FA). A FA can also read an additional symbol after reading the whole input called the right end-marker ($) for the post-processing. We abbreviate the FA versions of OBDD, POBDD, QOBDD, UOBDD, and AfOBDD as DFA, PFA, QFA, UFA, and AfA, respectively. Remark that UFAs are also known as Measure-Once or Moore-Crutchfield quantum finite automata [START_REF] Moore | Quantum automata and quantum grammars[END_REF][START_REF] Ambainis | Automata and quantum computing[END_REF].

A Las Vegas automaton can make three decisions: "accept", "reject", and "don't know". Therefore, its set of states is split into three disjoint sets, the set of accepting, rejecting, and neutral states in which the aforementioned decisions are given, respectively. To be a well-defined Las Vegas algorithm, each member (resp., non-member) is rejected (resp., member) with zero probability, i.e. the algorithm never makes false classification, and the correct decision is given with probability at least p > 0.

We assume the reader is familiar with the basic terminology of computing functions and recognizing languages. Here we revise some necessary notations.

A function f : {0, 1} n → {1, 0} is computed by a bounded-error machine if each member of f -1 (1) is accepted with probability at least 1 -ε and each member of f -1 (0) is accepted with probability no more than ε for some nonnegative ε < 1 2 . If ε = 0, then the computation (and the machine) is called zero-error or exact.

In the case of FAs, languages are considered instead of functions and the term "language recognition" is used instead of "computing a function".

A Las Vegas FA can recognize a language L with success probability p < 1 (with error bound 1 -p) if each member is accepted and each non-member is rejected with probability at least p.

For a given language L, DFA(L), LV ε (L), and ULV ε (L) denote the number of states of a minimal DFA, a minimal LV-PFA and a minimal LV-QFA recognizing language L, respectively, where the error bound is ε for the probabilistic and quantum models. For a given Boolean function f , OBDD(f), LV-OBDD ε (f), and ULV-OBDD ε (L) denote the widths of a narrowest OBDD, a narrowest LV-POBDD and a narrowest LV-UOBDDs computing f , respectively, where the error bound is ε for the probabilistic and quantum models. Remark that in the case of zero-error we set ε = 0.

Lower Bounds

Let X = {X 1 , . . . , X n } be the set of variables. Let θ = (X A , X B ) be a partition of the set X into two parts X A and X B = X\X A . Let f | ρ be a "subfunction" of f , where ρ is a mapping ρ :

X A → {0, 1} |X A | . The function f | ρ (X B )
is obtained from f by fixing each variable from X A to its value under ρ. The concept of subfunction can be seen as a counterpart of Myhill-Neroda equivalence classes. Let N θ (f ) be the number of different subfunctions with respect to the partition θ. Let Π(n) be the set of all permutations of {1, . . . , n}. Let θ(π, u) = (X A , X B ) = ({X j1 , . . . , X ju }, {X ju+1 , . . . , X jn }), for the permutation

π = (j 1 , . . . , j n ) ∈ Π(n), 1 < u < n. We denote Θ(π) = {θ(π, u) : 1 < u < n}. Let N π (f ) = max θ∈Θ(π) N θ (f ), N (f ) = min π∈Π(n) N π (f ).
Based on techniques from communication complexity theory, it has been shown that exact quantum and probabilistic protocols have at least the same complexity as deterministic ones [START_REF] Klauck | On quantum and probabilistic communication: Las Vegas and one-way protocols[END_REF][START_REF] Hirvensalo | Lower bounds for Las Vegas automata by information theory[END_REF]. The followings are also known:

Fact 1 [START_REF] Ďuriš | Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations[END_REF][START_REF] Klauck | On quantum and probabilistic communication: Las Vegas and one-way protocols[END_REF][START_REF] Hromkovič | On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata[END_REF][START_REF] Hirvensalo | Lower bounds for Las Vegas automata by information theory[END_REF] For any regular language L and error bound ε < 1, we have the following lower bounds for PFAs and QFAs:

(DFA(L)) 1-ε ≤ LV ε (L) and (DFA(L)) 1-ε ≤ ULV ε (L).
Fact 2 [START_REF] Sauerhoff | Quantum branching programs and space-bounded nonuniform quantum complexity[END_REF] For any Boolean function f over X = (X 1 , . . . , X n ) and error bound ε < 1: (OBDD(f)) 1-ε ≤ ULV-OBDD ε (f).

These results are followed from certiain facts from communication complexity. We briefly remind the notion of communication complexity (see [START_REF] Kushilevitz | Communication complexity[END_REF]). Let h : {0, 1} q × {0, 1} m → {0, 1} be a Boolean function. We have two players called Alice and Bob, who compute h(x, y). The function h is known by both of them, but Alice can see only x and Bob can see only y. First, Alice sends message(s) to Bob and then Bob returns the answer. Alice's aim is trying to minimize the number of sending bits. The protocol is called Las Vegas if Alice chooses her messages randomly, and then Bob returns the correct answer with probability at least 1 -ε and gives-up (has error) with the remaining probability.

The communication complexity of function h(x, y) equals to c if and only if the minimum number of bits sent during the communication is equal to c. It is denoted as C(h) if the protocol is deterministic and LV -C ε (h) if the protocol is Las Vegas and the probability of giving-up is bounded by ε. The relation between these two complexity measures is presented in the following fact:

Fact 3 [START_REF] Ďuriš | Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations[END_REF][START_REF] Klauck | On quantum and probabilistic communication: Las Vegas and one-way protocols[END_REF][START_REF] Hromkovič | On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata[END_REF][START_REF] Hirvensalo | Lower bounds for Las Vegas automata by information theory[END_REF] For any Boolean function h and an error bound ε < 1, we have the following lower bound:

(1 -ε)C(h) ≤ LV -C ε (h).
Facts 1 and 2 follows from Fact 3 and a simulation of automata and OBDD by communication protocols (see [START_REF] Hromkovič | On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata[END_REF][START_REF] Khadiev | On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs[END_REF]).

We can easily extend the result from Fact 2 for the probabilistic OBDD model as well. For this purpose, we also use the following fact.

Theorem 1. For any Boolean function f over X = {X 1 , . . . , X n } and error bound ε < 1: (OBDD(f)) 1-ε ≤ LV-OBDD ε (f).

Proof. Let d = OBDD(f). Due to [START_REF] Wegener | Branching Programs and Binary Decision Diagrams: Theory and Applications[END_REF], we have N (f ) = d. Assume that there is a Las Vegas OBDD P of width w, i.e. w < d 1-ε . Let u = argmax t N θ(π(P ),t) (f ) and θ = θ(π(P ), u). Then P can be simulated by a Las Vegas probabilistic protocol (see [START_REF] Khadiev | On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs[END_REF]) with log 2 w < (1 -ε) log 2 d bits. By the definition of the number of subfunctions, we have N θ (f ) ≥ d. Moreover, it is known that the deterministic communication complexity of a function is log 2 (N θ (f )) = log 2 d. But we also have a Las Vegas communication protocol which uses log 2 w < (1 -ε) log 2 d communication bits, which contradicts with Fact 3.

It is trivial that these results imply equivalence for exact (zero-error) computation, where ε = 0.

Zero-Error Affine OBDDs

We show that exact AfOBDDs can be exponentially narrower than classical and unitary quantum OBDD models. For this purpose we use two different functions.

The hidden weighted bit function [START_REF] Wegener | Branching Programs and Binary Decision Diagrams: Theory and Applications[END_REF] HWB n : {0, 1} n → {0, 1} returns the value of x z on the input x = (x 1 , . . . , x n ) where z

= x 1 + • • • + x n , taking x 0 = 0.
It is known [START_REF] Wegener | Branching Programs and Binary Decision Diagrams: Theory and Applications[END_REF] that any OBDD solving HWB n has a minimum width of 2 n/5 /n. Due to Fact 2 and Theorem 1, the same bound is also valid for exact POBDDs and UOBDDs. Theorem 2. An exact id-AfOBDD M with n classical and n affine states can solve HWB n .

Proof. The classical states are s 0 , . . . , s n-1 where s 0 is the initial and only accepting state. The affine states are e 0 , . . . , e n-1 where e 0 is the only accepting affine state and v 0 is e 0 .

Until reading the last input bit (x n ), for each value 1, the index of the classical state is increased by 1. Meanwhile, the value of x i is written to the value of e i in the affine state: the affine state after the (i -1)-th step becomes

v i-1 = (1 x 1 • • • x i-1 0 • • • 0) T , where 1 = 1 - i-1 j=1 x j . If x i = 0,
then the identity operator is applied. If x i = 1, then the following affine transformation is applied

             0 -1 • • • -1 0 0 0 . . . I (i-1)×(i-1)
. . .

0 0 1 1 • • • 1 1 0 0 I              ,
which updates the values of e 0 and e i as -i-1 j=1 x j and 1, respectively, and does not change the other entries. Remark that the first entry can also be written as 1 -i j=1 x j . Thus, before reading x n , the classical state is s t for t = x 1 + • • • + x n-1 , and, the affine state is

v n-1 = (1 x 1 x 2 • • • x n-1 ) T , where 1 is 1- n-1 j=1 x j .
After reading x n , the classical state is always set to s 0 and so the decision is made based on the affine state. Each pair of s t and x n determine an appropriate last affine transformation that sets the final affine state to v f = (x z 1 -x z 0 • • • 0) T , where x z is set to either 0 or 1. The details of each last transition are as follows: (i) if t = 0 and x n = 0, then the corresponding last transitions sets x z = 0, (ii) if t = n -1 > 0, then regardless the value of x n , the corresponding last transition sets x z = 1, and (iii) in any other case, z = t + x n and the corresponding last transition sets x z to the (z + 1)-th entry of v n-1 . Based on x z , the final decision is given: if x z = 0 (resp., x z = 1), then the input is accepted with probability 0 (resp., 1).

For a positive integer n, let x, y be the inputs of size n, let p(n) be the smallest prime number greater than n, and let s n (x) = (

n i=1 i • x i ) mod p(n).
The mixed weighted sum function [START_REF] Sauerhoff | Quantum vs. classical read-once branching programs[END_REF]

MWS n : {0, 1} n ×{0, 1} n → {0, 1} is defined as MWS n (x, y) = x i ⊕ y i if i = s n (x) = s n (y) ∈ {1, .
. . , n}, and 0 otherwise. Any bounded-error POBDD or UOBDD solving MWS n has a width of at least 2 Ω(n) /n [START_REF] Savickỳ | A read-once lower bound and a (1,+ k)-hierarchy for branching programs[END_REF][START_REF] Sauerhoff | Quantum vs. classical read-once branching programs[END_REF]. The same bound is also valid for OBDDs, and so for exact POBDDs and UOBDDs as well.

Before presenting our affine algoroithm for MWS n , we consider its simpler version: the weighted sum function [START_REF] Sauerhoff | Quantum vs. classical read-once branching programs[END_REF] WS n (x) : {0, 1} n → {0, 1}, defined as WS n (x) = x sn(x) if s n (x) ∈ {1, . . . , n}, and 0 otherwise. Theorem 3. An exact id-AfOBDD can solve WS n with p(n) classical states and n affine states.

Proof. We use almost the same algorithm given in the previous proof. The affine part is the same. The new classical states are s 0 , . . . , s p(n)-1 with the same initial and single accepting state s 0 . Until reading x n , the same affine transitions are applied:

v n-1 = (1 x 1 x 2 • • • x n-1 ) T , where 1 is 1 - n-1 j=1 x j .
The classical transitions are modified as follows: The classical state before reading x i (i < n), say s j , is set to s j+i•xi mod p(n) . Thus, before reading x n , the classical state is s t where t = n-1 i=1 i • x i mod p(n). At this point, the pair s t and x n sets the affine state to v f = (x sn(x) 1 -x sn(x) 0 • • • 0) T and then the classical state is set to s 0 . Here x sn(x) = 0 if t + n • x n mod p(n) / ∈ {1, . . . , n}. Otherwise, depending on the value of s n (x), x sn(x) is set to the corresponding value from v n-1 or directly to x n . Theorem 4. An exact id-AfOBDD can solve MWS n with p 2 (n) classical states and (n + 1) affine states.

Proof. The classical states are {s i,j | 0 ≤ i, j < p(n)} where s 0,0 is the initial state and the accepting states are {s i,i | 1 ≤ i ≤ n}. While reading all bits, the values of s n (x) and s n (y) are calculated and stored as the values of the first and second index of the classical states, respectively. Let s i,j be the final state. It is clear that if i = j or i = j but not in {1, . . . , n}, the input is rejected classically. In the remaining part, we assume that the final classical state is s i,i with i ∈ {1, . . . , n}. Thus, the final decision is given based on the final affine state.

The affine states are {e 0 , . . . , e n } where e 0 is the single accepting state. The initial affine state is v 0 = e 0 .

While reading the first part of the input, all x values are encoded in the affine state as (1 (-1)

x1 (-1) x2 • • • (-1) xn ) T , where 1 = 1 - n i=1 (-1) xi .
Then, for each y j (1 ≤ j ≤ n), we multiply the j-th entry of the affine state by (-1) yj (and update the first entry accordingly). Thus, the j-th entry becomes (-1) xj +yj , which is equal to 1 if x j = y j and -1 if x j = y j .

The last affine transformation is a composition of three affine transformations. The first transformation is the one explained above for y n . By using the second one, the affine state is set to ((-1

) xi+yi 1 -(-1) xi+yi 0 • • • 0) T .
Here the first two entries are (1 0) T for members and (-1 2) T for nonmembers. By using the third transformation, we can add half of the second entry to the first entry and so get respectively (1 0) T and (0 1) T . Thus the AfOBDD can separate members from non-members with zero error.

-If the scanned symbol is 0, then, for calculating the XOR value, the 2 d -th entry is multiplied by 1, i.e., 0 → 0 and 1 → 1. -If the scanned symbol is 1, then, for calculating the XOR value, the 2 d -th entry is multiplied by -1 and then 1 is added to this result, i.e., 0 → 0 → 1 and 1 → -1 → 0.

The last entry in the affine state is used to make the state vector well-formed. For example, if the state vector has 0 ≤ t ≤ 2 d 1s in its first 2 d entries, then the last entry is 1 -t.

After reading the whole input, the first 2 d entries keep the storage. We know the address i from our classical state s i -we move the corresponding storage value from e i to e 1 and sum all other entries in e 2 . Then, if the first entry is 1, the rest of the vector contains only 0. If the first entry is 0, the second entry is 1 and the rest of the vector contains 0. Therefore, any member (resp., non-member) of SSA n is accepted by A with probability 1 (resp., 0).

Las Vegas Automata and Zero-Error AfAs

Similar to OBDDs, for ε = 1 2 , the lower bound for finite automata (Section 3) is at most quadratic. Up to a constant, this quadratic gap is achieved by

END k = {u1v | u, v ∈ {0, 1} * and |v| = k-1}: DFA(END k ) = 2 k and LV 0.5 (END k ) ≤ 4•2 k/2 .
Here, we propose a new language MODXOR k based on which we improve the above constant for LV-PFAs and provide a LV-UFA algorithm with the same size as LV-PFAs. Then, we show that an AfA can recognize it with exponentially fewer states with zero error. The language MODXOR k for k > 0 is formed by the strings {0, 1} <2k x 1 {0, 1} 2k-1 x 2 {0, 1} 2k-1 • • • x m {0, 1} 2k-1 where m > 0, each x i ∈ {0, 1} for 1 ≤ i ≤ m, and m i=0 x i = 1, taking x 0 = 0. First, we give a lower bound for DFAs. Similarly to OBDDs, exact AfAs can also be exponentially more efficient than their classical and quantum counterparts.

Theorem 12. The language MODXOR k for k > 0 can be recognized by a (2k + 1)state AfA A with zero-error.

Proof. The AfA A does not use any classical state and it has 2k + 1 affine states, {e 1 , . . . , e 2k+1 }. The initial state is e 2k+1 and the only accepting state is e 1 . It starts its computation in v 0 = (0 • • • 0 1)

T . During the computation, it keeps the results in the values of the first 2k states, i.e. it sets each value to 0 or 1 depending the previous results and the current scanning symbols. More specifically, before each transition, the first 2k entries are shifted to the right by one and the 2k-th entry becomes the first entry. Then, depending on the scanned symbol, the value of the first entry is updated:

-If the scanned symbol is 0, then, for calculating XOR value, the first entry is multiplied by 1, i.e., 0 → 0 and 1 → 1. -If the scanned symbol is 1, then, for calculating XOR value, the first entry is multiplied by -1 and then 1 is added to this result, i.e., 0 → 0 → 1 and 1 → -1 → 0.

The last entry in the affine state is used to make the state vector well-formed. For example, if the state vector has 0 ≤ t ≤ 2k 1s in its first 2k entries, then the last entry is 1 -t. After reading the whole input, the first entry has the result and the rest of entries are summed to the second entry: if the first entry is 1 (resp., 0), then the rest of the vector contains only 0 (resp., 1). Therefore, any member (resp., non-member) is accepted by A with probability 1 (resp., 0).

Theorem 9 .

 9 DFA(MODXOR k ) ≥ 2 2k for each k > 0. Theorem 10. LV 0.5 (MODXOR k ) ≤ 2 • 2 k for any k > 0. Theorem 11. ULV 0.5 (MODXOR k ) ≤ 2 • 2 k for any k > 0.

Part of the research work was done while Ibrahimov was visiting University of Latvia in February 2017.[START_REF] Ablayev | On the computational power of probabilistic and quantum branching program[END_REF] It evolves linearly but a non-linear operator is applied when we retrieve information from the state vector.

Suppose we have wi ≤ m nodes on a level i; then the node uj of this level corresponds to the state sj, for j ∈ {1, . . . , wi}

Acknowledgements. We thank Evgenijs Vihrovs (University of Latvia) for his helpful discussions and anonymous reviewers for their very helpful comments.

The work is partially supported by ERC Advanced Grant MQC, Latvian State Research Programme NeXIT project No. 1. The work is also performed according to the Russian Government Program of Competitive Growth of Kazan Federal University. The research on Las-Vegas OBDDs (Section 5) is supported by Russian Science Foundation Grant 17-71-10152

Las Vegas POBDDs and UOBDDs

For OBDDs with ε = 1 2 , the lower bounds given in Section 3 can be at most quadratic. Up to a logarithmic factor, this quadratic gap was achieved by using the SA d function in [START_REF] Sauerhoff | Quantum branching programs and space-bounded nonuniform quantum complexity[END_REF] for id-OBDDs. Here we give the same result for OB-DDs (for any order) using the SSA n function and also provide an LV-UOBDD algorithm with the same size as the LV-OBDD.

We start with the well-known Storage Access Boolean Function SA d (x, y) = x y , where the input is split into the storage x = (x 1 , . . . , x 2 d ) and the address y = (y 1 , . . . , y d ).

By using the idea of "Shuffling" from [START_REF] Ablayev | Randomization and nondeterminism are incomparable for ordered read-once branching programs[END_REF][START_REF] Ablayev | On the power of randomized branching programs[END_REF][START_REF] Ablayev | Very narrow quantum OBDDs and width hierarchies for classical OBDDs[END_REF][START_REF] Ablayev | Very narrow quantum OBDDs and width hierarchies for classical OBDDs[END_REF], we define the Shuffled Storage Access Boolean function SSA n : {0, 1} n → {0, 1} for even n. Let x ∈ {0, 1} n be an input. We form two disjoint sorted lists of even indexes of bits I 0 = (2i 1 , . . . , 2i m ) and

Let d be such that 2 d + d = n/2. We can construct two binary strings by the following procedure: initially α(x) := 0 2 d , then for r from 1 to m we do α(x) := ShiftX(α(x), x 2ir ), where ShiftX((a 1 , ..., a m ), b) = (a 2 , ..., a m , a 1 ⊕ b). And initially β(x) := 0 d , then for r from 1 to k: β(x) := ShiftX(β(x), x 2jr ). Then, SSA n (x) = SA d (α(x), β(x)). Firstly, we provide a lower bound for OBDDs. Proof. The set of classical states is {(p, s) | p ∈ {p 0 , p 1 } and s ∈ {s 0 , . . . , s 2 d -1 }} having 2 d+1 states. The states p j denote whether the next even bit to read is a storage or address bit. The state s i corresponds to the current address being i. Every classical state is accepting, and so the decision is made based on the final affine state. The AfOBDD also has 2 d + 1 affine states, {e 1 , . . . , e 2 d +1 }. The initial state is e 2 d +1 , i.e. v 0 = (0

T , and the only accepting state is e 1 . During the computation, it keeps the value of the storage in the first 2 d states. Specifically, if (i) the next position to read is odd or (ii) even but an address bit (we are in a state (p 1 , s i )), then we perform the identity transformation on the affine state and change only the classical state. If we are reading a storage bit, the classical state remains unchanged and we implement the ShiftX operation on the storage: first, the 2 d entries are shifted to the left by one and the first entry becomes the 2 d -th entry. Then, depending on the scanned symbol, the value of the 2 d -th entry is updated:


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

Alexander Okhotin
email: alexander.okhotin@spbu.ru

State complexity of unambiguous operations on deterministic finite automata

The paper determines the number of states in a deterministic finite automaton (DFA) necessary to represent "unambiguous" variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state DFA, the state complexity is mn -1; for the unambiguous concatenation, it is known to be m2 n-1 -2 n-2 (Daley et al., "Orthogonal concatenation: Language equations and state complexity", J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be 3 8 2 n + 1. In the case of a unary alphabet, disjoint union requires up to 1 2 mn states, unambiguous concatenation has state complexity m + n -2, and unambiguous star requires n -2 states in the worst case.

Introduction

The basic operations on formal languages are union, concatenation and Kleene star. The main models for language description, namely, regular expressions and formal grammars, use these operations to express the structure of strings. An important special case of concatenation is unambiguous concatenation. Concatenation of two formal languages, K and L, is said to be unambiguous, if every string w in KL has a unique representation as w = uv, with u ∈ K and v ∈ L. The union operation also has its unambiguous special case: the disjoint union. These two operations are important, in particular, for giving rise to unambiguous grammars. One can also define the unambiguous Kleene star : the Kleene star of any language L with the property that every string in L * has a unique decomposition as a concatenation of zero or more strings in L.

This paper investigates the succinctness of description of these three unambiguous operations by deterministic finite automata (DFA). The state complexity of union, concatenation and Kleene star in their unrestricted form has long been known: Maslov [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF] was the first to determine their state complexity as mn states for the union, m2 n -2 n-1 states for the concatenation and 3 4 2 n states for the Kleene star, where m and n is the number of states in the DFA recognizing the arguments. These results were further elaborated by Yu et al. [START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF] and by Jirásek et al. [START_REF] Jirásek | State complexity of concatenation and complementation[END_REF]. For nondeterministic finite automata (NFA), the state complexity of these operations was determined by Holzer and Kutrib [START_REF] Holzer | Nondeterministic descriptional complexity of regular languages[END_REF], a similar study for two-way finite automata (2DFA) was carried out by Jirásková and Okhotin [START_REF] Jirásková | On the state complexity of operations on two-way finite automata[END_REF], whereas Jirásek Jr. et al. [START_REF] Jirásek | Operations on unambiguous finite automata[END_REF] determined the state complexity of basic operations for unambiguous finite automata (UFA). In the literature, special consideration was given to the case of the unary alphabet, where state complexity results are different: for DFA, as established by Yu et al. [START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF] and by Pighizzini and Shallit [START_REF] Pighizzini | Unary language operations, state complexity and Jacobsthal's function[END_REF], both union and concatenation require up to mn states for relatively prime m, n, and fewer states for other values of m, n; the star requires (n -1) 2 + 1 states. The state complexity of basic operations for unary two-way automata was established by Kunc and Okhotin [START_REF] Kunc | State complexity of union and intersection for two-way nondeterministic finite automata[END_REF][START_REF] Kunc | State complexity of operations on two-way deterministic finite automata over a unary alphabet[END_REF], and by Okhotin [START_REF] Okhotin | Unambiguous finite automata over a unary alphabet[END_REF] for unary UFA.

The question addressed in this paper is, do these state complexity results essentially depend on using ambiguity, that is, on taking a union of overlapping languages, on concatenating languages that allow some strings to be obtained in multiple ways, and on taking the star of languages with multiple partitions? If union, concatenation or star is restricted to be unambiguous, will it become substantially easier to express?

In the case of the disjoint union operation, investigated in Section 3, it turns out that it can be represented with one state less than the union in general: that is, mn -1 states are sufficient to represesent disjoint union of a pair of DFA with m and with n states. It is also proved that this number of states is in the worst case necessary, with witness languages defined over a binary alphabet. For the unary alphabet, the state complexity is 1 2 mn, under certain assumptions on m and n.

For the unambiguous concatenation, it is already known from Daley at al. [START_REF] Daley | Orthogonal concatenation: Language equations and state complexity[END_REF] that it requires exactly half as many states as concatenation in general: its state complexity is m2 n-1 -2 n-2 . The witness languages of Daley at al. [START_REF] Daley | Orthogonal concatenation: Language equations and state complexity[END_REF] are defined over a four-symbol alphabet. In this paper, new binary witness languages for this operation are constructed in Section 4. In the unary case, the state complexity of this operation is only m + n -2.

Finally, as established in Section 5, representing the unambiguous star takes half as many states as star in general, plus one extra state: its state complexity is 3 8 2 n + 1, with witness languages over a binary alphabet. In the unary case, its state complexity is n -2.

Basic notions

As usual, a deterministic finite automaton (DFA) is defined as a quintuple A = (Σ, Q, q 0 , δ, F ) where Σ is an input alphabet; Q is a finite non-empty set of states; q 0 ∈ Q is the initial state; δ : Q × Σ → Q is the transition function; F ⊆ Q is the set of accepting states. The computation of A on a string w = a 1 . . . a n , with a 1 , . . . , a n ∈ Σ, is the uniquely defined sequence of states r 0 , . . . , r n ∈ Q, in which r 0 = q 0 , r i = δ(r i-1 , a i ) for all i. If r n ∈ F , the DFA is said to accept the string w. The language recognized by a DFA, denoted by L(A), is the set of all strings it accepts.

It is convenient to extend the transition function to act on strings in Σ * , as δ : Q × Σ * → Q, with δ(q, ε) = q and δ(q, aw) = δ(δ(q, a), w). In these terms, L(A) = { w | δ(q 0 , w) ∈ F }. Also, the function is sometimes extended to act on sets of states, as δ(S, w) = { δ(q, w) | q ∈ S }.

A state q of a DFA is called dead, if no string is accepted from q. In a minimal DFA, there can be at most one dead state. A state q of a DFA is called cyclic if there is a non-empty string v with δ(q, v) = q.

A DFA over a unary alphabet Σ = {a} is a chain of transitions by a that eventually turns back to one of the previous states. The repetitive part is called the cycle, and the earlier states outside of the cycle form the tail. Thus, the language is ultimately periodic, beginning from (the length of the tail), with the length of the cycle as the period.

A nondeterministic finite automaton (NFA) is a quintuple A = (Σ, Q, Q 0 , δ, F ), where Q 0 ⊆ Q is the set of possible initial states and the transition function δ : Q × Σ → 2 Q may define multiple next states. An NFA accepts a string w = a 1 . . . a n if there exists a sequence of states r 0 , . . . , r n ∈ Q, with r 0 ∈ Q 0 , r i ∈ δ(r i-1 , a i ) for all i, and r n ∈ F .

In some literature, NFAs are defined with a unique initial state, that is, with Q 0 = {q 0 }. Every NFA can be converted to an NFA with a unique initial state by adding a new initial state.

An NFA A = (Σ, Q, Q 0 , δ, F ) can be transformed to an equivalent DFA with states corresponding to subsets of Q. The subset Q 0 is then the initial state of the DFA, its set of final states is {S ⊆ Q | S ∩F = ∅}, and its transition function δ : 2 Q × Σ → 2 Q is defined by δ (S, a) = q∈S δ(q, a).

Union

In general, the union of an m-state DFA A = (Σ, P, p 0 , γ, E) and an n-state DFA B = (Σ, Q, q 0 , δ, F ) can be recognized by a DFA with mn states, known as the direct product DFA. Its set of states is the set of all pairs P × Q, the initial state is (p 0 , q 0 ), the transition function simulates A on the first component and B on the second component, thus mapping (p, q) by a to (γ(p, a), δ(q, a)); and a pair (p, q) is accepting if p ∈ E or q ∈ F .

For automata without the disjointness restriction, mn states are in the worst case necessary [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF]. It turns out that if the union is disjoint, then the construction can be improved by one state.

Lemma 1. For every m-state DFA A and for every n-state DFA B, with m, n 2 and with L(A) ∩ L(B) = ∅, there is a DFA with mn -1 states that recognizes the disjoint union L(A) ∪ L(B).

0 A 1 . . . m -2 m -1 a a a a b b b b a 0 B 1 . . . n -2 n -1 b b b b a a a a b
Fig. 1. Binary witnesses for disjoint union meeting the upper bound mn -1.

Indeed, if any pair (p, q), with p accepting in A and q accepting in B, were reachable in the direct product automaton, then the union would not be disjoint. Thus, all such pairs can be excluded from the mn-state construction. Putting aside the trivial case of either automaton having no accepting states, at least one such pair exists.

It remains to show that this number of states, mn -1, is necessary in the worst case.

Lemma 2. For all m, n 2, there exist languages K, L ⊆ {a, b} * , recognized by an m-state and an n-state DFA, respectively, with K ∩ L = ∅, for which every DFA recognizing K ∪ L has at least mn -1 states.

Proof (a sketch). The desired witness languages are recognized by the pair of automata shown in Fig. 1. Every string in K ends with a, while every string in L ends with b, and therefore, K and L are disjoint. In the direct product automaton, each pair (i, j) is reachable by a i b j if i m -2, and by a m-1 b j a for i = m -2.

For every two pairs (i, j) and (k, ), if i < k, then the string a m-1-k is accepted from (i, j), but not from (k, ). The case of j < is symmetric.

The next theorem summarizes the results of the two lemmata above.

Theorem 3 (Disjoint Union). Let A and B be an m-state and n-state DFA, respectively, such that L(A) ∩ L(B) = ∅. Then the language L(A) ∪ L(B) is recognized by a DFA of at most mn -1 states. This upper bound is tight, and it is met by the binary witness languages recognized by DFAs shown in Fig. 1.

The union operation in the case of a unary alphabet still requires all mn states, as long as m and n are relatively prime; the reduction of state complexity in the case when m and n have common divisors was studied by Pighizzini and Shallit [START_REF] Pighizzini | Unary language operations, state complexity and Jacobsthal's function[END_REF]. However, if the union is disjoint, then it can be represented using half as many states.

Theorem 4 (Unary Disjoint Union). Let m, n 4. Let A be an m-state DFA and B an n-state DFA, both defined over a unary alphabet Σ = {a}, with L(A) ∩ L(B) = ∅. Then the disjoint union L(A) ∪ L(B) is recognized by a DFA with at most 1 2 mn states. This upper bound is tight whenever m and n are even numbers with m 2 and n 2 relatively prime, and it is met by the languages (a m ) * and a(a n ) * .

Proof. If either of the automata defines a finite language, then the union is recognized by a DFA with m + n states, which cannot exceed 1 2 mn: indeed,

m + n 2 max(m, n) 1 2 min(m, n) max(m, n) = 1 2 mn.
Assume that both languages are infinite. Let k be the length of the cycle in A, and let be the length of the cycle in B.

If the cycle lengths in A and in B are relatively prime, then the union is ambiguous. Let d be the greatest common divisor of their cycle lengths. Then the union L(A)∪L(B) is recognized by a DFA with a cycle of length lcm(k, ) = 1 d k , which is at most 1 2 k . In addition, there are max(m -k, n -) non-cyclic states. Assume that m -k n -. Then the number of states in the DFA is estimated as follows.

1 2 k + m -k 1 2 k + 1 2 (m -k) = 1 2 m 1 2 mn
Now, consider the tightness. Since the first language consists of even-length strings and the other one of odd-length strings, their union is disjoint. Since gcd(m, n) = 1 2 mn, the union is periodic with this period, and therefore every DFA recognizing the union must have at least this many states.

Concatenation

The state compliexity of unambiguous concatenation has been investigated before, and the following result is known.

Theorem A (Daley et al. [START_REF] Rampersad | State complexity of unique rational operations[END_REF]) Let A by an m-state DFA, and B an n-state DFA. If the concatenation L(A)L(B) is unambiguous, then it can be represented by a DFA with m2 n-1 -2 n-2 states. The bound is tight for a four-symbol alphabet.

This paper improves the tightness result by showing that the upper bound cannot be reduced already for a binary alphabet. omitting the dead state n -1 of B, by adding the transitions from p i to 0 by a, for all p i ∈ P \ {p m-1 }, and by making both p 0 and 0 initial. Each reachable subset is represented as (p, S) with p ∈ P and S ⊆ Q\{n-1}.

The first goal is to show that for each set S ⊆ Q, the state (p 0 , {0} ∪ S) is reachable, and so is each state (p i , S), with 1 i m -1. The proof is by induction on |S|. In the base case, |S| = 0, each pair (p i , ∅), with i ∈ {1, 2, . . . , m -1}, is reached as follows. (p 1 , S )

(p 0 , {0}) b - → (p 1 , {0}) (b m-2 a) n-2 --------→ (p 1 , {n -2}) b m-2 a ----→ (p 1 , ∅) b i-1 ---→ (p i , ∅)
ab -→(p 1 , {0} ∪ {q -j | q ∈ S \ {j}}) (b m-2 a) j ------→ (p 1 , {j} ∪ {q | q ∈ S \ {j}}) = (p 1 , S)
(2) 2 i m -1. Then (p 1 , S) was shown to be reachable in case (1), and (p i , S) is reached from it by the string b i-1 .

(3) i = 0. Then (p 1 , {q -1 | q ∈ S \ {0}}) is reachable as in case (1), and (p 0 , {0} ∪ S) is reached from it by the symbol a.

This proves the reachability of (m -1)2 n + 2 n-1 = m2 n -2 n-1 states.

To prove distinguishability, let (p i , S) and (p j , T ) be two distinct states. If S = T , let j ∈ Q be in their symmetric difference, and assume, without loss of generality, that j ∈ S and j / ∈ T . Then the string a n-2-j is accepted from (p i , S), but not from (p j , T ). Let S = T , and, without loss of generality, let i < j. Then the string b m-1-j a distinguishes (p i , S) and (p j , S) since

(p j , S) b m-1-j -----→ (p m-1 , S) a -→ p 1 , {q + 1 | q ∈ S} , (p i , S) b m-1-j -----→ (p m-1-(j-i) , S) a -→ p 0 , {0} ∪ {q + 1 | q ∈ S} ,
so, the resulting states differ in the second component, and therefore are distinguishable.

All the above results are summarized in the next theorem. Then, the unary case is discussed.

Theorem 6 (Unambiguous Concatenation). Let A and B be an m-state and n-state DFA, respectively, such that the concatenation L(A)L(B) is unambiguous. Then the language L(A)L(B) is recognized by a DFA of at most m2 n-1 -2 n-2 states. This upper bound is tight, and it is met by the binary witness languages recognized by the DFAs shown in Fig. 2.

Theorem 7 (Unary Unambiguous Concatenation). Let m, n

2, let A be an m-state and B an n-state DFA over a unary alphabet Σ = {a}, and let the concatenation L(A)L(B) be unambiguous. Then L(A)L(B) is recognized by a with at most m + n -2 states, and this upper bound is tight.

Proof. If both languages are infinite, then the concatenation is ambiguous. Therefore, one of the automata defines a finite language; since concatenation is commutative, there is no loss of generality in the assumption that this is A. Then A recognizes some subset of {ε, a, a 2 , . . . , a m-2 }.

Let L(B) be periodic with period k, beginning from ; then, k + n. Then, the concatenation L(A)L(B) is periodic with period k, beginning from m + -2, and is therefore recognized by a DFA with m + n -2 states.

In the worst case, m+n-2 states are necessary to represent the unambiguous concatenation of two unary languages represented by an m-state and an n-state DFA, which is witnessed by the singleton languages {a m-2 } and {a n-2 }. Their concatenation {a m+n-4 } requires a DFA with m + n -2 states.

Star

The star of an n-state DFA is representable by a DFA with 3 4 2 n states, and this number is in the worst case necessary [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF]. However, if the star is unambiguous, then the necessary number of states can be reduced. The proof is based on the property that for the star to be unambiguous, the automaton has to have a dead state. This property is in turn based on the following auxiliary result. Lemma 8. If a DFA A = (Σ, Q, q 0 , δ, F ), with L(A) = ∅, has no dead states, then there is an accepting state q ∈ F which is in a cycle, that is, δ(q, u) = q for some non-empty string u ∈ Σ * . Proof. Let u 0 ∈ L(A). Then δ(q 0 , u 0 ) = q 1 for some accepting state q 1 . Since A does not have any dead state, there is a non-empty string u 1 accepted from q 1 . Let q 2 = δ(q 1 , u 1 ) be the state, in which it is accepted. This yields a sequence of accepting states q i and non-empty strings u i , with i 1. Since A has finitely many accepting states, this sequence eventually revisits some state, that is, q i = q j for some i < j. Then the state q i is cyclic, with q i = δ(q i , u 1 . . . u j-1 ).

Lemma 9.

If A is a DFA and the star L(A) * is unambiguous, then A has a dead state.

Proof. Let A = (Σ, Q, q 0 , δ, F ) be a minimal DFA for L. Suppose for a contradiction that A does not have any dead state. Then, by Lemma 8, there is an accepting state p ∈ F and a nonempty string v ∈ Σ * , with δ(p, v) = p. Consider the sequence of states q i , with i 0, defined by q i = δ(q 0 , v i ). Since the number of states in A is finite, there are numbers j 0 and k 1 with q j = q j+k , and thus δ(q j , v k ) = q j . Now let u be a string, by which p is reached from q 0 , and let w be any string accepted from q j , Then the string uv j+k w can be partitioned as u • v j+k w or uv k • v j w, which is a contradiction with the unambiguity of L * . Therefore, A must have a dead state.

Lemma 10. For every n 4, the language L n = (a * b) n-3 b(ab) * is recognized by an n-state DFA, the star L * n is unambiguous, and every DFA recognizing L * n must have at least 3 8 2 n + 1 states.

Proof. The language L n is recognized by the DFA A shown in Fig. 3, Construct an NFA A * from A by omitting the dead state n -1, by adding the transition (n -3, b, 0), and by adding one more initial and final state s; see Fig 4 . The NFA A * is unambiguous, since the intersection of every reachable and every co-reachable set of A * is of size at most one. Let us show that the subset automaton D(A * ) has 3 8 2 n + 1 reachable and pairwise distinguishable states. The initial subset is {s, 0} and it is sent to the state [0, n -3] by b n-3 (ba) n . Next, every subset S of [0, n -3] can be shifted cyclically by one, that is, it can be sent to {(s + 1) mod (n -2) | s ∈ S}, by reading b if n -3 / ∈ S, by reading ba if {n -4, n -3} ⊆ S, and by reading baa if n -3 ∈ S and n -4 / ∈ S. Moreover, the state n -3 can be eliminated from every subset of [0, n -3] containing the state n -3 by reading a. It follows that every subset of [0, n -3] is reachable from [0, n -3]. To prove distinguishability, let S and S be any two distinct reachable subsets of the subset automaton D(A * ). Then they must differ in some state i ∈ [0, n-2]. Assume, without loss of generality, that i ∈ S and i / ∈ S Then, the string b n-2-i is accepted from S, but not from S .

The next theorem summarizes the results on the star operation. Then, the unary case is discussed.

Theorem 11 (Unambiguous Star). Let n 4 and A be an n-state DFA such that L(A) * is unambiguous. Then the language L(A) * is accepted by a DFA of at most 3 8 2 n + 1 states. This upper bound is tight, and it is met by the binary witness language (a * b) n-3 b(ab) * . Proof. To get an NFA A * for L * from the DFA A, first omit the dead state. Then add the transition (q, a, q 0 ) whenever δ(q, a) ∈ F . Finally, add one more initial and final state s with no transitions going from it. In the subset automaton D(A * ), the initial subset is {s, q 0 }, and no other reachable subset contains q 0 . Moreover, no subset which contains a final state of A but does not contain state q 0 is reachable. In total, the number of reachable subsets in D(A * ) is at most 1 + 2 n-1 -2 n-2 = 3 8 2 n + 1. The tightness of this upper bound follows from Lemma 10.

Theorem 12 (Unary Unambiguous Star).

Let A be an n-state unary DFA such that L(A) * si unambiguous. Then L(A) * is accepted by a DFA of at most n-2 states. This upper bound is tight, and it is met by the unary language {a n-2 }.

Proof. In the unary case, for L * to be unambiguous, L must be a singleton. Furthermore, if an n-state DFA recognizes a singleton {a }, then n -2, whereas the star of this language, (a ) * , is recognized by a DFA with states. Thus, unambiguous star of a unary DFA is representable using n -2 states. This number of states is necessary, witnessed by the language {a n-2 }.

DFA UFA NFA ∪ mn [17] m + O(n2 0.79m ) [11] m + n [9] mn -1 m + n m + n • m2 n -2 n-1 [17] 3 4 2 m+n -1 [11] m + n [9] unamb• m2 n-1 -2 n-2 [20] m + n m + n * 3 4 2 n [17] 3 4 2 n [11] n + 1 [9] unamb * 3 8 2 n + 1 n + 1 n + 1

Summary of results

State complexity of basic operations on regular languages and of their unambiguous variants studied in this paper is compared in Table 1 for three automata models: DFA, UFA and NFA.

For the three unambiguous operations on DFA, their state complexity has been established in this paper. These operations are easy to apply to UFA using the standard constructions for the union, concatenation and star of NFA: indeed, since the operations are unambiguous, they preserve the unambiguity of the automata involved; however, it remains to establish matching lower bounds.

Another line of related state complexity research is concerned with basic operations on prefix-free languages, that is, those with the property that uv ∈ L, with v ∈ Σ + , implies that u / ∈ L. Suffix-free languages are defined similarly. Notably, for prefix-free and for suffix-free languages, both concatenation and star are unambiguous, and hence the state complexity results on these subcases are natural tight upper bounds for these two operations. For prefix-free languages and for the DFA model, union has state complexity mn -2 [START_REF] Jirásková | Complexity in prefix-free regular languages[END_REF], the state complexity of concatenation is m + n -1 [START_REF] Han | Operational state complexity of prefix-free regular languages[END_REF][START_REF] Jirásková | Complexity in prefix-free regular languages[END_REF], whereas the star has state complexity n [START_REF] Han | Operational state complexity of prefix-free regular languages[END_REF][START_REF] Jirásková | Complexity in prefix-free regular languages[END_REF]. For suffix-free languages, the results are completely different: union has state complexity mn-m-n+2 [START_REF] Han | State complexity of basic operations on suffix-free regular languages[END_REF]13], concatenation has (m-1)2 n-2 +1 [START_REF] Han | State complexity of basic operations on suffix-free regular languages[END_REF][START_REF] Cmorik | Basic operations on binary suffix-free languages[END_REF], and for the star it is 2 n-2 + 1 [START_REF] Han | State complexity of basic operations on suffix-free regular languages[END_REF][START_REF] Cmorik | Basic operations on binary suffix-free languages[END_REF].

One more related research direction is the recent study of variants of the basic operations on languages defined over the field GF(2) instead of the standard Boolean logic [START_REF] Bakinova | Formal languages over GF(2)[END_REF]. The union operation turns into the symmetric difference, whereas concatenation gives rise to the following new GF(2)-concatenation operation.

K L = { w | # of partitions w = uv, with u ∈ K and v ∈ L, is odd }

The GF(2)-star is defined similarly, so as to preserve only the strings with an odd number of partitions. Notably, the unambiguous operations studied in this unamb• m + n -2 m + n m + n * (n -1) 2 + 1 [START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF] (n -1) 2 + 1 [START_REF] Okhotin | Unambiguous finite automata over a unary alphabet[END_REF] n + 1 [START_REF] Holzer | Nondeterministic descriptional complexity of regular languages[END_REF] unamb * n -2 n + 1 n + 1

Table 2. State complexity of operations in the case of a unary alphabet.

paper are a special case of the GF(2) operations in the same way as they are a special case of classical operations: indeed, the differences between classical and GF(2) operations are in the treatment of ambiguity. As the GF(2) operations preserve regularity, their state complexity is worth being compared to the unambiguous and the classical cases. So far, it has been proved that for DFA, GF(2)-concatenation has state complexity m • 2 n , while the state complexity of the GF(2)-star is 2 n + 1 [START_REF] Bakinova | Formal languages over GF(2)[END_REF].

Another incomparable extension of unambiguous concatenation and star are the unique concatenation and the unique star [START_REF] Rampersad | State complexity of unique rational operations[END_REF], defined similarly, using the uniqueness of partition as the condition of membership. The state complexity of unique concatenation is at most m3 n -3 n-1 , and for the unique star the upper bound is 2 • 3 n-1 -3 4 2 n + 2 [START_REF] Rampersad | State complexity of unique rational operations[END_REF], their tightness remains open. In the next Table 2, the state complexity of all the same operations is compared in the case of a unary alphabet. Again, for DFA, the state complexity of unambiguous operations has been established, whereas for UFA and for NFA there are only obvious upper bounds. For UFA, the state complexity of standard operations remains to be investigated, with only a few results known [START_REF] Okhotin | Unambiguous finite automata over a unary alphabet[END_REF].

Lemma 5 .Fig. 2 .

 52 Fig. 2. Binary witnesses for unambiguous concatenation meeting the upper bound m2 n-1 -2 n-2 .

  that for each set S with |S | = k -1, each state (p i , S) with 1 i m -1 and the state (p 0 , {0} ∪ S) is reachable. Let S ⊆ Q and |S| = k. Consider several cases:(1) i = 1. Let j = min S. Take S = {q -j -1 | q ∈ S \ {j}}. Then S ⊆ Q and |S | = k -1, so the state (p 1 , S ) is reachable by the induction assumption. The state (p 1 , S) is reachable from it as follows.

Fig. 3 .

 3 Fig. 3. A binary witness for unambiguous star meeting the upper bound 3 8 2 n +1.

Fig. 4 .

 4 Fig. 4. NFA A * for the star of the language accepted by DFA A from Fig. 3.

Table 1 .

 1 State complexity of standard and unambiguous operations for DFA, UFA and NFA: union (∪), disjoint union ( ), concatenation (•), unambiguous concatenation (unamb•), Kleene star ( * ), unambiguous Kleene star (unamb * ).

Research supported by VEGA grant 2/0084/15 and grant APVV-15-0091.