On Delay and Regret Determinization of Max-Plus Automata ∗ Emmanuel Filiot1, Ismaël Jecker1, Nathan Lhote1,2, Guillermo A. Pérez1, and Jean-François Raskin1 1Université Libre de Bruxelles 2Université de Bordeaux, LaBRI {efiliot, ijecker, gperezme, jraskin}@ulb.ac.be, nlhote@labri.fr March 6, 2017 7 1 0 2 Abstract r a Decidabilityofthedeterminizationproblemforweightedautomataoverthesemiring(Z∪{−∞},max,+), M WAforshort,isalong-standingopenquestion. Weproposetwowaysofapproachingitbyconstrain- ingthesearchspaceofdeterministicWA:k-delayandr-regret. AWAN isk-delaydeterminizableif 3 thereexistsadeterministicautomatonD thatdefinesthesamefunctionasN andforallwordsαin thelanguageofN,theacceptingrunofD onαisalways atmost k-awayfrom amaximalaccepting ] L run of N on α. That is, along all prefixes of the same length, the absolute difference between the F running sums of weights of the two runs is at most k. A WA N is r-regret determinizable if for all . wordsαinitslanguage, itsnon-determinismcanberesolvedontheflytoconstructarunofN such s that theabsolute difference between its valueand the valueassigned to αby N is at most r. c [ WeshowthataWAisdeterminizableifandonlyifitisk-delaydeterminizableforsomek. Hence decidingtheexistence of some k is as difficult as thegeneral determinization problem. When k and 2 r are given as input, thek-delay and r-regret determinization problems are shown to be EXPtime- v complete. We also show that determining whether a WA is r-regret determinizable for some r is in 3 EXPtime. 0 9 2 1 Introduction 0 . 1 Weightedautomata. Weightedautomatageneralizefiniteautomatawithweightsontransitions[DKV09]. 0 7 Theygeneralizewordlanguagesto partialfunctions fromwordstovaluesofasemiring. Firstintroduced 1 bySchützenbergerandChomskyinthe60s,theyhavebeenstudiedforlong[DKV09],withapplicationsin v: naturallanguage and image processingfor instance. More recently, they have found new applications in i computer-aidedverificationasameasureofsystemqualitythroughquantitativeproperties[CDH10],and X in system synthesis, as objectives for quantitative games [FGR12]. In this paper, we consider weighted r automata N over the semiring (Z∪{−∞},max,+), and just call them weighted automata (WA). The a value of a run is the sum of the weights occurring on its transitions, and the value of a word is the maximal value of all its accepting runs. Absent transitions have a weight of −∞ and runs of value −∞ are considered non-accepting. This defines a partial function denoted JNK : Σ∗ → Z whose domain is denoted by L . N Determinization problem. Mostofthegoodalgorithmicpropertiesoffiniteautomatadonottransfer to WA. Notably, the (quantitative) language inclusion JAK ≤ JBK is undecidable for WA [Kro92] (see also [DGM16] and [ABK11] for different proofs based on reductions from the halting problem for two- countermachines). Thishastriggeredresearchonsub-classesorotherformalismsforwhichthisproblem becomes decidable [FGR14,CE+10]. This includes the class of deterministic WA (DWA, also known as sequential WA in the literature), which are the WA whose underlying (unweighted) automaton is ∗ThisworkwaspartiallysupportedbytheERCStartinggrant279499(inVEST),theARCprojectTransform(Fédération Wallonie-Bruxelles), andthe BelgianFNRSCDR project Flare. E. Filiotis anF.R.S.-FNRSresearch associate, I. Jecker anF.R.S.-FNRSAspirantfellow,andG.A.Pérez anF.R.S.-FNRSAspirantfellowandFWApost-docfellow. 1 deterministic. AnotherscenariowhereitisdesirabletohaveaDWAisthequantitativesynthesisproblem, undecidable evenfor unambiguousWA, yetdecidable for DWA [FGR12]. However,and incontrastwith finite unweighted automata, WA are not determinizable in general. For instance, the function which outputs the maximalvalue between the number of a’s andthe number of b’s ina wordα∈{a,b}∗ is not realizablewithaDWA.Thismotivatesthedeterminizationproblem: givenaWAN,isitdeterminizable? I.e. is there a DWA defining the same (partial) function as N? The determinization problem for computational models is fundamental in theoretical computer sci- ence. For WA in particular, it is sometimes more natural (and at least exponentially more succinct) to specify a (non-deterministic) WA, even if some equivalent DWA exists. If the function is specified in a weighted logic equivalent to WA, such as weighted MSO [DG07], the logic-to-automata transformation mayconstructanon-deterministic,butdeterminizable,WA.However,despite manyresearchefforts,the largest class for which this problem is known to be decidable is the class of polynomially ambiguous WA [KL09], and the decidability status for the full class of WA is a long-standing open problem. Other contributions and approaches to the determinization problem include the identification of sufficient conditions for determinizability [Moh97], approximate determinizability (for unambiguous WA) where the DWA is required to produce values at most t times the value of the WA, for a given factor t [AKL13], and (incomplete) approximationalgorithms when the weights are non-negative [CD16]. Bounded-delay & regret determinizers. In this paper, we adopt another approachthat consists in constrainingthe class ofDWA thatcan be usedfor determinization. More precisely,we define a class of DWA C as a function from WA to sets of DWA, and say that a DWA D is a C-determinizer of a WA N if(i)D∈C(N)and(ii)JNK=JDK. Then,N is saidtobe C-deteminizableifitadmits aC-determinizer. If DWA denotes the function mapping any WA to the whole set of DWA, then obviously the DWA- determinization problem is the general (open) determinization problem. In this paper, we consider two restrictions. First, given a bound k ∈ N, we look for the class of k-delay DWA Del , which maintain a strong k relationwiththe sequenceofvaluesalongsomeacceptingrunofthe non-deterministicautomaton. More precisely, a DWA D belongs to Del (N) if for all words α∈L , there is an accepting run ̺ of N with k D maximal value such that the running sum of the prefixes of ̺ and the running sum of the prefixes of the unique run ̺ of D on α are constantly close in the following sense: for all lengths ℓ, the absolute D value of the difference of the value of the prefix of ̺ of length ℓ and the value of the prefix of ̺ of D lengthℓ is atmostk. Thenthe Del -determinizationproblemamountsto deciding whether there exists k D ∈ Del such that JNK = JDK. And if k is left unspecified, it amounts to decide whether there k exists D ∈ S Del (N) such that JNK = JDK. We note Del the function mapping any WA N to k∈N k S Del (N). We will show that the Del -determinization problem is complete for EXPtime, and the k k k Del-determinization problem is equivalent to the general (unconstrained) determinization problem. The notion of delay has been central in many works on automata with outputs. For instance, it has been a key notion in transducer theory (automata with word outputs) for the determinization and the functionality problems [BCPS03], and the decomposition of finite-valued transducers [SdS08]. The notion of delay has been also used in the theory of WA, for instance to give sufficient conditions for determinizability [Moh97] or for the decomposition of finite-valued group automata [FGR14]. Example 1. Let A={a,b}and k ∈N. The left automatonof Fig. 1 maps anywordin AaA∗ to 0, and any word in AbA∗ to 1. It is Del -determinizable by the right automaton of Fig. 1. After one step, the k delay ofthe DWA is k with both transitions ofthe left WA. After twoor more steps, the delayis always 0. It is not Del -determinizable for any j < k. (A second example of a bounded-delay determinizable j automaton is shown in Fig. 2.) Second, we consider the class Hom of so-called homomorphic DWA. Intuitively, any DWA D ∈ Hom(N) maintains a close relation with the structure of N: the existence of an homomorphism from D to N. An alternativedefinition is that of a 0-regret game [HPR16] playedonN: Adam choosesinput symbols one by one (forming a word α ∈ L ), while Eve reacts by choosing transitions of N, thus N constructing a run ̺ of N on the fly (i.e. without knowing the full word α in advance). Eve wins the gameif̺isacceptinganditsvalueisequaltoJNK(α), i.e. ̺isamaximalacceptingrunonα. Then,any (finite memory)winning strategy for Eve canbe seenas a Hom-determinizer of N and conversely. This generalizesthe notionofgood-for-gamesautomata,whichdo notneed to be determinized priorto being used as observers in a game, from the Boolean setting [HP06] to the quantitative one. In some sense, 2 a,k A,0 A,0 A,−k b,1−k A,0 a,0 b,0 b,1 A,k A,0 a,0 Figure 1: A WA (left) and one of its k-delay determinizers (right) a,k a,0 b,−k a,0 a,k b,−2k a,−k b,0 b,−k a,0 b,k b,2k Figure 2: Another WA (left) and one of its 2k-delay determinizers (right) Hom-determinizable WA are “goodfor quantitative games”: when used as an observerin a quantitative game, Eve’s strategy can be applied on the fly instead of determinizing the WA and constructing the synchronizedproduct of the resulting DWA with the game arena. This notion has been first introduced in [AKL10] with motivations coming from the analysis of online algorithms. In [AKL10], it was shown that the Hom-determinization problem is in Ptime. Example 2. The following WA maps both ab and aa to 0. It is not Hom-determinizable because Eve has to choose whether to go left or right on reading a. If she goes right, then Adam wins by choosing letter b. If she goes left, Adam wins by picking a again. However, it is almost Hom-determinizable by the DWA obtained by removing the right part, in the sense that the function realized by this DWA is 1-close from the original one. This motivates approximate determinization. a,0 b,0 a,0 a,0 a,1 Figure3: AWAthatisDel -determinizableand(1,Hom)-determinizable,butnotHom-determinizable 0 Approximate determinization. Approximate determinization of a WA N relaxes the determinization problem to determinizers which do not define exactly the same function as N but approximate it. Precisely, for a class C of DWA, D a DWA and r ∈ N, we say that D is an (r,C)-determinizer of N if (i) D ∈ C(N), (ii) L = L and (iii) for all words α ∈ L , |JNK(α)−JDK(α)| ≤ r. Then, N is D N N (r,C)-determinizable if it admits some (r,C)-determinizer, and it is approximately C-determinizable if it is (r,C)-determinizable for some r. As Example 2 shows, there are WA that are approximately Hom-determinizable but not Hom- determinizable, making this notion appealing for the class of homomorphic determinizers. However, thereareclassesCforwhichaWAisapproximatelyC-determinizableifandonlyifitisC-determinizable, making approximate determinization much less interesting for such classes. This is the case for classes C which are complete for determinization (Theorem 1), in the sense that any determinizable WA is also C-determinizable. Obviously, the class DWA is complete for determinization, but we show it is also the case for the class of bounded-delay determinizers Del (Theorem 2). Therefore, we study approximatedeterminizationfortheclassofhomomorphicdeterminizersonly. Wecallsuchdeterminizers r-regret determinizers, building on the regret game analogy given above. Indeed, a WA N is (r,Hom)- determinizable if and only if Eve wins the regret game previously defined, with the following modified 3 winning condition: the run that she constructs on the fly must be such that |JNK(α)−JDK(α)| ≤r, for all words α ∈ L that Adam can play. We say that a WA N is approximately Hom-determinizable if N there exists a r ∈N such that N is (r,Hom)-determinizable. Contributions. We showthatthe Del -determinizationproblemproblemis EXPtime-complete,even k whenk isfixed(Theorems3and4). WealsoshowthattheclassDeliscompletefordeterminization,i.e. any determinizable WA N is k-delay determinizable for some k (Theorem 2). This shows that solving the Del-determinization problem would solve the (open) general determinization problem. This also gives a new (complete) semi-algorithm for determinization, which consists in testing for the existence of k-delay determinizers for increasing values k. We exhibit a family of bounded-delay determinizable WA, for delays which depend exponentially on the WA. Despite our efforts, exponential delays are the highest lower bound we have found. Interestingly, finding higher lower bounds would lead to a better understandingofthedeterminizationproblem,andprovingthatoneoftheselowerboundisalsoanupper bound would immediately give decidability. To decide Del -determinization, we provide a reduction to k Hom-determinization (i.e. 0-regret determinization), which is known to be decidable in polynomial time [AKL10]. We showthatthe approximateHom-determinizationproblemis decidablein exponentialtime (The- orem 7), a problem which was left open in [AKL10]. This result is based on a non-trivial extension to the quantitative setting of a game tool proposed by Kuperberg and Skrzypczak in [KS15] for Boolean automata. In particular, our quantitative extension is based on energy games [BFL+08] while parity gamesaresufficientforthe Booleancase. Ifr isgiven(inbinary)the (r,Hom)-determinizationproblem is shown to be EXPtime-complete (Theorems 5 and 8). The hardness holds even if r is given in unary. In the course of establishing our results, we also show that every WA A that is approximately Hom- determinizableisalsoexactlydeterminizablebuttheremaynotbeahomomorphismfromadeterministic version of the automaton to the original one (Lemma 22 and Theorem 6). Hence, the decision proce- dure for approximate Hom-determinizability can also be used as an algorithmically verifiable sufficient condition for determinizability. Other related works. In transducer theory, a notion close to the notion of k-delay determinizer has beenintroducedin[FJLW16],thatofk-delayuniformizersofatransducer. Auniformizerofatransducer T is an(input)-deterministic transducersuchthat the word-to-wordfunctionit defines (seenasa binary relation) is included in the relation defined by T, and any of its accepting runs should be k-delay close from some accepting run of T. While the notion of k-delay uniformizer in transducer theory is close to the notion of k-delay determinizer for WA, the presence of a max operation in WA makes the k-delay determinization problem conceptually harder. 2 Preliminaries We denote by Z the set of all integers; by N, the set of all non-negative integers, i.e. the natural numbers—including 0; by S⊳x, the subset {s ∈ S | s⊳x} of any given set S. Finally, by ε we denote the empty word over any alphabet. Automata. A (non-deterministic weighted finite) automaton N =(Q,I,A,∆,w,F) consists of a finite set Q of states, a set I ⊆ Q of initial states, a finite alphabet A of symbols, a transition relation ∆ ⊆ Q × A × Q, a weight function w : ∆ → Z, and a set F ⊆ Q of final states. By w we max denote the maximal absolute value of a transition weight, i.e. w := max |w(δ)|. We say N is max δ∈∆ pair-deterministic if |I| = 1 and for all (q,a) ∈ Q× A we have that (q,a,q ),(q,a,q ) ∈ ∆ implies 1 2 q = q or w(q,a,q ) 6= w(q,a,q ); deterministic, if |I| = 1 and for all (q,a) ∈ Q×A we have that 1 2 1 2 (q,a,q ),(q,a,q )∈∆ implies q =q . 1 2 1 2 Arun ofN onaworda ...a ∈A∗ isasequence̺=q a q ...q a q ∈(Q·A)∗Qsuchthat 0 n−1 0 0 1 n−1 n−1 n (q ,a ,q ) ∈ ∆ for all 0 ≤ i < n. We say ̺ is initial if q ∈ I; final, if q ∈ F; accepting, if it is both i i i+1 0 n initial and final. The automaton N is said to be trim if for all states q ∈Q, there is a run from a state q ∈I to q and there is a run from q to some q ∈F. The value of ̺, denoted by w(̺), corresponds to I F the sum of the weights of its transitions: w(̺):=Pn−1w(q ,a ,q ). i=0 i i i+1 The automaton N has the (unweighted) language L = {α ∈ A∗ | there is an accepting run of N N on α} and defines a function JNK : L →Z as follows α 7→max{w(̺) | ̺ is an accepting run of N N on α}. A run ̺ of N on α is said to be maximal if w(̺)=JNK(α). 4 Determinization with delay. Given k ∈ N and two automata N = (Q,I,A,∆,w,F) and N′ = (Q′,I′,A,∆′,w′,F′), we say that N is k-delay-included (or k-included, for short) in N′, denoted by N ⊆ N′, if for every accepting run ̺ = q a ...a q of N, there exists an accepting run ̺′ = k 0 0 n−1 n q′a ...a q′ of N′ such that w′(̺′) = w(̺), and for every 1 ≤ i ≤ n, |w′(q′ ...q′)−w(q ...q )| ≤ k. 0 0 n−1 n 0 i 0 i For an automaton N, we denote by Del (N) the set {D∈DWA | D⊆ N}. k k An automaton N is said to be k-delay determinizable if there exists an automaton D ∈ Del (N) k such that JDK=JNK. Such an automaton is called a k-delay determinizer of N. Determinizationwithregret. GiventwoautomataN =(Q,I,A,∆,w,F)andN′ =(Q′,I′,A,∆′,w′,F′), a mapping µ: Q→Q′ from states in N to states in N′ is a homomorphism from N to N′ if µ(I)⊆I′, µ(F) ⊆ F′, {(µ(p),a,µ(q)) | (p,a,q) ∈ ∆} ⊆ ∆′, and w′(µ(p),a,µ(q)) = w(p,a,q). For an automaton N,wedenotebyHom(N)thesetofdeterministicautomataD forwhichthereisahomomorphismfrom D to N. The following lemma follows directly from the preceding definitions. Lemma 1. For all automata N, for all D ∈ Hom(N), we have that L ⊆ L and JDK(α) ≤ JNK(α) D N for all α∈L . N Given r ∈ N and an automaton N, we say N is r-regret determinizable if there is a deterministic automaton D such that: (i) D ∈ Hom(N), (ii) L = L , and (iii) sup |JNK(α)−JDK(α)| ≤ r. N D α∈LN The automaton D is said to be an r-regret determinizer of N. Note that (i) implies we can remove the absolute value in (iii) because of Lemma 1. Regret games. Givenr ∈NandanautomatonN =(Q,I,A,∆,w,F),anr-regret game isatwo-player turn-basedgameplayedonN byEveandAdam. Tobegin,Evechoosesaninitialstate. Then,the game proceeds in rounds as follows. From the currentstate q, Adam chooses a symbol a∈A and Eve chooses a new state q′ (notnecessarilya valid a-successorofq). After a wordα∈L has been playedby Adam, N he may decide to stop the game. At this point Eve loses if the currentstate is not final or if she has not constructed a valid run of N on α. Furthermore, she must pay a (regret) value equal to JNK(α) minus the value of the run she has constructed. Formally,astrategyfor Adam isafinitewordα∈A∗ fromrunstosymbolsandastrategyfor Eve isa functionσ :(Q·A)∗ →Qfromstate-symbolsequencestostates. Givenaword(strategy)α=a ...a , 0 n−1 we write σ(α) to denote the sequence q a ...a q such that σ(ε)=q and σ(q a ...q a )=q for 0 0 n−1 n 0 0 0 i i i+1 all 0≤iχ (1) 0 0 ℓ−1 ℓ 0 0 ℓ−1 ℓ forsome0≤ℓ≤nandq′a ...a q′ theuniqueinitialrunofDonα. Weconsiderthetwopossibilities. 0 0 n−1 n Supposethatw(q a ...a q )−w′(q′a ...a q′)>χ. Then,atleastonefinalstateq isreachable 0 0 ℓ−1 ℓ 0 0 ℓ−1 ℓ n inN fromq ,andtheshortestpathtoitconsistsofatmost|Q|transitions. Sinceχ≥|Q|(w +w′ ), ℓ max max D does not realize the same function as N, which contradicts our hypothesis. Suppose that w′(q′a ...a q′)−w(q a ...a q ) > χ. Using the fact that χ = |Q||Q′|(w + 0 0 ℓ−1 ℓ 0 0 ℓ−1 ℓ max w′ ),weexposealoopthatcanbepumpeddowntopresentawordmappedtodifferentvaluesbyDand max N. For every0≤j ≤|Q||Q′|, let 0≤i ≤ℓ denote the minimalintegersatisfying w′(q′a ...a q′ )− j 0 0 ij−1 ij w(q a ...a q ) ≥ j(w + w′ ). Then there exist 0 ≤ j < k ≤ |Q||Q′| such that q = q , 0 0 ij−1 ij max max ij ik q′ =q′ . Moreover, since w and w′ correspond to the maximal weights of N and D respectively, ij ik max max i 6= i holds, and w(q a ...a q ) > w′(q′ a ...a q′ ). Since D is deterministic, it assigns a j k ij ij ik−1 ik ij ij ik−1 ik strictly lowervalue thanJNK to the worda ...a a ...a , which contradictsour assumptionthat 0 ij−1 ik n−1 D realizes the same function as N. Although we do not have an upper bound on the k needed for a determinizable automaton to be k-delay determinizable, we are able to provide an exponentially large lower bound. Proposition6. Given an automaton N =(Q,I,A,∆,w,F), a delay k as big as 2O(|Q|) might be needed for it to be k-delay determinizable. To prove the above proposition we will make use of the language of words with a j-pair [KZ15]. Words with a j-pair. Consider the alphabet A = {1,...,n}. Let α = a a ··· ∈ A∗ and j ∈ A. A 0 1 j-pair is a pair of positions i j},0 Figure 4: Automaton N realizing function f which outputs the (negative) length of the word if it has no j-pair. Proof. Consider a word α of length 2n −1 containing no j-pair—which exists according to Lemma 7. Furtherconsideranarbitraryk-determinizerD forN. We remarkthatJDK(α)=JNK(α)=1−2n,since both automata realize f and α does not contain a j-pair. It follows from Lemma 7 that α·a contains a j-pair(thatis,foralla∈A). Hence,foralla∈A,wehaveJNK(α·a) =0. Furthermore,byconstruction of N, for all maximal accepting runs q a ...a q of N on α·a we have w(q ...q ) = 0 for all 0 0 |α|+1 |α|+2 0 i 1 ≤ i ≤ |α|+2. In particular, for i = |α|+1, we have JDK(α)−w(q ...q ) = 2n−1 which proves the 0 i claim. 3.2 Upper bound We nowarguethat0-delaydeterminizabilityisinEXPtime. Then, weshowhowto reduce(inexponen- tial time) k-delay determinizability to 0-delay determinizability. We claim that the composition of the two algorithms remains singly exponential. Proposition 9. Deciding the 0-delay problem for a given automaton is in EXPtime. The result will follow from Propositions 3 and 12. Before we state and proveProposition12 we need some intermediate definitions andlemmas. The following propertiesof k-inclusion,whichfollow directly from the definition, will be useful later. Lemma 10. For all automata N, N′, and N′′, for all k,k′ ∈N, the following hold: 1. if N ⊆k N′ and k ≤k′, then N ⊆k′ N′; 2. if N ⊆k N′ and N′ ⊆k′ N′′, then N ⊆k+k′ N′′; 3. if N ⊆k N′, then LN ⊆LN′, and for every α∈LN, JNK(α)≤JN′K(α). We now show how to decide 0-delaydeterminizability by reductionto 0-regretdeterminizability. Let us first convince the reader that 0-regret determinizability implies 0-delay determinizability. Proposition 11. If an automaton N is 0-regret determinizable, then it is 0-delay determinizable. Proof. We have, from Lemma 2, that Eve has a finite-memory winning strategy σ in the 0-regret game played on N. Then, by definition of the regret game, L = L , and for every α ∈ L , JNK(α)− N Nσ N JN K(α) ≤ 0, hence JNK = JN K. Moreover, as Eve chooses a run in N, we have N ⊆ N. Therefore σ σ σ 0 N is a 0-delay determinizer of N. σ The converse of the above result does not hold in general (see Fig. 3). Nonetheless, it holds when the automatonispair-deterministic. We nowshowthat, underthis hypothesis,anautomatonis0-regret determinizable if and only if the automaton is 0-delay determinizable. Proposition12. A pair-deterministic automaton N is 0-delaydeterminizable if andonlyif it is0-regret determinizable. Sketch. If N is 0-regret determinizable, then N is 0-delay determinizable by Proposition 11. Now suppose that N is 0-delay determinizable, and let D be a 0-delay determinizer of N. For every initial run ̺ = p a p ...a p of D on input α = a ...a , there exists exactly one initial run ̺′ = α 0 0 1 n−1 n 0 n−1 α p′a p′ ...a p′ of N such that for every 1≤i≤n, w(p′ ...p′)=w′(p ...p ). The existence of ̺′ is 0 0 1 n−1 n 0 i 0 i α 8 guaranteedby the fact that D is a 0-delay determinizer of N, and, since N is pair-deterministic, such a run is unique. Then the strategy for Eve in the 0-regretgame played on N obtained by following, given an input word α, the run ̺′ of N, is winning. α We observe that any automaton N =(Q,I,A,∆,w,F) can be transformed into a pair-deterministic automaton P(N) with at most an exponential blow-up in the state-space. Intuitively, we merge all the states from the originalautomaton which can be reachedby reading a∈A and taking a transition with weightx∈Z. Thisisageneralizationoftheclassicalsubsetconstructionusedtodeterminizeunweighted automata. Critically,theconstructionissuchthatP(N)⊆ N andN ⊆ P(N). (Forcompleteness,the 0 0 construction is given in appendix.) The next result then follows immediately from the latter property and from Lemma 10 item 2. Proposition 13. An automaton N is 0-delay determinizable if and only if P(N) is 0-delay determinizable if and only if P(N) is 0-regret determinizable. We now show how to extend the above techniques to the general case of k-delay. Theorem 3. Deciding the k-delay problem for a given automaton is in EXPtime. Given an automaton N and k ∈ N, we will construct a new automaton δ (N) that will encode k delays (up to k) in its state space. In this new automaton, for every state-delay pair (p,i) and for every transition (p,a,q) ∈ ∆, we will have an a-labelled transition to (q,j) with weight i+w(p,a,q)−j for all −k ≤j ≤k. Intuitively, i is the amount of delay the automaton currently has, and to get to a point wherethedelaybecomesj viatransition(p,a,q)aweightofi+w(p,a,q)−j mustbeoutputted. Wewill then show that the resulting automaton is 0-delay determinizable if and only if the original automaton is k-delay determinizable. k-delay construction. Let N =(Q,I,A,∆,w,F) be anautomaton. Let δ (N)=(Q′,I′,A,∆′,w′,F′) k be the automaton defined as follows. • Q′ =Q×{−k,...,k}; • I′ =I×{0}; • ∆′ ={((p,i),a,(q,j)) | (p,a,q)∈∆}; • w′ :∆′ →Z, ((p,i),a,(q,j))7→i+w(p,a,q)−j; • F′ =F ×{0}. Lemma 14. The k-delay construction satisfies the following properties. 1. δ (N)⊆ N; k k 2. for every automaton M such that M⊆ N, we have M⊆ δ (N); k 0 k 3. Jδ (N)K=JNK. k Proof. 1) Let (q ,i )a (q ,i )...a (q ,i ) be an accepting run of δ (N). Then q a q ...a q is an ac- 0 0 0 1 1 n−1 n n k 0 0 1 n−1 n cepting run of N, and for every 0≤j

On Delay and Regret Determinization of Max-Plus Automata

Similar On Delay and Regret Determinization of Max-Plus Automata