Viliam Geffert

Abuzer Yakaryılmaz

Classical Automata on Promise Problems *

Keywords: descriptional complexity, promise problems, nondeterministic automata, probabilistic automata, alternating automata

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Second, despite of the existing quadratic gap between Las Vegas realtime probabilistic automata and oneway deterministic automata for language recognition, we show that, by turning to promise problems, the tight gap becomes exponential. Last, we show that the situation is different for one-way probabilistic automata with two-sided bounded-error. We present a family of unary promise problems that is very easy for these machines; solvable with only two states, but the number of states in two-way alternating or any simpler automata is not limited by a constant. Moreover, we show that one-way bounded-error probabilistic automata can solve promise problems not solvable at all by any other classical model.

Introduction

Promise problem is a generalization of language recognition. Instead of testing all strings over a given alphabet for language membership, we focus only on a given subset of strings as potential inputs that should be tested. The language under consideration and its complement form this subset.

Promise problems have already provided several different perspectives in computational complexity. (See the survey by Goldreich [START_REF] Goldreich | On promise problems: A survey[END_REF].) For example, it is not known whether the class of languages recognizable by bounded-error probabilistic polynomial-time algorithms has a complete problem, but the class of promise problems solvable by the same type of algorithms has some complete problems. A similar phenomenon has been observed for quantum complexity classes [START_REF] Watrous | Quantum computational complexity[END_REF]. The first known result on promise problems for restricted computational models we are aware of was given by Condon and Lipton in 1989 [START_REF] Condon | On the complexity of space bounded interactive proofs (extended abstract)[END_REF]. They showed that a promise version of emptiness problem is undecidable for one-way probabilistic finite automata. In the literature, some separation results regarding restricted computational models have also been given in the form of promise problems. (See, e.g., [START_REF] Dwork | A time complexity gap for two-way probabilistic finitestate automata[END_REF][START_REF] Dwork | Finite state verifiers I: The power of interaction[END_REF].) The first result for restricted quantum models was given by Murakami et al. [START_REF] Murakami | Quantum versus classical pushdown automata in exact computation[END_REF]: There exists a promise problem that can be solved by quantum pushdown automata exactly but not by any deterministic pushdown automaton. Recently, Ambainis and Yakaryılmaz [START_REF] Ambainis | Superiority of exact quantum automata for promise problems[END_REF] showed that there is an infinite family of promise problems which can be solved exactly just by tuning transition amplitudes of a one-way two-state quantum finite automaton (QFA), whereas the size of the corresponding classical automata grows above any fixed limit. Then, a series of papers [START_REF] Rashid | Implications of quantum automata for contextuality[END_REF][START_REF] Gainutdinova | Unary probabilistic and quantum automata on promise problems[END_REF][START_REF] Nakanishi | Quantum pushdown automata with a garbage tape[END_REF][START_REF] Nakanishi | Classical and quantum counter automata on promise problems[END_REF] presented many superiority results of QFAs over their classical counterparts. Meanwhile, some further results on succinctness of QFAs have been obtained in [START_REF] Zheng | State succinctness of two-way finite automata with quantum and classical states[END_REF][START_REF] Gruska | Generalizations of the distributed Deutsch-Jozsa promise problem[END_REF][START_REF] Gruska | Potential of quantum finite automata with exact acceptance[END_REF][START_REF] Zheng | On the state complexity of semi-quantum finite automata[END_REF][START_REF] Maria | Complexity of promise problems on classical and quantum automata[END_REF]. As a very recent study, different from the standard approach, Gruska et al. [START_REF] Gruska | Recognizability versus solvability of promise problems in finite classical and quantum automata framework[END_REF] focused on a subset of promise problems by introducing a new framework in which they extended the definition of the standard automaton so that the set of all accepting and rejecting states does not necessarily form the set of all states. Such automaton corresponds to a unique promise problem such that each yes-instance (no-instance) leads the automaton to an accepting (a rejecting) state. (i) In this paper, we turn our attention to classical models and obtain some new results. In the next two sections, we give some preliminaries and present some basic facts for the classical models. Among others, we show that (i) the computational power of deterministic, nondeterministic, alternating, and Las Vegas probabilistic automata is the same, even after turning from the classical language recognition to solving promise problems, and, (ii) on promise problems, neither existing gaps of succinctness for classical language recognition can be violated, between any two of deterministic, nondeterministic, and alternating automata models.

Then, in Section 4, we consider a family of unary promise problems given by Ambainis and Yakaryılmaz in [START_REF] Ambainis | Superiority of exact quantum automata for promise problems[END_REF], solvable by only two-state one-way quantum finite automata. On the other hand, for solving this family by the use classical automata, we show that the exact number of states for one-way/two-way deterministic/nondeterministic automata is the same. Thus, for this family, replacing the classical oneway deterministic automata even by two-way nondeterministic automata does not help to save a single state. However, for the same family, already the one-way alternation does help, which gives us the tight exponential gap between one-way alternating and two-way sequential models of automata solving unary promise problems.

In Section 5, we show that the trade-off for the case of Las Vegas probabilistic versus one-way deterministic automata is different; by turning from language recognition to promise problems the tight quadratic gap changes to a tight exponential gap.

In Section 6, we show how the situation changes for finite state automata with two-sided bounded-error. First, we present a probabilistically very easy family of unary promise problems, i.e., solvable by one-way two-state automata with bounded-error. Then, we show that this family is hard for two-way alternating automata, and hence for any simpler classical automata as well. Finally, we prove that, on promise problems, bounded-error probabilistic automata are more powerful than any other classical model.

(i) In this way, for example, the class of promise problems defined by deterministic finite automata simply forms the set of all pairs of disjoint regular languages, i.e., {(P 1 , P 2 ) | P 1 and P 2 are disjoint regular languages}.

Preliminaries

We assume the reader is familiar with the basic standard models of finite state automata (see e.g. [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF]). For a more detailed exposition related to probabilistic automata, the reader is referred to [START_REF] Paz | Introduction to Probabilistic Automata[END_REF][START_REF] Bukharaev | Probabilistic automata[END_REF]. Here we only recall some models and introduce some elementary notation.

By Σ * , we denote the set of strings over an alphabet Σ. The set of strings of length n is denoted by Σ n and the unique string of length zero by ε. By N + , we denote the set of all positive integers. The cardinality of a finite set S is denoted by S .

A one-way nondeterministic finite automaton with ε-moves (1 ε NFA, for short) is a quintuple A = (S, Σ, H, s I , S A ), where S is a finite set of states, Σ an input alphabet, s I ∈ S an initial state, and S A ⊆ S a set of accepting (final) states. Finally, H ⊆ S × (Σ ∪ {ε}) × S is a set of transitions, with the following meaning. s a -→ s ∈ H: if the next input symbol is a, A gets from the state s to the state s by reading a from the input. s ε -→ s ∈ H: A gets from s to s without reading any symbol from the input. (ii) The machine A halts in the state s, if there are no executable transitions in H at a time. Typically, this happens after reading the entire input, but the computation may also be blocked prematurely, by undefined transitions, i.e., by absence of transitions for the current state s and the next input symbol a (or ε).

An accepting computation starts in the initial state s I and, after reading the entire input, it halts in any accepting state s ∈ S A . The language recognized (accepted) by A, denoted by L(A), is the set of all input strings having at least one accepting computation. The inputs with no accepting computation are rejected.

A two-way nondeterministic finite automaton (2NFA) is defined in the same way as 1 ε NFA, but now A can move in both directions along the input. For these reasons, the transitions in H are upgraded as follows. s a → -→ s , s a← -→ s , s a -→ s : if the current input symbol is a, A gets from s to s and moves its input head one position to the right, to the left, or keeps it stationary, respectively. The input is enclosed in between two special symbols " " and " ", called the left and right endmarkers, respectively. By definition, the input head cannot leave this area, i.e., there are no transitions moving to the left of nor to the right of . A starts in s I with the input head at the left endmarker and accepts by halting in s ∈ S A anywhere along the input tape.

A deterministic finite automaton (1 ε DFA or 2DFA) can be obtained from 1 ε NFA or 2NFA by claiming that the transition set H does not allow executing more than one possible transition at a time. Consequently, a 1 ε DFA A can have at most one transition s a -→ s , for each s ∈ S and each a ∈ Σ. In theory, one can consider ε-transitions (even though this feature is rarely utilized): a transition s ε -→ s implies that there are no other transitions starting in the same state s. Similar restrictions can be formulated for 2DFAs.

A self-verifying finite automaton (1 ε SVFA or 2SVFA) [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF] is a 1 ε NFA or 2NFA A which is additionally equipped with S R ⊆ S, the set of rejecting states disjoint from S A , the set of accepting states. The remaining states form S N = S \ (S A ∪ S R ), the set of neutral "don't know" states. In this model, (i) for each accepted input, A has at least one computation path halting in an accepting state and, moreover, no path halts in a rejecting state, (ii) for each rejected input, A has at least one computation path halting in a rejecting state and, moreover, no path halts in an accepting state. In both these cases, some computation paths may return "don't know" answers, by halting in neutral states or by getting into infinite loops.

(ii) Traditionally [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF], the behavior is defined by a function δ : S × (Σ ∪ {ε}) → 2 S . However, a traditional transition δ(s, a) s can be easily converted to s a -→ s and vice versa. In the same way, all models introduced here are consistent with the traditional definitions. Using transitions instead of a δ-function, we just make the notation more readable.

A one-way probabilistic finite automaton with ε-moves (1 ε PFA) is defined in the same way as 1 ε NFA, but the transitions in H are upgraded with probabilities, as follows. s a,p -→ s ∈ H: if the current input symbol is a, A gets from the state s to the state s by reading this symbol with probability p ∈ [0, 1]. For a = ε, no input symbol is consumed. A transition with p = 1 may be displayed as s a -→ s , since the next step is deterministic; transitions with p = 0 can be completely erased, as not executable. By definition, (iii) for each s ∈ S and each a ∈ Σ, the sum of probabilities over all transitions beginning in s and labeled by a ∈ {a, ε} must be equal to 1. The overall accepting probability of A on a given input w ∈ Σ * , denoted by f A (w), is calculated over all accepting paths. Hence, the overall rejecting probability is 1-f A (w).

A two-way version, 2PFA, was first introduced in [START_REF] Yu | Two-way probabilistic automata[END_REF].

A Las Vegas probabilistic finite automaton (Las Vegas 1 ε PFA or Las Vegas 2PFA) [START_REF] Hromkovič | On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata[END_REF] is a 1 ε PFA or 2PFA of special kind, obtained from self-verifying automata (i.e., from nondeterministic automata of special kind). Thus, transitions are upgraded with probabilities, and the state set is partitioned into the sets of accepting, rejecting, and neutral "don't know" states. This gives three overall probabilities on a given input; accepting, rejecting, and neutral.

A one-way alternating finite automaton with ε-moves (1 ε AFA) is obtained from 1 ε NFA by partitioning the state set S into two disjoint subsets S ∃ and S ∀ , the sets of existential and universal states, respectively. The global rules are defined as is usual for alternating devices (see e.g. [6]): if, at the given moment, there are several executable transitions, the machine A (i) nondeterministically chooses one of them, if it is in an existential state s, but (ii) follows, in parallel, all possible branches, if the current state s is universal.

For better readability, a nondeterministic switch from the existential s into one of the states s 1 , . . . , s k , by reading an input symbol a, will be displayed as s a -→ s 1 ∨ • • • ∨ s k , while a parallel branching from the universal s to all these states as s a -→ s 1 ∧ • • • ∧ s k . The same applies for a = ε. The input is accepted, if all branches in the nondeterministically chosen computation subtree, rooted in the initial state at the beginning of the input and embedded in the full tree of all possible computation paths, halt in accepting states at the end of the input. (iv) Also this model was extended to a two-way version, 2AFA (see e.g. [START_REF] Geffert | An alternating hierarchy for finite automata[END_REF]).

A realtime automaton (rtDFA, rtSVFA, rtNFA, rtPFA, rtAFA,. . . ) is the corresponding one-way finite automaton (v) that executes at most a constant number of ε-transitions in a row. (After that, the next input symbol is consumed or the machine halts.)

A one-way ε-free automaton (1DFA, 1SVFA, 1NFA, 1PFA, 1AFA,. . . ) is the corresponding one-way finite automaton with no ε-transitions at all. (This is a special case of a realtime machine, with the number of executed ε-transitions bounded by zero.)

It should be pointed out that, in 1 ε NFAs, the ε-transitions can be removed without increasing the number of states [START_REF] Kumar | Theory of Automata, Languages, and Computation[END_REF]Sect. 2.11]. Therefore, 1NFAs, rtNFAs, and 1 ε NFAs agree in upper/lower bounds for states. The same works for 1SVFAs, rtSVFAs, and 1 ε SVFAs, as well as for 1DFAs, rtDFAs, and 1 ε DFAs. For this reason, we consider only 1NFAs, 1SVFAs, and 1DFAs.

(iii) Traditionally [START_REF] Michael | Probabilistic automata[END_REF], the behavior of PFAs is defined by stochastic matrices. (iv) The alternating automaton should not be confused with a Boolean finite automaton, which is (quite inappropriately) also sometimes called "alternating" in some literature. Instead of alternating existential and universal branching, the Boolean automaton can control acceptance by the use of arbitrarily complex Boolean functions. As an example, s a -→ s 1 ∧ (s 2 ∨ s 3 ) specifies that, for the current input symbol a, the subtree rooted in the state s is successful if and only if the subtree rooted in s 1 and at least one of those rooted in s 2 , s 3 are successful. (v) All realtime quantum models use a classical input head and so they are not allowed to create a superposition of the head positions on the input tape.

Occasionally, we shall also mention some restricted versions of two-way machines, e.g., sweeping automata, changing the direction of the input head movement only at the endmarkers [START_REF] Sipser | Lower bounds on the size of sweeping automata[END_REF][START_REF] Kapoutsis | Size complexity of rotating and sweeping automata[END_REF], or a very restricted version of sweeping automaton called a restarting one-way automaton, running one-way in an infinite loop [START_REF] Yakaryılmaz | Succinctness of two-way probabilistic and quantum finite automata[END_REF] -if the computation does not halt at the right endmarker, then it jumps back to the initial state at the beginning of the input.

A promise problem is a pair of languages P = (P yes , P no ), where P yes , P no ⊆ Σ * , for some Σ, and P yes ∩ P no = ∅ [START_REF] Watrous | Quantum computational complexity[END_REF].

The promise problem P is solved by a finite automaton P, if P accepts each w ∈ P yes and rejects each w ∈ P no . (That is, we do not have to worry about the outcome on inputs belonging neither to P yes nor to P no .) If P yes ∪ P no = Σ * and P is solved by P, we have a classical language recognition, and say that P yes is recognized by P.

If P is a probabilistic finite automaton, we say that P solves P with error bound ε ∈ [0, 1 2 ), if P accepts each w ∈ P yes with probability at least 1-ε and rejects each w ∈ P no with probability at least 1-ε. (The remaining probability goes to erroneous answers.) P solves P with a bounded-error, if, for some ε, it solves P with the error bound ε. If ε = 0, the problem is solved exactly.

A special case of bounded-error is a one-sided bounded-error, where either each w ∈ P yes is accepted with probability 1 or each w ∈ P no is rejected with probability 1.

If P is a Las Vegas probabilistic finite automaton, we say that P solves P with a success probability p ∈ (0, 1], if (i) for each w ∈ P yes , P accepts w with probability at least p and never rejects (i.e., the probability of rejection is 0) and (ii) for each w ∈ P no , P rejects w with probability at least p and never accepts. (In both these cases, the remaining probability goes to "don't know" answers.)

Basic Facts on Classical Automata

We continue with some basic facts regarding classical automata. We start with a simple observation: The cardinality of the class of the promise problems defined by 1DFAs is uncountable. This holds even for the class defined by a fixed two-state 1DFA on unary languages. Let U ⊆ 1 * be any language defined over the unary input alphabet. Then, the following unary promise problem P(U) is solvable by a two-state 1DFA:

P yes (U) = {a 2n | n ∈ U} , P no (U) = {a 2n+1 | n ∈ U} .
Clearly, P(U) can be solved by a 1DFA D with only two states, counting the length of the input modulo 2, switching between an accepting state and a rejecting state. Since there is a one-to-one correspondence between {U | U ⊆ 1 * } and {P(U) | U ⊆ 1 * }, the cardinality of the class of the promise problems solvable by D is uncountable. Moreover, if U is an uncomputable language, then both P yes (U) and P no (U) are uncomputable. The interested reader can easily find some other promise problems, solvable by very small 1DFAs, with yes-and no-instances satisfying some special properties (e.g., not context-free but context-sensitive, NP-complete, semi-decidable, and so on). One trivial construction for a binary language L ⊆ {0, 1} * is to define the promise problem as

P(L) = ({0w | w ∈ L}, {1w | w ∈ L}).
(A promise problem solvable by 1DFAs whose yes-and no-instances are not regular was previously given in [START_REF] Gruska | Potential of quantum finite automata with exact acceptance[END_REF].) Despite of the above facts, all trade-offs established between various models of automata stay valid also for promise problems.

First, let us show that the classes of promise problems solvable by deterministic, nondeterministic, alternating, and Las Vegas probabilistic finite automata are identical. Theorem 3.1 If a promise problem P = (P yes , P no ) can be solved by a 2AFA A with n states, it can also be solved by a 1DFA D with t(n) ≤ 2 n•2 n states.

Proof: Let R denote the regular language recognized by A. (That is, even though we are given a 2AFA A for solving a promise problem P, such machine is still associated with some classical regular language L(A) = R.) The complement of this language will be denoted by R. Since the problem P is solvable by A, we have that P yes ⊆ R and P no ⊆ R. Now, by [START_REF] Ladner | Alternating pushdown and stack automata[END_REF], each 2AFA A with n states can be transformed into an equivalent 1DFA D with t

(n) ≤ 2 n•2 n
states. This gives that P yes ⊆ R = L(D) and P no ⊆ R = L(D), that is, D accepts each w ∈ P yes and rejects each w ∈ P no . Therefore, D can be used for solving P.

2

The proof of the above theorem can be easily updated for other classical models of automata -using the corresponding trade-off t(n) for the conversion known from the literature -by which we obtain the following corollary.

Corollary 3.2 Any trade-off t(n) in the number of states for language recognition, between any two of deterministic, nondeterministic, or alternating automata models, is also a valid trade-off for promise problems.

Next, we show that neither Las Vegas PFAs gain any computational power. Theorem 3.3 If a promise problem P = (P yes , P no ) can be solved by a Las Vegas 2PFA P with n states and any success probability p > 0, it can also be solved by a 1DFA D with t(n) ≤ 2 n 2 +n states.

Proof: First, for each w ∈ P yes , the machine P has at least one accepting computation path and no rejecting path. Conversely, for each w ∈ P no , the machine has at least one rejecting path and no accepting path. In both cases, the paths that are not successful return a "don't know" answer.

Therefore, by removing the probabilities and converting neutral "don't know" states into rejecting states, we obtain an n-state 2NFA N recognizing a regular language R such that P yes ⊆ R and P no ∩ R = ∅. Therefore, P no ⊆ R. Now, by [START_REF] Kapoutsis | Removing bidirectionality from nondeterministic finite automata[END_REF], the 2NFA N can be converted to an equivalent 1DFA D with the number of states bounded by t

(n) ≤ n-1 i=0 n-1 j=0 ( n i )( n j )(2 i -1) j ≤ 2 n 2 +n , which gives P yes ⊆ R = L(D) and P no ⊆ R = L(D).
That is, D accepts each w ∈ P yes and rejects each w ∈ P no , and hence it can be used for solving P. 2

A similar idea can be used for Las Vegas 1 ε PFAs:

Corollary 3.4 If a promise problem P = (P yes , P no ) can be solved by a Las Vegas 1 ε PFA P with n states and any success probability p > 0, it can also be solved by a 1DFA D with t(n) ≤ 1+3 (n-1)/3 ≤ 2 0.529•n states.

Proof: By removing the probabilities, we first obtain an n-state 1 ε SVFA N recognizing a regular language R such that P yes ⊆ R and P no ⊆ R. Then, after elimination of ε-transitions by the method described in [29, Sect. 2.11] (still not increasing the number of states), we have a 1SVFA that can be converted to an equivalent 1DFA D with t(n) ≤ 1 + 3 (n-1)/3 states [START_REF] Jirásková | Optimal simulation of self-verifying automata by deterministic automata[END_REF]. The resulting 1DFA is then used for solving P. 2

In Section 5, we show that the corresponding lower bound is also exponential.

A Classically Expensive Unary Promise Problem

Recently, Ambainis and Yakaryılmaz [START_REF] Ambainis | Superiority of exact quantum automata for promise problems[END_REF] presented a family of promise problems EvenOdd(k), for k ∈ N + , where

EvenOdd yes (k) = {a m•2 k | m is even} , EvenOdd no (k) = {a m•2 k | m is odd} ,
such that, for each k, the promise problem EvenOdd(k) can be solved exactly by only a two-state realtime quantum finite automaton. On the other hand, for 1DFAs, 2 k+1 states are necessary and also sufficient. Later, it was shown that 2 k+1 states are also necessary in any bounded-error 1PFA [START_REF] Rashid | Implications of quantum automata for contextuality[END_REF] and that 2DFAs must use at least 2 k+1 -1 states [START_REF] Maria | Complexity of promise problems on classical and quantum automata[END_REF]. (vi) Here we show that even two-way nondeterminism does not help us to save a single state for this promise problem; and hence 2 k+1 states is the exact value for one-way/two-way deterministic/nondeterministic automata. After that, we show that alternation does help to reduce the number of states to Θ(k), already by the use of one-way ε-free machines. More precisely, EvenOdd(k) can be solved by a 1AFA with 11k-14 states (for k ≥ 3); the corresponding lower bound for 1AFAs is k +1. For two-way machines, 2AFAs, the exact lower bound is an open problem, but we know that it must grow in k, which is an easy consequence of Theorems 3.1 and 4.1. Similarly, we do not know whether bounded-error 2PFAs can work with fewer than 2 k+1 states.

The method used for proving the lower bound in the following theorem is not new -inspired by [START_REF] Stearns | Hierarchies of memory limited computations[END_REF][START_REF] Chang | Space bounded computations: Review and new separation results[END_REF][START_REF] Geffert | Nondeterministic computations in sublogarithmic space and space constructibility[END_REF] -but it needs some modifications on promise problems. Proof: Suppose, for contradiction, that the promise problem can be solved by a 2NFA N with S < 2 k+1 states.

Consider now the input a 2 k+1 . Clearly, it must be accepted by N , and hence there must exist at least one accepting computation path, so we can fix one such path. (Besides, being nondeterministic, N can have also other paths, not all of them necessarily accepting, but we do not care for them.) Along this fixed path, take the sequence of states q 0 , p 1 , q 1 , p 2 , q 2 , p 3 , q 3 , . . . , p r , q r , p r+1 , where q 0 is the initial state, p r+1 is an accepting state, and all the other states {p i ∪ q i | 1 ≤ i ≤ r} are at the left/right endmarkers of the input 2 k+1 , such that:

• If p i is at the left (resp., right) endmarker, then q i is at the opposite endmarker, and the path from p i to q i traverses the entire input from left to right (resp., right to left), not visiting any of endmarkers in the meantime.

• The path between q i and p i+1 starts and ends at the same endmarker, possibly visiting this endmarker several times, but not visiting the opposite endmarker. Such a path is called a "U-turn". This covers also the case of q i = p i+1 with zero number of executed steps in between.

(vi) Recently [START_REF] Ablayev | Very narrow quantum OBDDs and width hierarchies for classical OBDDs[END_REF], it was also shown that the width of any nondeterministic or bounded-error stable OBBD cannot be smaller than 2 k+1 , for a functional version of EvenOdd(k).

Now, the path connecting p i with q i must visit all input tape positions in the middle of the input a 2 k+1 , and hence N must enter 2 k+1 states, at least one state per each input tape position. However, since S < 2 k+1 , some state r i must be repeated. That is, between p i and q i , there must exist a loop, starting and ending in the same state r i , traveling some i positions to the right, not visiting any of the endmarkers. For each traversal, we fix one such loop (even though the path from p i to q i may contain many such loops). Note that the argument for traveling across the input from right to left is symmetrical. Since this loop is in the middle of the traversal, we have that i < 2 k+1 . But then i can be expressed in the form

i = γ i •2 αi ,
where γ i > 0 is odd (not excluding γ i = 1) and α i ∈ {0, 1, . . . , k}. Note that if α i ≥ k +1, we would have a contradiction with i < 2 k+1 . Now, consider the value = lcm{ 1 , 2 , . . . , r } , the least common multiple of all fixed loops, for all traversals of the input a 2 k+1 . Clearly, can also be expressed in the form

= γ •2 α ,
where γ > 0 is odd and α ∈ {0, 1, . . . , k} (actually, γ = lcm{γ 1 , . . . , γ r } and α = max{α 1 , . . . , α r }).

We shall now show that the machine N must also accept the input

a 2 k+1 + •2 k-α .
First, if q i and p i+1 are connected by a U-turn path on the input a 2 k+1 , they will be connected also on the input a 2 k+1 + •2 k-α since such path does not visit the opposite endmarker and 2 k+1 + • 2 k-α ≥ 2 k+1 . Second, if p i and q i are connected by a left-to-right traversal along a 2 k+1 , they will stay connected also along the input a

2 k+1 + •2 k-α
. This only requires to repeat the loop of the length i beginning and ending in the state r i . Namely, we can make i • 2 k-α more iterations. Note that = lcm{ 1 , . . . , r } and hence is divisible by i , for each i = 1, . . . , r, and that α ≤ k, which gives that i • 2 k-α is an integer. Note also that these i •2 k-α additional iterations of the loop of the length i travel exactly ( i •2 k-α )× i = •2 k-α additional positions to the right. Thus, if N has an accepting path for a 2 k+1

, it must also have an accepting path for a 2 k+1 + •2 k-α (just by a straightforward induction on r). Therefore, N accepts a 2 k+1 + •2 k-α . (Actually, N can have many other paths for this longer input, but they cannot rule out the accepting decision of the path constructed above.)

However, the input a

2 k+1 + •2 k-α should be rejected, since 2 k+1 + •2 k-α = 2 k+1 + γ •2 α •2 k-α = (2+γ) • 2 k ,
where γ is odd. This is a contradiction. So, N must have at least 2 k+1 states.

2

The above argument cannot be extended to alternating automata: using "cooperation" of several computation paths running in parallel, the number of states can be reduced from 2 k+1 to O(k), even by the use of one-way ε-free machines. We first present a conceptually simpler realtime version. Lemma 4.2 For each k ∈ N + , the language EvenOdd yes (k) can be recognized -and hence the promise problem EvenOdd(k) can be solved -by an rtAFA A with 7k+2 states.

Proof: Recall that EvenOdd yes (k) = {a m•2 k | m is even}, and hence the unary input string a n is in this language if and only if n is an integer multiple of 2 k+1 . In turn, this holds if and only

if b n,k = b n,k-1 = • • • = b n,0 = 0,
where b n,i denotes the i th bit in the binary representation of the number n. (The bit positions are enumerated from right to left, beginning with zero for the least significant bit.) That is, written in binary, n should be of the form γ0 k+1 , for some γ ∈ {0, 1} * .

Based on this, the rtAFA A counts the length of the input modulo 2 k+1 and verifies, for the binary representation of this length, that the last k + 1 bits are all equal to zero. The important detail is that A counts down, starting from zero. That is, along the input, the value of the counter changes as follows:

:= 0, 2 k+1 -1, 2 k+1 -2, . . . , 2, 1, 0, 2 k+1 -1, . . .
Thus, the counter is interpreted as the number of input symbols not processed yet (and taken modulo 2 k+1 ). The machine A accepts if and only if this value is zero when it halts at the end of the input.

Implemented deterministically, this counting requires 2 k+1 states. However, an alternating automaton can use several processes running in parallel. (See [START_REF] Reinhardt | The minimum amount of useful space: New results and new directions[END_REF][START_REF] Bednárová | New results on the minimum amount of useful space[END_REF] for a similar idea.) Each parallel process will keep only one bit of the current value of . That is, for i ∈ {k, k -1, . . . , 0}, we shall use the states "i 0 " and "i 1 " to indicate that i th bit in the current value of is cleared to zero or set to one, respectively. This will hold for each "proper" sequence of existential guesses along each input. The correctness of this guessing will be verified when A halts at the end of the input. (Actually, the alternating tree of computation paths will be highly redundant; the same bit will be remembered by a huge number of activated identical copies of i 0 or i 1 , running in parallel.) Clearly, for each symbol a along the input, we need to decrement the counter by one and hence to update properly the corresponding bits. This is implemented by the use of some additional auxiliary states.

We are now ready to present the set of states for the rtAFA A, together with their brief description: i x , for i = k, . . . , 0 and x ∈ {0, 1}: the i th bit of is x (b ,i = x), i x,∀ 1 , for i = k, . . . , 1 and x ∈ {0, 1}: the i th bit of is x and, moreover, all bits to the right are set to 1 (b ,i = x and b ,j = 1 for each j < i), i x,∃ 0 , for i = k, . . . , 1 and x ∈ {0, 1}: the i th bit of is x and, moreover, at least one bit to the right is set to 0 (b ,i = x and b ,j = 0 for some j < i), i ∃ 0 , for i = k, . . . , 2: the i th bit of may be quite arbitrary, but at least one bit to the right is set to 0 (b ,j = 0 for some j < i), s I : the initial state.

All states of type i 0 , i 1 , i ∃ 0 are existential, whereas those of type i 0,∀ 1 , i 1,∀ 1 , i 0,∃ 0 , i 1,∃ 0 , s I are universal. The states of type i 0 , s I are accepting and none of the remaining states is accepting.

Clearly, the total number of states is 2(k+1) + 2k + 2k + (k-1) + 1 = 7k+2.

Transitions in A are defined as follows:

i x a -→ i x,∃ 0 ∨ i 1-x,∀ 1 , for i = k, .
. . , 1 and x ∈ {0, 1}: The i th bit of is set to x if and only if either (i) the i th bit of = -1 is set to the same value x, provided that at least one bit to the right in is set to zero, that is, b ,j = 0 for some j < i, or (ii) the i th bit of is flipped to the complementary value 1 -x, provided that all bits the right in are set to one, that is, b ,j = 1 for each j < i. Therefore, in the state i x , branching existentially while reading the next input symbol a, A guesses between switching to i x,∃ 0 or to i 1-x,∀ 1 .

0 x a -→ 0 1-x , for x ∈ {0
, 1}, a special case of i x for i = 0: Transitions for the rightmost bit are simplified, since there is no bit position with j < i and hence we do not need to use

0 0,∀ 1 , 0 1,∀ 1 , 0 0,∃ 0 , 0 1,∃ 0 .
Therefore, in 0 x , the machine reads the next input symbol a deterministically, by switching to 0 1-x .

i x,∀ 1 ε -→ i x ∧ (i-1) 1 ∧ • • • ∧ 0 1 , for i = k, .
. . , 1 and x ∈ {0, 1}: In the auxiliary state i x,∀ 1 , the machine A has to verify the bit setting at the corresponding positions in , namely, that b ,i = x and that b ,j = 1 for each j < i. Thus, branching universally with ε-transitions for each bit position j ≤ i, it splits into parallel processes i x , (i-1) 1 , . . . , 0 1 .

i x,∃ 0 ε -→ i x ∧ i ∃ 0 , for i = k, .
. . , 2 and x ∈ {0, 1}: The role of the auxiliary state i x,∃ 0 is similar to that of i x,∀ 1 , verifying the bit setting in . This time we verify that (i) b ,i = x and that (ii) b ,j = 0 for at least one j < i. In order not to mix universal and existential decisions, we delay the condition (ii) until the next computation step, and hence A branches universally in i x,∃ 0 , splitting into two parallel processes i x and i ∃ 0 , by the use of ε-transitions.

1 x,∃ 0 ε -→ 1 x ∧ 0 0 , for x ∈ {0, 1}, a special case of i x,∃ 0 for i = 1:
Transitions are simplified, since we can work without 1 ∃ 0 . Therefore, in 1 x,∃ 0 , the machine splits universally into 1 x and 0 0 , using ε-transitions.

i ∃ 0 ε -→ (i-1) 0 ∨ • • • ∨ 0 0 , for i = k, . . . , 2:
In the auxiliary state i ∃ 0 , we verify that b ,j = 0 for at least one j < i. Therefore, branching existentially with ε-transitions, A guesses which bit is set to zero, switching to j 0 , for some j < i.

s I a -→ k 1,∀ 1 : At the very beginning, = n. Therefore, for each accepted input a n , the initial value of must be an integer multiple of 2 k+1 , with the last k+1 bits all equal to zero. Thus, after reading the first input symbol a, we should get = -1 in which all these bits are set to one. For this reason, in the initial state, the machine reads the first input symbol a by switching deterministically to k 1,∀ 1 .

It is easy to see from the above transitions that A is a realtime machine: After reading an input symbol, a computation path can pass through at most two ε-transitions in a row, after which it gets to a state i x , for some i = k, . . . , 0 and some x ∈ {0, 1}. In i x , the machine waits for a next input symbol.

To show that A indeed recognizes EvenOdd yes (k), we need to prove the following claim.

Claim. For each ≥ 0, each i = k, . . . , 0, and each x ∈ {0, 1}, the rtAFA A has an accepting alternating subtree of computation paths rooted in the state i x at the input position (measured from the end of the input) if and only if the i th bit of is equal to x.

The claim is proved by induction on = 0, 1, 2, . . .

First, let = 0, that is, A has already processed all input symbols. Clearly, all bits of are equal to zero, i.e., b ,i = 0 for each i. Now, since there are no more input symbols to be processed and there are no ε-transitions starting in the state i x , the machine A must halt in i x . Therefore, A has an accepting alternating subtree rooted in i x at the end of the input if and only if i x is an accepting state. By definition of accepting states in A (the states of type i 0 are accepting but those of type i 1 are not), this holds if and only if x = 0, which in turn holds if and only if x = 0 = b ,i , the i th bit of .

Second, by induction, assume that the claim holds for = -1. Now, by definition of the transitions in the state i x for i > 0, taking into account subsequent ε-transitions passing through auxiliary states, it can be seen (vii) that A has an accepting alternating subtree of computation paths rooted in the state i x at the input position if and only if either (i) A has an accepting alternating subtree rooted in the state i x at the input position = -1 and, moreover, the same holds for at least one subtree rooted in a state j 0 at the position , for some j < i, or (ii) A has an accepting alternating subtree rooted in i 1-x at the input position and, moreover, the same holds for all subtrees rooted in j 1 at the position , for each j < i. However, by induction, using = -1, this statement holds if and only if either (i) b ,i = x and, moreover, b ,j = 0, for some j < i, or (ii) b ,i = 1-x and, moreover, b ,j = 1, for each j < i. Using = +1, it is easy to see that this holds if and only if b ,i = x. This completes the proof of the claim. Now, recall that the machine A reads the first input symbol a by switching deterministically from the initial state to the state k 1,∀ 1 . After that, branching universally with ε-transitions for each bit position j ≤ k, the computation splits into parallel processes k 1 , (k -1) 1 , . . . , 0 1 . Thus, using the above claim, A accepts a n with n > 0 if and only if, in = n-1, the last k +1 bits are all equal to 1. Clearly, this holds if and only if the last k+1 bits in n are all equal to 0, that is, if and only if n is and integer multiple of 2 k+1 . This gives that the language recognized by A agrees with EvenOdd yes (k) on all inputs of length n > 0.

For the special case of n = 0, we have that a 0 = a 0•2 k ∈ EvenOdd yes (k), since m = 0 is even. However, a 0 = ε is accepted by A due to the fact that the initial state s I is also an accepting state, which completes the argument.

2

By increasing slightly the number of states, we can replace the realtime alternating machine from the above lemma by a one-way AFA not using any ε-transitions: Theorem 4.3 For each k ≥ 3, the language EvenOdd yes (k) can be recognized -and hence the promise problem EvenOdd(k) can be solved -by a 1AFA A with 11k-14 states.

Proof: By inspection of the rtAFA A constructed in Lemma 4.2, it can be seen that A can read an input symbol only by transitions starting in the states of type i x , s I . After reading, the computation path can pass through at most two subsequent ε-transitions until it gets to a state of type i x , ready to read from the input again.

First, as an intermediate product, we replace A by an equivalent machine A in which reading an input symbol is always followed by exactly three subsequent ε-transitions, along each computation path. This only requires to delay artificially the moment when the automaton gets to a state of type i x by the use of some additional states, namely, the following additional states:

(vii) With obvious modifications, the argument presented here can be easily extended also for the case of i = 0 (the rightmost bit), which we leave to the reader. i x , i x , for i = k, . . . , 0 and x ∈ {0, 1}: delay switching to the state i x by one or two steps, respectivelyimplemented by transitions i x ε

-→ i x ε -→ i x , 0
x , for x ∈ {0, 1}: delay switching to the state 0 x by three steps -implemented by 0 x ε -→ 0 x .

Taking also into account the states used by the original machine A, the total number of states increases to (7k+2) + 4(k+1) + 2 = 11k+8. Transitions for the "original" states (cf. construction in Lemma 4.2) are modified as follows:

i x a -→ i x,∃ 0 ∨ i 1-x,∀ 1 , for i = k, . . . , 1 and x ∈ {0, 1} (not modified), 0 x a -→ 0 1-x , for x ∈ {0, 1}, i x,∀ 1 ε -→ i x ∧ (i-1) 1 ∧ • • • ∧ 0 1 , for i = k, . . . , 1 and x ∈ {0, 1}, i x,∃ 0 ε -→ i x ∧ i ∃ 0 , for i = k, . . . , 2 and x ∈ {0, 1}, 1 x,∃ 0 ε -→ 1 x ∧ 0 0 , for x ∈ {0, 1}, i ∃ 0 ε -→ (i-1) 0 ∨ • • • ∨ 0 0 , for i = k, . . . , 2, s I a -→ k 1,∀ 1 (not modified).
Since A and A share the same set of accepting states, it should be obvious that they recognize the same language.

Second, replace all ε-transitions in A by transitions reading the input symbol a. That is, each transition of type s 1 ε -→ s 2 is replaced by s 1 a -→ s 2 ; the transitions already reading input symbols do not change; nor does the set of accepting states. This way we obtain a one-way AFA A without any ε-transitions such that, for each n ≥ 0, it accepts the input a 4n if and only if A accepts a n , i.e., if and only if a n ∈ EvenOdd yes (k). The new machine A does not accept any input the length of which is not an integer multiple of 4.

Therefore, with 11k+8 states, A recognizes the language

{(a 4 ) m•2 k | m is even} = {a m•2 k+2 | m is even} = EvenOdd yes (k+2) .
Using the substitution k = k+2, we thus get that EvenOdd yes (k ) can be recognized by a one-way ε-free AFA A with 11(k -2) + 8 = 11k -14 states, for each k ≥ 3. 2

To show that the gap exhibited by Theorems 4.1 and 4.3 is tight, we need an upper bound for converting alternation into determinism on unary promise problems: Lemma 4.4 If a promise problem P = (P yes , P no ) built over a unary input alphabet can be solved by a 1AFA with n states, it can also be solved by a 1DFA with t(n) ≤ 2 n states.

Proof: As pointed out in [START_REF] Mereghetti | Optimal simulations between unary automata[END_REF]Sect. 5], each 1AFA A with n states recognizing a unary language U can be replaced by an equivalent 1DFA D with 2 n states. This is a simple consequence of the fact that A can be replaced by a 1DFA D with 2 n states recognizing U R , the reversal of the original language [6]. (Actually, the construction in [6] works for Boolean automata -see Footnote (iv) -which covers, as a special case, the classical alternating automata as well.) However, for unary languages, we have U R = U.

Then, by the same reasoning as used in the proof of Theorem 3.1, this trade-off easily extends to unary promise problems.

2

By the above lemma, the lower bound for solving EvenOdd(k) by 1AFAs is k +1 states, since a 1AFA with less than k+1 states would give us a 1DFA with less than 2 k+1 states for this promise problem, which contradicts Theorem 4.1.

By combining Theorems 4.1 and 4.3 with Lemma 4.4, we thus get:

Corollary 4.5
The tight gap of succinctness between two-way NFAs and one-way ε-free AFAs is asymptotically exponential on promise problems, even for a unary input alphabet.

Las Vegas Probabilistic Finite Automata

In the case of language recognition, the gap of succinctness between Las Vegas realtime PFAs and oneway DFAs can be at most quadratic and this gap is tight [START_REF] Ďuriš | Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations[END_REF][START_REF] Hromkovič | On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata[END_REF]. Quite surprisingly, despite of this fact and despite of the fact that the existing gaps for language recognition are not be violated on promise problems by classical models of automata (cf. Corollary 3.2), we shall show here that this does not hold for the case of one-way Las Vegas probabilistic versus one-way deterministic automata; by switching from language recognition to promise problems, the quadratic gap increases to a tight exponential gap.

For this purpose, we introduce a family of promise problems solvable by Las Vegas 1PFAs with a linear number of states and success probability arbitrarily close to 1, but for which any 1DFAs require an exponential number of states. (viii) Consider a family of promise problems TRIOS(n, r), for n, r ∈ N + , such that

TRIOS yes (n, r) = { #x 1 x 1 y 1 #x 2 x 2 y 2 • • • #x r x r y r | x 1 , y 1 , . . . , x r , y r ∈ {0, 1} n , ∀i ∈ {1, .
. . , r} ∃j ∈ {1, . . . , n} : x i,j < y i,j } ,

TRIOS no (n, r) = { #x 1 y 1 x 1 #x 2 y 2 x 2 • • • #x r y r x r | x 1
, y 1 , . . . , x r , y r ∈ {0, 1} n , ∀i ∈ {1, . . . , r} ∃j ∈ {1, . . . , n} : x i,j > y i,j } , where x i,j , y i,j ∈ {0, 1} denote the j th bit in the respective strings x i , y i ∈ {0, 1} n .

Theorem 5.1 For each n, r ∈ N + , the promise problem TRIOS(n, r) can be solved by a Las Vegas 1PFA P with 4n+3 states and success probability 1 -( n-1 n ) r .

Proof: The automaton P uses the following state set:

Q = {q I , q A , q R } ∪ {s i | i ∈ {1, . . . , n}} ∪ {t i,0 | i ∈ {1, . . . , 2n}} ∪ {t i,1 | i ∈ {1, . . . , n}} ,
where q I is the initial and also the "don't know" state, while q A , q R are the accepting and rejecting states, respectively.

(viii) Remark that, in [START_REF] Geffert | Classical automata on promise problems[END_REF], we argued the same exponential separation by using some other families of promise problems, but it appeared that some of these families can also be solved by 1DFAs with a linear number of states, and hence they cannot be used as witness families for proving such separation. More precisely, a single sentence statement given just before Corollary 4 in [START_REF] Geffert | Classical automata on promise problems[END_REF] is not correct.

Recall that we do not have to worry about the outcome of the computation if the input is not of the form (#{0, 1} 3n ) r . Now, let #x i u i v i , with x i , u i , v i ∈ {0, 1} n , denote the i th input segment. Typically, for i > 1, the processing of the i th segment is activated already somewhere in the middle of the previous segment, by switching to the initial state q I . For i = 1, the machine begins with the first symbol #. For these reasons, in the state q I , the machine ignores all symbols along the input until it reads the separator #, when it enters the state s 1 . This is implemented by transitions q I b -→ q I , for each b ∈ {0, 1}, together with q I # -→ s 1 . (Unless otherwise stated explicitly, all transitions throughout this proof are "deterministic", i.e., with probability 1.)

Next, starting in the state s 1 , the automaton P moves along the string x i and chooses, with equal probability 1 n , one of the symbols x i,1 , . . . , x i,n ∈ {0, 1} for subsequent verification. This is implemented as follows. If P is in the state s j , for j ∈ {1, . . . , n}, and the next input symbol is b ∈ {0, 1}, then P reads this symbol by switching to the state t 1,b with probability p j =

1 p 1 •••p j-1 • 1
n and to the state s j+1 with probability p j = 1 -p j . (As usual in mathematical notation, we take p 1 • • • p j-1 = 1 for j = 1.) The reader may easily verify that the sequence of probabilities p 1 , . . . , p n ends with p n = 1, which gives p n = 0, and hence there is no need to introduce a state s n+1 . It is also easy to see that P gets from the state s 1 at the beginning of x i = x i,1 • • • x i,n to the state t 1,xi,j positioned just behind the symbol x i,j with probability 1 n . The next phase depends on whether P is in the state t 1,0 or in t 1,1 , that is, on whether the chosen bit x i,j is equal to 0 or to 1.

For the case of x i,j = 0, the routine starting in the state t 1,0 is responsible to verify that v i,j = 1, which corresponds to the case of #x i u i v i = #x i x i y i , with x i,j < y i,j . Since P gets to t 1,0 just after reading the symbol x i,j , this only requires to examine the bit that is placed exactly 2n positions to the right. This is implemented by transitions t j,0 b -→ t j+1,0 , for each j ∈ {1, . . . , 2n-1} and each b ∈ {0, 1}. Finally, if v i,j = 1, then P accepts, using t 2n,0 1 -→ q A . Otherwise, P switches back to the initial state, by t 2n,0 0 -→ q I . In the accepting state q A , the machine just consumes the remaining part of the input, using q A a -→ q A , for each a ∈ {0, 1, #}. Conversely, in the initial state q I , the machine proceeds to examine the next input segment #x i+1 u i+1 v i+1 , by transitions already described above. However, if P switches to q I while processing the last input segment (for i = r), it halts in q I at the end of the input. This is interpreted as a "don't know" answer.

The case of x i,j = 1 is very similar. This time the routine starting in the state t 1,1 verifies that u i,j = 0, which corresponds to the case of #x i u i v i = #x i y i x i , with x i,j > y i,j . This only requires to examine the bit placed exactly n positions to the right of the symbol x i,j . This is implemented by transitions t j,1 b -→ t j+1,1 , for each j ∈ {1, . . . , n-1} and each b ∈ {0, 1}. After that, if u i,j = 0, then P rejects, using t n,1 0 -→ q R . Otherwise, P switches back to the initial state, by t n,1 1 -→ q I . In the rejecting state q R , the machine consumes the rest of the input, using q R a -→ q R , for each a ∈ {0, 1, #}. Conversely, in the initial state q I , the machine proceeds in the same way as in the case of x i,j = 0; either it proceeds to the next input segment, or else it halts in q I at the end of the input, giving a "don't know" answer. Summing up, if the i th segment is of the form #x i u i v i = #x i x i y i , with x i,j < y i,j for some j ∈ {1, . . . , n}, then P, starting to process this segment in the state q I , accepts the entire input with probability at least 1 n (the exact value increases in the number of bit pairs satisfying x i,j < y i,j ) and proceeds to the next segment in the state q I with probability at most 1-1 n . (The machine never rejects on such segment, since u i = x i and there are no bit pairs satisfying x i,j > u i,j .) Clearly, also here the computation starts in the state q 1 = s I . Now, using the fact that δ(q, #u q ) = δ(q, #v q ) for each state q ∈ S, we have that q i+1 can also be expressed as

q i+1 = δ(q i , #u qi u qi v qi ) = δ(δ(q i , #u qi ), u qi v qi ) = δ(δ(q i , #v qi ), u qi v qi ) = δ(q i , #v qi u qi v qi ) ,
for each i = 1, . . . , r. Therefore, along the input w R , D passes the segment boundaries by the same sequence of states q 1 , q 2 , . . . , q r , q r+1 , halting in q r+1 . But then, since q r+1 is an accepting state, D accepts w R . However, w R ∈ TRIOS no (n, r), since, for each segment #v qi u qi v qi , we have a bit position j ∈ {1, . . . , n} satisfying v q,j > u q,j .

Thus, each 1DFA D with less than 2 n states accepts an input that should be rejected, a contradiction. 2

As a consequence of the above theorem, we get the asymptotically optimal exponential size Θ(2 n ) for 1DFAs solving TRIOS(n, r); the construction of a 1DFA with O(2 n ) states is quite straightforward.

On the other hand, Theorem 5.1 guarantees 4n+3 states for Las Vegas 1PFAs solving TRIOS(n, r), and hence we have an exponential lower bound for the gap between these two models of automata. Finally, by Corollary 3.4, we have an exponential upper bound, which gives:

Corollary 5.3
The tight gap of succinctness between one-way DFAs and Las Vegas one-way ε-free PFAs is asymptotically exponential on promise problems.

Due to Theorem 5.1, we know that TRIOS(n, n 2 ) can be solved by a Las Vegas 1PFA with 4n+3 states and success probability σ

(n) ≥ 1 -(1-1 n ) n 2 . Thus, using the fact [23, Lm. A.3.60+] that (1-1 x ) x < 1 e
for each real x > 1, the probability of a "don't know" outcome is at most

1-σ(n) ≤ 1-1 n n•n < 1 e n = 1 e n .
This Las Vegas 1PFA can be converted to an equivalent restarting one-way PFA, executing the procedure in an infinite loop, by restarting the entire computation when the original machine halts in the "don't know" state at the end of the input. (This can be easily achieved by using a single additional state.) Therefore, we can obtain a restarting 1PFA with 4n+4 states, solving TRIOS(n, n 2 ) exactly. The expected number of the input tape sweeps can be bounded by

(n) = ∞ i=1 i•σ(n)•(1-σ(n)) i-1 ≤ ∞ i=1 i•1• 1 e n i-1 = 1 1-1 e n 2 = 1+ 1 e n -1 2 ≤ 1+o(1) .
Thus, for the input of length |w|, the expected running time is (1+o(1))•|w|.

Finally, the family of promise problems TRIOS(n, r), for n, r ∈ N + , does not give corresponding separations for two-way machines, since already 2DFAs can solve TRIOS(n, r) with O(n) states, for each r. This is done as follows. Let #x i u i v i , with x i , u i , v i ∈ {0, 1} n , denote the i th segment along the input. Processing of this segment begins with positioning the input head at the n th bit of u i , by moving 2n positions to the right from the symbol #. Then, for j = n, . . . , 1 (in that order), the machine verifies that u i,j = x i,j . (To move from the j th bit of u i to the j th bit of x i , just travel exactly n positions to the left; to move from the j th bit of x i to the (j -1) st bit of u i , just travel exactly n-1 positions to the right. The machine detects that it has tested all n bits from the fact that, after traveling exactly n positions to the left for the j th bit of x i , it finds the symbol # at this position, instead of zero or one.) In a similar way, the machine can also search for a bit position j satisfying u i,j < v i,j , this time iterating in ascending order, for j = 1, . . . , n. If the i th input segment passes the test successfully, the machine proceeds to examine the next segment #x i+1 u i+1 v i+1 or, for i = r, it accepts.

6 Two-Sided Bounded-Error Probabilistic Finite Automata

In Section 3, we have shown the limitations of Las Vegas PFAs. One-sided error (ix) PFAs have similar limitations since they can be simulated by nondeterministic or universal finite automata by removing the probabilities: If a promise problem P = (P yes , P no ) can be solved by a PFA rejecting each w ∈ P no with probability 1 (only members of P yes are accepted), then we obtain an NFA from the one-sided error PFA. Conversely, if each w ∈ P yes is accepted with probability 1 (only members of P no are rejected), then we obtain a finite automaton making only universal decisions (or an NFA for P no ) from the one-sided error PFA. In this section, we show that we have a different picture for PFAs with two-sided bounded-error.

First, we show that bounded-error 1PFAs can be very succinct compared to Las Vegas 2PFAs, 2AFAs, or any other simpler machines. In fact, we present a parallel result to that of Ambainis and Yakaryılmaz [START_REF] Ambainis | Superiority of exact quantum automata for promise problems[END_REF] but with bounded error instead of exact acceptance.

To this aim, consider U p , a 1PFA with the unary input alphabet Σ = {a} and two states. Namely, let s I be the initial and also the only accepting state, and s R be the rejecting state. In the state s I , the machine reads the symbol a staying in s I with probability p and switching to s R with the remaining probability p = 1-p. In s R , the machine just consumes the remaining part of the input, executing a single-state loop. Now, let UP(p) be a promise problem such that

UP yes (p) = {a j | f Up (a j ) ≥ 3 4 } , UP no (p) = {a j | f Up (a j ) ≤ 1 4 } .
Clearly, for each p ∈ (0, 1), the promise problem UP(p) can be solved by a bounded-error one-way ε-free PFA with only two states, namely, by U p . On the other hand, it is easy to show that the number of states required by any 2AFA for solving UP(p) (which covers all simpler models of automata as well) increases when p approaches 1: Since it is straightforward that the string a j is accepted by U p with probability p j for each j ≥ 0, we get a j ∈ UP yes (p) only for finitely many values satisfying j ≤ log p 3 4 , whereas UP no (p) contains infinitely many strings satisfying j ≥ log p Note also that A p → +∞ as p → 1. Theorem 6.1 For one-way/two-way deterministic/nondeterministic finite automata, and each p ∈ (0, 1), the number of states that is sufficient and necessary for solving the promise problem UP(p) is exactly A p +1.

Proof: First, we can easily design a 1DFA D (hence, any more powerful model as well) solving U p with A p +1 states. After the initial chain of A p +1 accepting states, responsible to accept a j for j ∈ {0, . . . , A p }, the automaton enters a rejecting state s R , in which it executes a single-step loop, consuming the rest of the input. By allowing undefined transitions in D, the state s R can be eliminated.

Second, before providing the matching lower bound, we need to present the so-called "n → n + n!" method [START_REF] Stearns | Hierarchies of memory limited computations[END_REF][START_REF] Chang | Space bounded computations: Review and new separation results[END_REF][START_REF] Geffert | Nondeterministic computations in sublogarithmic space and space constructibility[END_REF] (cf. also the proof of Theorem 4.1). To make the paper self-contained, we include also a proof, for a simplified version of this method that is sufficient for our purposes.

Claim. Let N be a 2NFA (or any less powerful model) with n states and let a m be a unary string, with m ≥ n. Then, if N has a computation path traversing across a m from left to right, starting in some state q 1 and ending in some q 2 , it has also a computation path traversing across a m+h•m! , for each h ≥ 1, starting and ending in the same states q 1 and q 2 .

The proof is based on the fact that N uses only n states, but the sequence of states along the left-to-right traversal across a m is of length m+1 > n (including q 1 at the beginning and q 2 at the end). Thus, in the course of this traversal, some state must be repeated. Hence, N executes a loop, by which it travels some ≤ m positions to the right. Note that m!/ is a positive integer. Hence, for each h ≥ 1, by using h•m!/ additional iterations of this loop traveling positions, the machine traverses the string a m+h•m! , starting and ending in the same states q 1 and q 2 . This completes the proof of the claim. Now, let N be a 2NFA (or any less powerful model) solving UP(p) with at most A p states. Consider the inputs a m and a m+h•m! , for m = A p and arbitrary h ≥ 1. Clearly, a m = a Ap ∈ UP yes (p), and hence N has at least one accepting computation path for this input.

However, by the above claim, whenever this computation path traverses from the left endmarker of a m to the opposite endmarker, starting in some state q 1 and ending in some q 2 , an updated version of this path can traverse across a m+h•m! starting and ending in the same states q 1 and q 2 . By symmetry, the same holds for right-to-left traversals. Moreover, a U-turn starting and ending at the same endmarker of a m can obviously do the same on the input a m+h•m! . Thus, for each h ≥ 1, N has a computation path accepting a m+h•m! . But then N accepts infinitely many inputs, which contradicts the fact that all inputs longer than R p belong to UP no (p) and should be rejected. Thus, N must use at least A p +1 states.

2

A lower bound for 2AFAs solving the promise problem UP(p) can be obtained by combining Corollary 3.2, Theorem 6.1, and the result of Geffert and Okhotin [START_REF] Geffert | Transforming two-way alternating finite automata to oneway nondeterministic automata[END_REF], stating that an arbitrary n-state 2AFA can be converted into an equivalent 1NFA with 2 O(n•log n) states. From this one can derive that the number of states in any 2AFA solving UP(p) is at least Ω( log Ap log log Ap ). Corollary 6.2 There exists {UP(p) | p ∈ (0, 1)}, a family of unary promise problems such that boundederror one-way ε-free PFAs with only two states are sufficient to solve all family, but the number of states required by 2AFAs (or by any simpler machines) to solve this family cannot be bounded by any constant.

The error bound 1 4 in the definition of UP(p) can be replaced with an arbitrarily small error; the same results will follow by the use of the same reasoning.

Next, we present a separation result between bounded-error 1PFAs and 1DFAs (and so 2AFAs, or any other model capable of recognizing only regular languages). For this purpose, we use an idea given by Jibran and Yakaryılmaz [START_REF] Rashid | Implications of quantum automata for contextuality[END_REF]. It is known that 2PFAs can recognize some nonregular languages, e.g., EQ = {a n b n | n ∈ N + } [START_REF] ¸š | Probabilistic two-way machines[END_REF], with bounded error but this requires exponential time [START_REF] Dwork | A time complexity gap for two-way probabilistic finitestate automata[END_REF]. It was also shown that EQ can be recognized by a restarting 1PFA for any error bound [START_REF] Yakaryılmaz | Succinctness of two-way probabilistic and quantum finite automata[END_REF]. If the given string a m b n , where m, n ∈ N + , can be examined exponentially many times, then the algorithm given in [START_REF] Yakaryılmaz | Succinctness of two-way probabilistic and quantum finite automata[END_REF] for EQ can distinguish between the cases of m = n and m = n with high probability. Based on this, we introduce a new family of promise problems ExpEQ(c), for integer c ≥ 3:

ExpEQ yes (c) = {(a m b n ) 3•(2c 2 ) m+n • ln c | m, n ∈ N + , m = n} , ExpEQ no (c) = {(a m b n ) 3•(2c 2 ) m+n • ln c | m, n ∈ N + , m = n} .
By [START_REF] Yakaryılmaz | Succinctness of two-way probabilistic and quantum finite automata[END_REF], for each integer c ≥ 3, there exists a restarting 1PFA P c recognizing EQ such that, in one pass along each given input a m b n , the probability of giving an erroneous decision (rejecting if the input should be accepted or accepting if it should be rejected) is at least c times smaller than the probability of giving a correct decision. From this moment on, one pass of P c along the given input a m b n will be called a "round". To be more exact, let A and R denote, respectively, the probability that P c accepts and rejects the input a m b n in a single round. Then, by [START_REF] Yakaryılmaz | Succinctness of two-way probabilistic and quantum finite automata[END_REF], the following holds:

R ≤ 1 c •A , if m = n , A ≤ 1 c •R , if m = n . (1)
The remaining probability N = 1-A-R represents computations ending with a "don't know yet" result, after which P c restarts another round. In addition, we know from [START_REF] Yakaryılmaz | Succinctness of two-way probabilistic and quantum finite automata[END_REF] that

A = 1 3•(2c 2 ) m+n , independently of whether m = n . (2)
Note also that by combining ( 2) and (1) we get A > 0 for m = n and R > 0 for m = n. Finally, one of nice properties of these restarting 1PFAs is that they all use the same number of states, which is a constant that does not depend on c. (This is achieved by using arbitrarily small transition probabilities.)

Now we are ready to construct a 1PFA P c for solving ExpEQ(c). For the given input (a m b n ) t , where

t = 3•(2c 2 ) m+n • ln c , (3)
P c simulates P c on a m b n but, each time P c restarts its computation from the very beginning of a m b n , the machine P c proceeds to the next copy of a m b n along its own input. More precisely, if P c gives the decision of "acceptance" in the course of one round, P c immediately accepts, by switching to an accepting state s A . Similarly, if P c gives the decision of "rejection", P c immediately rejects, switching to a rejecting s R . (In both these states, P c consumes the rest of the input by executing single-state loops.) Otherwise, P c gets to the end of the current copy of a m b n in a state s N , representing here a "don't know yet" outcome. That is, P c is ready to retry the entire procedure with the next copy of a m b n . Clearly, along the input (a m b n ) t , this can be repeated t times, after which P c halts in the state s N . Since the number of states in P c is a constant not depending on c, it is obvious that P c also uses a constant number of states that does not depend on c. Now, let A t and R t denote the respective probabilities that P c accepts and rejects the input (a m b n ) t , by halting in the respective state s A or s R . The remaining probability N t = 1-A t -R t represents computations not deciding about acceptance or rejection, halting in the state s N .

Let us estimate N t first. By combining R ≥ 0 with (2), (3), and the fact [START_REF] Hromkovič | Design and Analysis of Randomized Algorithms (Introduction to Design Paradigms[END_REF]Lm. A.3.60+] that (1-1

x ) x < 1 e for each real x > 1 (in that order), we get, independently of whether m = n, that Therefore, using (1) and A > 0, we can derive that the input (a m b n ) t satisfying m = n is accepted with probability at least

N t = N t = (1-A-R) t ≤ (1-A) t = 1- 1 3•(2c 2 ) m+n t = 1-
A t = t i=1 A•N i-1 = A• 1-N t 1-N = A A+R •(1-N t ) ≥ A A + A/c •(1-N t ) = c c+1 •(1-N t ) > c c+1 •(1-1 c ) = 1-2 c+1 .
Similarly, using (1) and R > 0, the input (a m b n ) t satisfying m = n is rejected with probability at least

R t = t i=1 R•N i-1 = R• 1-N t 1-N = R A+R •(1-N t ) ≥ R R/c + R •(1-N t ) = c c+1 •(1-N t ) > c c+1 •(1-1 c ) = 1-2 c+1 .
Summing up, the success probability is always above 1 -2 c+1 and consequently the error probability is always below 2 c+1 . (It should be pointed out that the standard PFAs do not use "don't know" states. However, we can declare, by definition, the state s N to be a rejecting state. This may potentially change all "don't know" answers to errors, rejecting inputs that should be accepted. However, this does not change the fact that A t > 1-2 c+1 for m = n, nor does it decrease R t for m = n.) By taking c = max{3, 2 ε -1} for arbitrarily small but fixed ε > 0, we obtain the error probability 2 c+1 ≤ ε, keeping the same constant number of states for each ε. This gives: Theorem 6.3 For each fixed ε > 0, there exists a promise problem solvable by a 1PFA with bounded error ε, using a constant number of states that does not depend on ε, but there is no 1DFA (hence, no other machine capable of recognizing only regular languages) solving the same problem.

Proof: We only need to show that ExpEQ(c) cannot be solved by any 1DFA, for no c ≥ 3. For contradiction, let D be a 1DFA solving ExpEQ(c), for some c ≥ 3. Without loss of generality, we assume that D does not have undefined transitions, and hence it always halts at the end of the input. (Otherwise, we can define all missing transitions by switching to a single new rejecting state, in which D scans the rest of the input.) Let n ≥ 1 denote the number of states in D.

Consider now the unary string a n . Using the Claim presented in the proof of Theorem 6.1, we see that if D traverses across a n , starting in some state q 1 and ending in some q 2 , it will do the same also on the string a n+h•n! , for each h ≥ 1. Clearly, the same holds for traversals of b n and b n+h•n! .

Next, consider the input (a n b n ) t , where t = 3 • (2c 2 ) 2n+2n! • ln c . If, on this input, D halts in a state q , then, by the observation above, D must halt in the same state q also on the inputs (a n+n! b n+n! ) t and (a n b n+2n! ) t . Therefore, D accepts (a n+n! b n+n! ) t if and only if it accepts (a n b n+2n! ) t . But this is a contradiction, since the former string should be accepted by D while the latter should be rejected. Consequently, there is no 1DFA solving ExpEQ(c).

Final Remarks

A thorough study of promise problems can reveal several interesting properties of computational models and give new fundamental insights about them. In automata theory, promise problems have mainly been used to show how quantum models can do much better than the classical ones when compared to the case of language recognition. In this paper, we initiated a systematic work on promise problems for classical one-way finite automata (deterministic, nondeterministic, alternating, and probabilistic). In this context, we have also shown that randomness can do much better than other classical resources.

Promise problems can further be investigated for different computational models and from different perspectives. Two-way finite state machines and counter or pushdown automata models are the first ones coming to the mind. Moreover, we believe that some long-standing open problems, formulated for language recognition, might be solved more easily in the case of promise problems.

Theorem 4 . 1

 41 For each k ∈ N + , any 2NFA for solving the promise problem EvenOdd(k) needs at least 2 k+1 states.

1 4 . 4 and R p = log p 1 4

 444 Let us denote these two critical lengths asA p = log p 3 .

1 3 • 1 e

 31 (2c 2 ) m+n 3•(2c 2 ) m+n • ln c < ln c ≤ 1 c .

(ix) We also cover the case of unbounded-error, i.e., the machines with no bound on the error and so the error can be arbitrarily close to 1 for some inputs.

Acknowledgements

The authors thank Beatrice Palano for providing us a copy of [4].

Supported by the Slovak grant contracts VEGA 1/0142/15 and APVV-0035-10. ‡ Supported by CAPES with grant 88881.030338/2013-01, ERC Advanced Grant MQC, and FP7 FET project QALGO. Moreover, the part of the research work was done while Yakaryılmaz was visiting Kazan Federal University.

subm. to DMTCS

Now, recall that each w ∈ TRIOS yes (n, r) consists of r segments having this form, and hence P gives the "don't know" answer with probability at most (1-1 n ) r for w. Therefore, w is accepted with probability at least 1 -(1-1 n ) r and never rejected. Conversely, if i th segment is of the form #x i u i v i = #x i y i x i , with x i,j > y i,j for some j ∈ {1, . . . , n}, then, in the course of processing this segment, P rejects the entire input with probability at least 1 n and proceeds to the next segment with probability at most 1 -1 n . (Here the machine never accepts, since v i = x i and there are no bit pairs with x i,j < v i,j .)

But then each w ∈ TRIOS no (n, r), consisting of r segments of this form, is rejected with probability at least 1 -(1-1 n ) r and never accepted, by the same reasoning as for TRIOS yes (n, r). 2

It is obvious that, for arbitrarily small fixed constant ε > 0, by taking r = log ε/ log( n-1 n ) , we shall obtain a family of promise problems, namely, TRIOS ε (n), for n ∈ N + , where

, such that the n th member of this family can be solved by a Las Vegas 1PFA with 4n+3 states and success probability at least 1-ε.

On the other hand, for each fixed r ∈ N + , 1DFAs need an exponential number of states for solving TRIOS(n, r). Theorem 5.2 For each n, r ∈ N + , any 1DFA needs at least 2 n states for solving the promise problem TRIOS(n, r).

Proof: For contradiction, suppose that this promise problem can be solved by a 1DFA D using S < 2 n states. Let s I be its initial state, and let δ(q, u) ∈ S denote the state reached by D from the state q ∈ S by reading the string u ∈ Σ * . Clearly, δ(q, uv) = δ(δ(q, u), v), for each state q and each two strings u, v. Now, for each state q ∈ S, consider the enumeration of states δ(q, #u), running over all strings u ∈ {0, 1} n . Since the number of states in S is smaller than the number of strings in {0, 1} n , we have, for each q ∈ S, that there must exist at least two different strings u, v ∈ {0, 1} n with δ(q, #u) = δ(q, #v). Using some lexicographic ordering for {0, 1} n , we can pick u q and v q , the first pair of strings satisfying u q = v q and δ(q, #u q ) = δ(q, #v q ). Moreover, without loss of generality, we can assume that, for some bit position j ∈ {1, . . . , n}, we have u q,j < v q,j . (Here u q,j , v q,j denote the j th bit in the respective strings u q , v q .) Otherwise, by renaming, the roles of u q and v q can be swapped.

Consider now the input

It should be easily seen that, along the input w A , D passes the segment boundaries by the sequence of states q 1 , q 2 , . . . , q r , q r+1 . More precisely, for each i = 1, . . . , r, the machine is in the state q i at the beginning of the i th segment #u qi u qi v qi , halting in the state q r+1 at the end of the last segment. It is also obvious that w A ∈ TRIOS yes (n, r), since, for each segment #u qi u qi v qi , we have a bit position j ∈ {1, . . . , n} satisfying u q,j < v q,j . Therefore, q r+1 is an accepting state.

Next, consider the input