Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata

A max-plus automaton is a finite automaton whose transitions are weighted by real numbers. A max-plus automaton assigns a weight to each of its runs by adding the weights of the transitions which constitute the run and it assigns a weight to every word by taking the maximum over the weights of all runs on the given word. Max-plus automata are weighted automata [1,2,3,4,5] over the max-plus semiring. In the form of min-plus automata, they were originally introduced by Imre Simon as a means to show the decidability of the finite power property [6, 7] and they enjoy a continuing interest [8,9,10,11,12,13,14]. They have found applications in many different contexts, for example to determine the star height of a language [15], to prove the termination of certain string rewriting systems [16], and to model discrete event systems [17]. They also appear in the context of natural language processing [18], where probabilities are often computed in the min-plus semiring as negative log-likelihoods for reasons of numerical stability.

Like finite automata, max-plus automata are by definition non-deterministic devices. However, while every finite automaton can be determinized [19], the same is in general not true for max-plus automata [10]. In fact, it is a long-standing open question whether given a max-plus automaton, the existence of an equivalent deterministic automaton can be decided. This problem is commonly known as the sequentiality problem and is one of the most prominent open questions about max-plus automata. For practical applications, the execution of a deterministic automaton is of course much more efficient than the execution of a non-deterministic one, so being able to decide whether a given automaton can be determinized is very much desirable. While open in general, the sequentiality problem has been shown to be decidable for some important subclasses of max-plus automata, namely for unambiguous [18], finitely ambiguous [10], and polynomially ambiguous [20] max-plus automata. Here, we call a max-plus automaton unambiguous if there exists at most one run on every word, finitely ambiguous if the number of runs on each word is bounded by a global constant, and polynomially ambiguous if the number of runs on each word is bounded polynomially in the length of the word. Note that the classes of deterministic, unambiguous, finitely ambiguous, polynomially ambiguous, and arbitrary max-plus automata form a strictly ascending hierarchy [10, 14, 21]. Also, deciding the degree of ambiguity of a max-plus automaton can easily be reduced to deciding the degree of ambiguity of a finite automaton. It is trivial to decide whether a finite automaton is deterministic. Polynomial time algorithms to decide whether a finite automaton is unambiguous, finitely ambiguous, or polynomially ambiguous can be found in [22,23,24].

While a given max-plus automaton may not be equivalent to a single deterministic max-plus automaton, this does not exclude the possibility that it is equivalent to the pointwise maximum of finitely many deterministic automata. The problem of deciding whether a max-plus automaton possesses such a finitely sequential representation is known as the finite sequentiality problem. The decidability of the finite sequentiality problem was posed as an open question in [9] and has been solved only recently for unambiguous [25] and finitely ambiguous [26] max-plus automata. Note that the class of max-plus automata which possess a finitely sequential representation lies strictly between the classes of deterministic and finitely ambiguous max-plus automata, and it is incomparable to the class of unambiguous max-plus automata [10].

In this paper, we show that the finite sequentiality problem is decidable for finitely ambiguous max-plus tree automata. Operating on trees instead of words, max-plus tree automata are a generalization of max-plus word automata and more generally, they are weighted tree automata [27,28,29,30] over the max-plus semiring. Applications of max-plus tree automata include proving the termination of certain term rewriting systems [31] and they are commonly employed in natural language processing [32] in the form of probabilistic context-free grammars. Our approach to proving the decidability of the finite sequentiality problem for finitely ambiguous max-plus tree automata employs ideas from Bala’s proof of the corresponding result for finitely ambiguous max-plus word automata [26]. However, due to lack of space, formal proofs had to be omitted in [26] and Bala’s informal description of his methods does not suffice for reconstruction. Also, no other published version of [26] exists. We provide an honest attempt to compare our approach to his but note that our interpretation might not be accurate.

In his proof for max-plus word automata, Bala first introduces the A-Fork property and then proceeds to show that this property is a decidable criterion characterizing the finite sequentiality of a finitely ambiguous max-plus automaton. More precisely, he shows that a finitely ambiguous max-plus automaton possesses a finitely sequential representation if and only if the A-Fork property is not satisfied. To show the decidability of the A-Fork property, he shows its expressibility in a decidable fragment of Presburger arithmetic. To show that an automaton is not finitely sequential if the A-Fork property is satisfied, he uses pumping techniques similar to those employed in [25] for the finite sequentiality problem of unambiguous max-plus word automata. This part of his proof most likely employs Ramsey’s Theorem [33] as it involves “colorings of finite hypercubes’. His proof for the existence of a finitely sequential representation in case that the A-Fork property is not satisfied employs transducers and the notions of critical pairs and close approximations, none of which occur in our approach. We are thus unsure about the nature of this particular part of the proof, but it most likely uses a reduction to the decidability of the finite sequentiality problem for unambiguous automata.

Our approach is as follows. First, we introduce the separation property, a twofold modification of the A-Fork property. On the one hand, we endow our new property with a criterion accounting for the non-linear structure of trees. This new criterion is inspired by the criterion we added in [34] to the fork property [25], the property characterizing finite sequentiality of unambiguous max-plus word automata, in order to obtain the tree fork property, the property characterizing finite sequentiality of unambiguous max-plus tree automata. On the other hand, we strengthen the A-Fork property as with only the first modification, our new property would wrongly characterize some finitely sequential automata as not being finitely sequential. We then show that the separation property is decidable by employing Parikh s Theorem [35, 36] for a reduction to the decidability of the satisfiability of systems of linear inequalities over the rational numbers with integer solutions [37, 38]. This means in particular that we show the decidability of the finite sequentiality problem only for automata with weights in the rationals. Then we employ Ramsey’s Theorem to show that no finitely sequential representation exists whenever the separation property is satisfied. Due to the criterion accounting for the non-linearity of trees, this is considerably more difficult than in [26] and it is in fact the most technical and the most challenging aspect of our result. Finally, we show that if the separation property is not satisfied for a given max-plus tree automaton, then we can construct finitely many unambiguous max-plus tree automata which all do not satisfy the tree fork property and whose pointwise maximum is equivalent to the automaton. By [34], these unambiguous automata then possess finitely sequential representations. Combining these, we obtain a finitely sequential representation of the original automaton.

An extended abstract of this paper appeared as [39]. Here, we provide full proofs together with detailed illustrations for these.

For a set X, we denote the power set of X by \(\mathcal {P}(X)\) and the cardinality of X by |X|. For two sets X and Y and a mapping f : X → Y, we call X the domain of f, denoted by dom(f), and Y the range of f, denoted by range(f). For a subset \(X^{\prime } \subseteq X\), we call the set \(f(X^{\prime }) = \{ y \in Y \mid \exists x \in X^{\prime } \colon f(x) = y \}\) the image or range of \(X^{\prime }\) under f. The restriction of f to \(X^{\prime }\), denoted by \(f \!\!\upharpoonright _{X^{\prime }}\), is the mapping \(f\!\!\!\upharpoonright _{X^{\prime }} \colon X^{\prime } \to Y\) defined by \(f\!\!\upharpoonright _{X^{\prime }}(x) = f(x)\) for every \(x \in X^{\prime }\). For an element y ∈ Y, we call the set f^− 1(y) = {x ∈ X∣f(x) = y} the preimage of y under f. For a second mapping g: X → Y, we write f = g if for all x ∈ X we have f(x) = g(x).

An alphabet Σ is a non-empty finite set. By Σ^∗, we denote the set of all finite words over Σ. The empty word is denoted by ε, and the length of a word w ∈Σ^∗ by |w|. The number of occurrences of a letter a ∈Σ in a word w is denoted by |w|_a. A subset \(L \subseteq {{\varSigma }}^{*}\) is called a language over Σ.

We let \(\mathbb {N} = \{0,1,2,\ldots \}\). By \(\mathbb {N}^{*}\) we denote the set of all finite words over \(\mathbb {N}\). The set \(\mathbb {N}^{*}\) is partially ordered by the prefix relation ≤_p and totally ordered with respect to the lexicographic ordering ≤_l. Two words from \(\mathbb {N}^{*}\) are called prefix-dependent if they are in prefix relation, and otherwise they are called prefix-independent.

A ranked alphabet is a pair (Γ,rk_Γ), often abbreviated by Γ, where Γ is a non-empty finite set and \(\text {rk}_{{{\varGamma }}}\colon {{\varGamma }} \to \mathbb {N}\) a mapping which assigns a rank to every symbol. For every m ≥ 0 we define \({{\varGamma }}^{(m)} = \text {rk}_{{{\varGamma }}}^{-1}(m)\) as the set of all symbols of rank m. The rank of Γ is defined as \(\text {rk}({{\varGamma }}) = \max \limits \{\text {rk}_{{{\varGamma }}}(a) \mid a \in {{\varGamma }}\}\).

The set of (finite, labeled, and ordered) Γ-trees, denoted by T_Γ, is the set of all pairs t = (pos(t),label_t), where \(\text {pos}(t) \subset \mathbb {N}^{*}\) is a finite non-empty prefix-closed set of positions, label_t: pos(t) →Γ is a mapping, and for every w ∈pos(t) we have wi ∈pos(t) iff 1 ≤ i ≤rk_Γ(label_t(w)). We write t(w) for label_t(w) and |t| for |pos(t)|. We also refer to the elements of pos(t) as nodes, to ε as the root of t, and to prefix-maximal nodes as leaves. The height of t is defined as \(\text {height}(t) = \max \limits _{w \in \text {pos}(t)} |w|\). For a leaf w ∈pos(t), the set {v ∈pos(t)∣v ≤_pw} is called a branch of t. A subset \(L \subseteq T_{{{\varGamma }}}\) is called a tree language over Γ.

Now let s, t ∈ T_Γ and w ∈pos(t). The subtree of t at w, denoted by \(t\!\!\upharpoonright _{w}\), is a Γ-tree defined as follows. We let \(\text {pos}(t\!\!\upharpoonright _{w}) = \{ v \in \mathbb {N}^{*} \mid wv \in \text {pos}(t)\}\) and for \(v \in \text {pos}(t\!\!\upharpoonright _{w})\), we let \(\text {label}_{t\!\upharpoonright _{w}}(v) = t(wv)\).

The substitution of s into w of t, denoted by t〈s → w〉, is a Γ-tree defined as follows. We let pos(t〈s → w〉) = (pos(t) ∖{v ∈pos(t)∣w ≤_pv})∪{wv∣v ∈pos(s)}. For u ∈pos(t〈s → w〉), we let label_t〈s→w〉(u) = s(v) if u = wv for some v ∈pos(s), and otherwise label_t〈s→w〉(u) = t(u).

For a ∈Γ^(m) and trees t₁,…,t_m ∈ T_Γ, we also write a(t₁,…,t_m) to denote the tree t with pos(t) = {ε}∪{iw∣i ∈{1,…,m},w ∈pos(t_i)}, label_t(ε) = a, and label_t(iw) = t_i(w). For a ∈Γ⁽⁰⁾, the tree a() is abbreviated by a.

For a ranked alphabet Γ, a tree over the alphabet Γ_◇ = (Γ∪{◇},rk_Γ∪{◇↦0}) is called a Γ-context. Let \(t \in T_{{{\varGamma }}_{{\diamond }}}\) be a Γ-context and let w₁,…,w_n ∈pos(t) be a lexicographically ordered enumeration of all leaves of t labeled ◇. Then we call t an n-Γ-context and define ◊_i(t) = w_i for i ∈{1,…,n}. For an n-Γ-context t and contexts \(t_{1}, \ldots , t_{n} \in T_{{{\varGamma }}_{\diamond }}\), we define t(t₁,…,t_n) = t〈t₁ → ◊₁(t)〉⋯〈t_n → ◊_n(t)〉 by substitution of t₁,…,t_n into the ◇-leaves of t. We also call a 1-Γ-context a Γ-word. For a Γ-word s, we define s⁰ = ◇ and s^n+ 1 = s(sⁿ) for n ≥ 0.

A commutative semiring is a tuple , abbreviated by K, with operations sum ⊕ and product ⊙ and constants and such that and are commutative monoids, multiplication distributes over addition, and for every κ ∈ K. In this paper, we mainly consider the following two semirings.

• The Boolean semiring \(\mathbb {B} = (\{0,1\}, \lor , \land , 0, 1)\) with disjunction ∨ and conjunction ∧.

• The max-plus semiring \(\mathbb {{Q}}_{\max \limits } = {}(\mathbb {Q} \boldsymbol {\cup } \{-\infty \},\max \limits ,+,-\infty ,0)\) where the sum and the product operations are \(\max \limits \) and + , respectively, extended to \(\mathbb {Q} \boldsymbol {\cup } \{-\infty \}\) in the usual way.

For a commutative semiring and an integer n ≥ 1, the product semiring is defined by componentwise operations and the constants and . We will usually denote ⊕_n and ⊙_n simply by ⊕ and ⊙.

Let be a commutative semiring. A weighted bottom-up finite state tree automaton (short: WTA) over K and Γ is a tuple \(\mathcal {A} = ({Q},{{\varGamma }},{\mu },{\nu })\) where Q is a finite set (of states), Γ is a ranked alphabet (of input symbols), \({\mu } \colon \bigcup _{m=0}^{\text {rk}({{\varGamma }})} {Q}^{m} \times {{\varGamma }}^{(m)} \times {Q} \to K\) (the function of transition weights), and ν : Q → K (the function of final weights). We define \({\Delta }_{\mathcal {A}} = \text {dom}({\mu })\). A tuple \(d \in {\Delta }_{\mathcal {A}}\) is called a transition and d is called valid if . A state q ∈ Q is called final if .

We call a WTA over the max-plus semiring a max-plus-WTA and a WTA over the Boolean semiring a finite tree automaton (FTA). We also write a WTA \(\mathcal {A} = ({Q},{{\varGamma }},{\mu },{\nu })\) over \(\mathbb {B}\) as a tuple \(\mathcal {A}^{\prime } = ({Q}, {{\varGamma }}, \delta , F)\) where \(\delta = \{d \in {\Delta }_{\mathcal {A}} \mid {\mu }(d) = 1\}\) and F = {q ∈ Q∣ν(q) = 1}.

For a tree t ∈ T_Γ, a mapping r: pos(t) → Q is called a quasi-run of \(\mathcal {A}\) on t. For a quasi-run r on t and a position w ∈pos(t) with t(w) = a ∈Γ^(m), the tuple

is called the transition at w. The quasi-run r is called a (valid) run if for every w ∈pos(t) the transition \(\mathbbm {t}(t,r,w)\) is valid with respect to \(\mathcal {A}\). We call a run r accepting if r(ε) is final. By \(\text {Run}_{\mathcal {A}}(t)\) and \(\text {Acc}_{\mathcal {A}}(t)\) we denote the sets of all runs and all accepting runs of \(\mathcal {A}\) on t, respectively. For a state q ∈ Q, we denote by \(\text {Run}_{\mathcal {A}}(t,q)\) the set of all runs \(r \in \text {Run}_{\mathcal {A}}(t)\) such that r(ε) = q. For a position w ∈pos(t), we define the restriction \(r \!\!\upharpoonright _{w} \in \text {Run}_{\mathcal {A}}(t \!\!\upharpoonright _{w})\) of r to w by \(r \!\!\upharpoonright _{w}(v) = r(wv)\) for every \(v \in \text {pos}(t \!\!\upharpoonright _{w})\).

For a run \(r \in \text {Run}_{\mathcal {A}}(t)\), the weight of r is defined by

The behavior of \(\mathcal {A}\), denoted by \(\llbracket {\mathcal {A}}\rrbracket \), is the mapping defined for every t ∈ T_Γ by

where the sum over the empty set is by convention. The support of a WTA \(\mathcal {A}\) is the set . The support of an FTA \(\mathcal {A}\) is also called the language accepted by \(\mathcal {A}\) and denoted by \({\mathscr{L}}(\mathcal {A})\). A subset \(L \subseteq T_{{{\varGamma }}}\) is called recognizable if there exists an FTA \(\mathcal {A}\) with \(L = {\mathscr{L}}(\mathcal {A})\).

For a WTA \(\mathcal {A} = ({Q}, {{\varGamma }}, {\mu }, {\nu })\), a run of \(\mathcal {A}\) on a Γ-context t is a run of the WTA \(\mathcal {A}^{\prime } = ({Q}, {{\varGamma }}_{{\diamond }}, {\mu }^{\prime }, {\nu })\) on t, where for all q ∈ Q and \({\mu }^{\prime }(d) = {\mu }(d)\) for all \(d \in {\Delta }_{\mathcal {A}}\). We denote \(\text {Run}_{\mathcal {A}}^{{\diamond }}(t) = \text {Run}_{\mathcal {A}^{\prime }}(t)\) and for \(r \in \text {Run}_{\mathcal {A}}^{{\diamond }}(t)\) define \(\text {wt}_{\mathcal {A}}^{{\diamond }}(t, r) = \text {wt}_{\mathcal {A}^{\prime }}(t, r)\). For an n-Γ-context \(t \in T_{{{\varGamma }}_{{\diamond }}}\) and states q₀,…,q_n, we denote by \(\text {Run}^{{\diamond }}_{\mathcal {A}}(q_{1}, \ldots , q_{n}, t, q_{0})\) the set of all runs \(r \in \text {Run}_{\mathcal {A}}^{\diamond }(t)\) such that r(ε) = q₀ and r(◊_i(t)) = q_i for every i ∈{1,…,n}.

We consider the set Γ × Q as an alphabet by defining rk_Γ×Q(a, q) = rk_Γ(a) for every pair (a, q) ∈Γ× Q and identify every tree \(t^{\prime } \in T_{{{\varGamma }} \times Q}\) with the pair (t, r) given by \(t = (\text {pos}(t^{\prime }), \pi _{{{\varGamma }}} \circ \text {label}_{t^{\prime }}) \in T_{{{\varGamma }}}\) and \(r = \pi _{Q} \circ \text {label}_{t^{\prime }}\), where π_Γ: Γ × Q →Γ and π_Q: Γ × Q → Q are the projections. For a Γ-word \(s \in T_{{{\varGamma }}_{\diamond }}\), a state q ∈ Q, and a run \(r_{s} \in \text {Run}^{\diamond }_{\mathcal {A}}(q,s,q)\), we define (s, r_s)⁰ = (◇,q) and \((s,r_{s})^{n+1} = (s,r_{s}) \langle (s,r_{s})^{n} \to {\Diamond }_{1}(s) \rangle \) for n ≥ 0. For a Γ-context \(t \in T_{{{\varGamma }}_{{\diamond }}}\), a run \(r_{t} \in \text {Run}_{\mathcal {A}}^{{\diamond }}(t)\), and a position w ∈pos(t) with r(w) = q, we define the insertion of (s, r_s) into (t, r) at w by .

We call a WTA \(\mathcal {A} = ({Q}, {{\varGamma }}, {\mu }, {\nu })\) over K and Γ trim if for every p ∈ Q, there exist t ∈ T_Γ, \(r \in \text {Acc}_{\mathcal {A}}(t)\), and w ∈pos(t) with r(w) = p. The trim part of \(\mathcal {A}\) is the automaton obtained from \(\mathcal {A}\) by removing all states p ∈ Q for which no such t, r, and w exist. This process obviously has no influence on \(\llbracket {\mathcal {A}}\rrbracket \).

We call \(\mathcal {A}\) complete if for every m ≥ 0, a ∈Γ^(m), and \((q_{1}, \ldots , q_{m}) \in {Q}^{m}\), there exists at least one . We call \(\mathcal {A}\) deterministic or sequential if for every m ≥ 0, a ∈Γ^(m), and \((q_{1}, \ldots , q_{m}) \in {Q}^{m}\), there exists at most one q ∈ Q with . If there exists an integer M ≥ 1 such that \(|\text {Acc}_{\mathcal {A}}(t)| \leq M\) for every t ∈ T_Γ, we call \(\mathcal {A}\) M-ambiguous. We call \(\mathcal {A}\) finitely ambiguous if it is M-ambiguous for some M ≥ 1 and unambiguous if it is 1-ambiguous. We call the behavior \(\llbracket {\mathcal {A}}\rrbracket \) of \(\mathcal {A}\) finitely sequential if there exist finitely many deterministic WTA \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{n}\) over K and Γ such that \(\llbracket {\mathcal {A}}\rrbracket = \bigoplus _{i = 1}^{n} \llbracket {\mathcal {A}_{i}}\rrbracket \), where the sum is taken pointwise.

We will show that for a finitely ambiguous max-plus-WTA \(\mathcal {A}\), it is decidable whether its behavior \(\llbracket {\mathcal {A}}\rrbracket \) is finitely sequential. Moreover, we will show that if \(\llbracket {\mathcal {A}}\rrbracket \) is finitely sequential, then deterministic max-plus-WTA whose pointwise maximum is equivalent to \(\llbracket {\mathcal {A}}\rrbracket \) can be effectively constructed. Our approach is inspired by Bala’s corresponding proof for finitely ambiguous max-plus word automata [26]. A precise comparison of our methods to those of [26] is difficult, however, as for lack of space, most proof details had to be left out in [26]. The general outline of our proof can be summarized as follows.

First, we formulate the separation property, a generalization of Bala’s A-Fork property. Then we show that it is decidable whether the separation property is satisfied and that the behavior of a max-plus-WTA is finitely sequential if and only if the separation property is not satisfied. For the decidability of the separation property, we employ Parikh’s Theorem [35, 36] and show that the decidability of the separation property can be reduced to the satisfiability of systems of linear inequalities over the rationals with integer solutions. To show that the behavior of a max-plus-WTA \(\mathcal {A}\) which satisfies the separation property is not finitely sequential, we assume that \(\llbracket {\mathcal {A}}\rrbracket \) can be represented as a finite maximum of deterministic max-plus-WTA and employ Ramsey’s Theorem [33] to obtain a contradiction. For the converse, if the separation property is not satisfied, we show how to construct finitely many unambiguous max-plus-WTA whose pointwise maximum is equivalent to \(\llbracket {\mathcal {A}}\rrbracket \) and which all do not satisfy the tree fork property. As the behavior of an unambiguous max-plus-WTA which does not satisfy the tree fork property is finitely sequential [34], we obtain that \(\llbracket {\mathcal {A}}\rrbracket \) is also finitely sequential.

We need some more preparation before we can formulate the separation property. In the following, let Γ be a ranked alphabet. We begin by recalling the tree fork property and the related concepts of rivals, reachers, distinguishers, and forks. Intuitively, two states of a finitely ambiguous max-plus-WTA \(\mathcal {A}\) are called rivals if they can be reached by the same tree u and they can loop in the same Γ-word s but the weights of these loops differ. The tree u is then called a reacher of p and q and the Γ-word s a distinguisher for p and q. For two rivals p and q, a Γ-word f is called a p-q-fork if f can both loop in p and also go from p to q, in a bottom-up sense. We say that \(\mathcal {A}\) satisfies the tree fork property if there exist two rivals p and q such that either there exists a p-q-fork or p and q can occur at prefix-independent positions in some run of \(\mathcal {A}\). Formally, these definitions are as follows.

Definition 1

Let \(\mathcal {A} = ({Q}, {{\varGamma }}, {\mu }, {\nu })\) be a finitely ambiguous max-plus-WTA. Two states p, q ∈ Q are called rivals if there exists a tree u ∈ T_Γ with \(\text {Run}_{\mathcal {A}}(u,p) \neq \) ∅ and \(\text {Run}_{\mathcal {A}}(u,q) \neq \emptyset \) and a Γ-word s with runs \(r_{p} \in \text {Run}^{\diamond }_{\mathcal {A}}(p,s,p)\) and \(r_{q} \in \text {Run}^{\diamond }_{\mathcal {A}}(q,s,q)\) such that \(\text {wt}^{{\diamond }}_{\mathcal {A}}(s,r_{p}) \neq \text {wt}^{{\diamond }}_{\mathcal {A}}(s,r_{q})\). In this case, we call u a p-q-reacher and s a p-q-distinguisher.

We say that \(\mathcal {A}\) satisfies the tree fork property if at least one of the following two conditions is satisfied.

1. (i)

   There exist rivals p, q ∈ Q and a Γ-word f with \(\text {Run}_{\mathcal {A}}(p,f,p) \neq \emptyset \) and \(\text {Run}_{\mathcal {A}}(p,f,q) \neq \emptyset \). In this case, we call f a p-q-fork.

2. (ii)

   There exist rivals p, q ∈ Q, a 2-Γ-context \(t \in T_{{{\varGamma }}_{{\diamond }}}\), and a run \(r \in \text {Run}^{{\diamond }}_{\mathcal {A}}(t)\) with r(◊₁(t)) = p and r(◊₂(t)) = q. In this case, we call t a p-q-split.

We have the following theorem relating the tree fork property to finite sequentiality of unambiguous max-plus-WTA.

Theorem 1

[34] The behavior of a trim unambiguous max-plus-WTA \(\mathcal {A}\) is finitely sequential if and only if \(\mathcal {A}\) does not satisfy the tree fork property. If \(\llbracket {\mathcal {A}}\rrbracket \) is finitely sequential, a finitely sequential representation of \(\mathcal {A}\) can be effectively constructed.

For finitely ambiguous max-plus-WTA, however, the tree fork property does not capture finite sequentiality. To see why, consider an unambiguous max-plus-WTA \(\mathcal {A}\) satisfying the tree fork property [10, 25, 34] and let L be the largest weight used in \(\mathcal {A}\). Then construct a one-state max-plus-WTA \({\mathscr{B}}\) whose every transition weight and every final weight is L. Clearly, \({\mathscr{B}}\) is deterministic and we have \(\llbracket {{\mathscr{B}}}\rrbracket \geq \llbracket {\mathcal {A}}\rrbracket \). By taking the disjoint union \(\mathcal {A} \boldsymbol {\cup } {\mathscr{B}}\) of \(\mathcal {A}\) and \({\mathscr{B}}\), we obtain a 2-ambiguous max-plus-WTA which satisfies the tree fork property but whose behavior coincides with that of the deterministic automaton \({\mathscr{B}}\). In this particular example, the states relevant for the tree fork property to be satisfied are not relevant at all for the behavior of the automaton.

In order to reduce the finite sequentiality problem of finitely ambiguous max-plus-WTA to that of unambiguous max-plus-WTA, we decompose every finitely ambiguous max-plus-WTA \(\mathcal {A}\) into a maximum of finitely many unambiguous max-plus-WTA \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{N}\) and then analyze the interplay of these latter automata. We can do so as in fact, every finitely ambiguous WTA can be decomposed into finitely many unambiguous WTA [10, 40]. This is a common approach when dealing with finite ambiguity [10, 41, 42] and is also used by Bala in the corresponding proof for words [26]. In the simplest case, if \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{N}\) all do not satisfy the tree fork property, we find a finitely sequential representation of \(\mathcal {A}\) by constructing such a representation for each \(\mathcal {A}_{n}\) and then combining all of these. However, if some \(\mathcal {A}_{n}\) does satisfy the tree fork property, we have to analyze whether this automaton contributes enough to the behavior of \(\mathcal {A}\) for there not to exist a finitely sequential representation of \(\mathcal {A}\). We have the following lemma.

Lemma 1

[40] Let \(\mathcal {A}\) be a finitely ambiguous WTA over a semiring K and a ranked alphabet Γ, then we can effectively find an integer \(M \in \mathbb {N}\) and construct finitely many unambiguous WTA \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{M}\) over K and Γ with \(\llbracket {\mathcal {A}}\rrbracket = \llbracket {\mathcal {A}_{1}}\rrbracket \oplus {\ldots } \oplus \llbracket {\mathcal {A}_{M}}\rrbracket \).

Proof

We provide a short direct proof. We let n be the number of states of \(\mathcal {A}\). Then by [24], \(\mathcal {A}\) is at most \(2^{2^{2\log (\text {rk}({{\varGamma }})+1)n}}\)-ambiguous. We let \(M = n \cdot 2^{2^{2\log (\text {rk}({{\varGamma }})+1)n}}\). By pigeonhole principle, we obtain that \(|\text {Run}_{\mathcal {A}}(t)| \leq M\) holds for every t ∈ T_Γ. To construct \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{M}\), we employ an idea also used in [43] for word automata, namely a lexicographic ordering on the runs of \(\mathcal {A}\). We write \(\mathcal {A} = (\{1, \ldots , n\}, {{\varGamma }}, {\mu }, {\nu })\) and for every tree t ∈ T_Γ, define a total order <_l on \(\text {Run}_{\mathcal {A}}(t)\) by r₁ <_lr₂ if and only if there exists w ∈pos(t) such that r₁(w) < r₂(w) and for all v ∈pos(t) with v <_lw we have r₁(v) = r₂(v). For every i ∈ {1,…,M}, we define an unambiguous WTA \(\mathcal {A}_{i}\) executing every lexicographically i-th run of \(\mathcal {A}\) as follows. For every m ∈{0,…,rk(Γ)}, we define a total order <_l on (Q ×{1,…,M})^m × Q by \(((q_{1}, n_{1}), \ldots , (q_{m}, n_{m}), q_{0}) \!<_{\textsc {l}}\! ((q_{1}^{\prime }, n_{1}^{\prime }), \ldots , (q_{m}^{\prime }, n_{m}^{\prime }), q_{0}^{\prime })\) if and only if either \(q_{0} \!< q_{0}^{\prime }\) or \(q_{0} = q_{0}^{\prime }\) and for some k ∈{1,,m} we have \(n_{k} < q_{0}^{\prime }\) and for some k ∈{1,,m} we have \(n_{k} < n_{k}^{\prime }\) and \(n_{l} = n_{l}^{\prime }\) for all l < k.

For a letter a ∈Γ^(m) and sets \(V_{1}, \ldots , V_{m} \subseteq {Q} \times \{ 1, \ldots , M\}\), we let \(((q_{1}^{(1)}, n_{1}^{(1)} ), \ldots , (q_{m}^{(1)}, n_{m}^{(1)} ), q_{0}^{(1)} ) <_{\textsc {l}} {\ldots } <_{\textsc {l}} ((q_{1}^{(N)}, n_{1}^{(N)}), \ldots , (q_{m}^{(N)}, n_{m}^{(N)}), q_{0}^{(N)})\) be an enumeration of the set and let

and \(\text {succ}(V_{1}, \ldots , V_{m}, a) = \{(q_{0}^{(k)},k) \mid k \in \{1, \ldots , N\} \}\). Then for every i ∈{1,…,M}, we define a WTA \(\mathcal {A}_{i} = ({Q} \times \{1, \ldots , M\} \times \mathcal {P}({Q} \times \{1, \ldots , M\}), {{\varGamma }},{\mu }^{\prime },{\nu }_{i})\) over K and Γ by defining for every a ∈Γ with m = rk_Γ(a) and \((q_{0},n_{0},V_{0}), \ldots , (q_{m},n_{m},V_{m}) \in {Q} \times \{1, \ldots , M\} \times \mathcal {P}({Q} \times \{1, \ldots , M\})\)

We let π₁: Q ×{1,…,M}→ Q and π₂: Q ×{1,…,M}→{1,…,M} be the projections. Then for every tree t ∈ T_Γ and every runs \(r, r_{1}, r_{2} \in \text {Run}_{\mathcal {A}_{i}}(t)\), we have \(\pi _{1} \circ r \in \text {Run}_{\mathcal {A}}(t)\), \(\text {wt}_{\mathcal {A}_{i}}(t, r) = \text {wt}_{\mathcal {A}}(t, \pi _{1} \circ r)\), and π₁ ∘ r₁ <_lπ₁ ∘ r₂ if and only if π₂ ∘ r₁(ε) < π₂ ∘ r₂(ε). It follows that every automaton \(\mathcal {A}_{i}\) is unambiguous and we have \(\llbracket {\mathcal {A}} \rrbracket = \llbracket {\mathcal {A}_{1}}\rrbracket \oplus {\ldots } \oplus \llbracket {\mathcal {A}_{M}}\rrbracket \). □

In order to analyze the interplay of the unambiguous automata we obtain from Lemma 1 more easily, we want to join them into a product automaton. For this, it is necessary that all of these automata coincide on their support. For the max-plus semiring, this can easily be achieved.

Lemma 2

Let \(\mathcal {A}\) be a finitely ambiguous max-plus-WTA over Γ, then we can effectively find an integer \(M \in \mathbb {N}\) and construct unambiguous max-plus-WTA \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{M}\) over Γ with \(\llbracket {\mathcal {A}}\rrbracket = \max \limits _{i = 1}^{M} \llbracket {\mathcal {A}_{i}}\rrbracket \) and \(\text {supp}(\mathcal {A}_{1}) = {\ldots } = \text {supp}(\mathcal {A}_{M})\).

Proof

By Lemma 1, we can effectively find an integer \(M \in \mathbb {N}\) and construct unambiguous max-plus-WTA \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{M}\) over Γ with \(\llbracket {\mathcal {A}}\rrbracket = \max \limits _{i = 1}^{M} \llbracket {\mathcal {A}_{i}}\rrbracket \). We write \(\mathcal {A}_{i} = ({Q}_{i}, {{\varGamma }}, {\mu }_{i}, {\nu }_{i})\), let \(L = \bigcup _{i = 1}^{M} \text {supp}(\mathcal {A}_{i})\), and let κ be the smallest weight used in the automata \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{M}\), i.e., for \(R = \bigcup _{i = 1}^{M} ({\mu }_{i}({\Delta }_{\mathcal {A}_{i}}) \boldsymbol {\cup } {\nu }_{i}({Q}_{i}))\) we let \(\kappa = {\min \limits } (R \setminus \{-\infty \})\).

First, note that each support \(\text {supp}(\mathcal {A}_{i})\) is recognizable. This follows from the main result of [44], but is also easy to see as replacing the weight \(-\infty \) by 0 and all other weights by 1 in \(\mathcal {A}_{i}\) yields an FTA recognizing \(\text {supp}(\mathcal {A}_{i})\). The tree language L is thus recognizable, therefore for i ∈{1,…,M}, the tree language \(L_{i} = L \setminus \text {supp}(\mathcal {A}_{i})\) is also recognizable and there exists a deterministic FTA \(\mathcal {A}_{i}^{\prime } = ({Q}_{i}^{\prime }, {{\varGamma }}, \delta _{i}^{\prime }, F_{i}^{\prime })\) with \({\mathscr{L}}(\mathcal {A}_{i}^{\prime }) = L_{i}\). We define the max-plus-WTA \(\mathcal {A}_{i}^{\prime \prime } = ({Q}_{i}^{\prime }, {{\varGamma }}, {\mu }_{i}^{\prime \prime }, {\nu }^{\prime \prime })\) by

We assume without loss of generality that \({Q}_{i} \cap {Q}_{i}^{\prime } = \emptyset \) and define \(\mathcal {A}_{i}^{\prime \prime \prime } = ({Q}_{i} \boldsymbol {\cup } {Q}_{i}^{\prime }, {{\varGamma }}, {\mu }_{i}^{\prime \prime \prime }, {\nu }_{i} \boldsymbol {\cup } {\nu }_{i}^{\prime \prime })\) with

as the union of \(\mathcal {A}_{i}\) and \(\mathcal {A}_{i}^{\prime \prime }\). Then \(\mathcal {A}_{i}^{\prime \prime \prime }\) is unambiguous since \(\mathcal {A}_{i}\) is unambiguous, \(\mathcal {A}_{i}^{\prime \prime }\) is deterministic, and \(\text {supp}(\mathcal {A}_{i}) \cap \text {supp}(\mathcal {A}_{i}^{\prime \prime }) = \emptyset \). Furthermore, for \(t \in \text {supp}(\mathcal {A}_{i})\) we have \(\llbracket {\mathcal {A}_{i}^{\prime \prime \prime }}\rrbracket (t) = \llbracket {\mathcal {A}_{i}}\rrbracket (t)\).

For every \(t \in \text {supp}(\mathcal {A}_{i}^{\prime \prime })\), there exists some j ∈{1,…,M} with \(t \in \text {supp}(\mathcal {A}_{j})\) and due to the choice of κ we have \(\llbracket {\mathcal {A}_{j}}\rrbracket (t) \geq \llbracket {\mathcal {A}_{i}^{\prime \prime }}\rrbracket (t)\). In conclusion, for all i ∈{1,…,M} we have that \(\mathcal {A}_{i}^{\prime \prime \prime }\) is unambiguous, \(\text {supp}(\mathcal {A}_{i}^{\prime \prime \prime }) = L\), and \(\max \limits _{i = 1}^{M} \llbracket {\mathcal {A}_{i}^{\prime \prime \prime }}\rrbracket = \max \limits _{i = 1}^{M} \llbracket {\mathcal {A}_{i}}\rrbracket = \llbracket {\mathcal {A}}\rrbracket \). □

For our proofs, it will be convenient to assume that all final weights of the automata we obtain from Lemma 2 are either \(-\infty \) or 0, i.e., they only decide whether a run is accepting or not, but otherwise do not influence the weight of the run. We can do so by the following lemma.

Lemma 3

[45] Let \(\mathcal {A} = ({Q}, {{\varGamma }}, {\mu }, {\nu })\) be a WTA over a semiring K and a ranked alphabet Γ. Then we can effectively construct a WTA \(\mathcal {A}^{\prime } = ({Q}^{\prime }, {{\varGamma }}, {\mu }^{\prime }, {\nu }^{\prime })\) over K and Γ with , and \(|\text {Acc}_{\mathcal {A}}(t)| = |\text {Acc}_{\mathcal {A}^{\prime }}(t)|\) for every t ∈ T_Γ.

Proof

We define the WTA \(\mathcal {A}^{\prime } = ({Q}^{\prime }, {{\varGamma }}, {\mu }^{\prime }, {\nu }^{\prime })\) as follows. We let \({Q}^{\prime } = {Q} \times \{ 0,1 \}\) and define and for all q ∈ Q. For every \(d = (p_{1}, \ldots , p_{m}, a, p_{0}) \in {\Delta }_{\mathcal {A}}\), we let \({\mu }^{\prime }((p_{1},0), \ldots , (p_{m},0), a, (p_{0},0)) = {\mu }(d)\) and \({\mu }^{\prime }((p_{1},0), \ldots , (p_{m},0), a, (p_{0},1)) = {\mu }(d) \odot {\nu }(p_{0})\). On all remaining transitions we define \({\mu }^{\prime }\) as .

It is easy to see that for every tree t ∈ T_Γ, we have a bijection \(f \colon \text {Acc}_{\mathcal {A}}(t) \to \text {Acc}_{\mathcal {A}^{\prime }}(t)\) given by (f(r))(ε) = (r(ε),1) and (f(r))(w) = (r(w),0) for w ∈pos(t) ∖{ε}, and for this bijection it holds that \(\text {wt}_{\mathcal {A}}(t,r) \odot {\nu }(r(\varepsilon )) = \text {wt}_{\mathcal {A}^{\prime }}(t,f(r))\) for every \(r \in \text {Acc}_{\mathcal {A}}(t)\). □

For the rest of this paper, let \(\mathcal {A}\) be a trim finitely ambiguous max-plus-WTA over the ranked alphabet Γ. We join the automata we obtain for \(\mathcal {A}\) from Lemma 2 and Lemma 3 into a product automaton over the product semiring \(\mathbb {Q}_{\max \limits }^{M}\) as follows.

Lemma 4

We can effectively find an integer \(M \in \mathbb {N}\) and construct a trim WTA \(\mathcal {U} = ({Q}, {{\varGamma }}, {\mu }, {\nu })\) over \(\mathbb {Q}_{\max \limits }^{M}\) and Γ such that

• \(\boldsymbol {\mathcal {U}}\) is unambiguous,

• \({\mu }({\Delta }_{\mathcal {U}}) \subseteq \mathbb {Q}^{M} \boldsymbol {\cup } \{ (-\infty , \ldots , -\infty ) \}\) and \({\nu }({Q}) \subseteq \{ (0, \ldots , 0), (-\infty , \ldots , -\infty ) \}\), and

• for every t ∈ T_Γ we have \(\llbracket {\mathcal {A}}\rrbracket (t) = \max \limits _{i=1}^{M} \pi _{i}(\llbracket {\mathcal {U}}\rrbracket (t))\),

where \(\pi _{i} \colon \mathbb {Q}_{\max \limits }^{M} \to \mathbb {Q}_{\max \limits }\) is the projection to the i-th coordinate for every i ∈{1,…,M}.

Proof

By combining Lemma 2 and Lemma 3, we can find \(M \in \mathbb {N}\) and unambiguous max-plus-WTA \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{M}\) over Γ such that \(\llbracket {\mathcal {A}}\rrbracket = \max \limits _{i = 1}^{M} \llbracket {\mathcal {A}_{i}}\rrbracket \), \(\text {supp}(\mathcal {A}_{1}) = {\ldots } = \text {supp}(\mathcal {A}_{M})\), and such that with \(\mathcal {A}_{i} = ({Q}_{i}, {{\varGamma }}, {\mu }_{i}, {\nu }_{i})\), we have \({\nu }_{i}({Q}_{i}) \subseteq \{ 0, -\infty \}\) for every i ∈{1,…,M}. We define \({\mathcal {U}} = ({Q}, {{\varGamma }}, {{\mu }}, {{\nu }})\) as the trim part of the automaton \(\mathcal {U}^{\prime } = ({Q}^{\prime }, {{\varGamma }}, {\mu }^{\prime }, {\nu }^{\prime })\) defined as follows. We let \({Q}^{\prime } = {Q}_{1} \times {\ldots } \times {Q}_{M}\) and for a ∈Γ with rk_Γ(a) = m and \(p_{0}, \ldots , p_{m} \in {Q}^{\prime }\) with p_j = (p_j1,…,p_jM) we define, with x_i = μ_i(p_1i,…,p_mi, a, p_0i) and y_i = ν_i(p_0i),

It is easy to verify that \(\boldsymbol {\mathcal {U}}\) defined likes this satisfies all properties from the statement of the lemma. □

Let \(\boldsymbol {\mathcal {U}}\) be the automaton we obtain for \(\mathcal {A}\) from Lemma 4. For a tree t ∈ T_Γ, a Γ-word \(s \in T_{{{\varGamma }}_{{\diamond }}}\), runs \({r}_{t} \in \text {Run}_{{\mathcal {U}}}(t)\), \({r}_{s} \in \text {Run}_{{\mathcal {U}}}^{\diamond }(s)\), states p, q ∈ Q, and a coordinate i ∈{1,…,M}, we let \(\text {wt}_{i}(t,r_{t}) = \pi _{i}(\text {wt}_{\mathcal {U}}(t,r_{t}))\), \(\text {wt}{}_{i}^{{\diamond }}(s,r_{s}) = \pi _{i}(\text {wt}_{\mathcal {U}}^{{\diamond }}(s,r_{s}))\), and \(\text {wt}{}^{{\diamond }}_{i}(p,s,q) = \text {wt}_{i}^{{\diamond }}(s, r_{p}^{q})\) for the unique run \(r_{p}^{q} \in \text {Run}^{{\diamond }}_{\mathcal {U}}(p,s,q)\).

As we are still concerned with the rivals of the individual automata used to construct \(\boldsymbol {\mathcal {U}}\), we define in the following the concepts of rivals, reachers, distinguishers, and forks for \(\boldsymbol {\mathcal {U}}\).

Definition 2

Let i ∈{1,…,M}, p, q ∈ Q, t ∈ T_Γ, and \(r \in \text {Run}_{\mathcal {U}}(t)\).

• We call p and q i-rivals if there exists a tree u ∈ T_Γ such that \(\text {Run}_{\mathcal {U}}(u, p) \neq \emptyset \) and \(\text {Run}_{\mathcal {U}}(u, q) \neq \emptyset \) and a Γ-word s such that \(\text {Run}^{\diamond }_{{\mathcal {U}}}({p},s,{p}) \neq \emptyset \), \(\text {Run}^{{\diamond }}_{\mathcal {U}}(q,s,q) \neq \emptyset \), and \(\text {wt}{}^{{\diamond }}_{i}(p, s, p) \neq \text {wt}{}^{{\diamond }}_{i}(q,s,q)\). In this case, we also call u a p-q-reacher and s an i-p-q-distinguisher.

• We call a Γ-word f an i-p-q-fork if p and q are i-rivals, \(\text {Run}^{{\diamond }}_{\mathcal {U}}(p,f,p) \neq \emptyset \), and \(\text {Run}^{{\diamond }}_{\mathcal {U}}(p,f,q) \neq \emptyset \).

• We say that (t, r) is i-p-q-fork-broken if there exist positions w_p, w_q ∈pos(t) such that w_q <_pw_p, r(w_p) = p, r(w_q) = q, and \((t \langle {\diamond } \to w_{p} \rangle ) \!\!\upharpoonright _{w_{q}}\) is an i-p-q-fork.

• We say that (t, r) is i-p-q-split-broken if p and q are i-rivals and there exist two prefix-independent positions w_p, w_q ∈pos(t) with r(w_p) = p and r(w_q) = q.

When appropriate, we may drop some of the hyphenated modifiers from the terms above; for example, we will refer to (t, r) as i-fork-broken if there exist states p, q ∈ Q such that (t, r) is i-p-q-fork-broken and as i-split-broken if there exist states p, q ∈ Q such that (t, r) is i-p-q-split-broken. We call (t, r) i-broken if it is i-fork-broken or i-split-broken.

Our concept of brokenness is inspired by Bala’s notion of “broken paths” [26]. Of course, as his proof is concerned with words, the concept of split-brokenness does not exist. His notion of brokenness corresponds to our notion of fork-brokenness. Employing the notion of brokenness, Bala characterizes finite sequentiality of finitely ambiguous max-plus word automata using the A-Fork property. Translated to tree automata, the A-Fork property is defined as follows. We say that \(\boldsymbol {\mathcal {U}}\) satisfies the A-Fork property if for every constant C > 0, there exists a tree t ∈ T_Γ and an accepting run \(r \in \text {Acc}_{{\mathcal {U}}}(t)\) such that for some weight-maximal coordinate i, i.e., with \({\text {wt}}_{i}(t,r) = \max \limits _{j = 1}^{M} {\text {wt}}_{j}(t,r)\), we have that (t, r) is i-broken and for every coordinate j such that (t, r) is not j-broken, we have wt_j(t, r) < wt_i(t, r) − C. In other words, the A-Fork property is satisfied if broken coordinates are able to dominate non-broken coordinates by an arbitrarily large margin. Bala shows that a finitely ambiguous max-plus word automaton is finitely sequential if and only if the corresponding automaton \(\boldsymbol {\mathcal {U}}\) does not satisfy the A-Fork property.

For tree automata, however, this criterion does not capture finite sequentiality. More precisely, if we know that there do not exist a tree t and a run r on t such that (t, r) is split-broken, then the A-Fork property does capture finite sequentiality also for tree automata. However, if \(\boldsymbol {\mathcal {U}}\) satisfies the A-Fork property due to split-broken coordinates dominating non-broken coordinates, the behavior of \(\mathcal {A}\) may still be finitely sequential. This is evidenced by the following example.

Example 1

Consider the scenario for \(\boldsymbol {\mathcal {U}}\) as defined in Fig. 1. The support of \(\boldsymbol {\mathcal {U}}\) consists of all trees of the form \(c(b^{k}({a_{i}^{m}}(d_{i})), b^{l}({a_{j}^{n}}(d_{j})))\) with i, j ∈{1,2}, k, l > 0, and m, n ≥ 0. A valid run on such a tree necessarily assigns states from {p₁, p₂, p} to the left branch of the tree and states from {q₁, q₂, q} to the right branch of the tree. Moreover, if a branch begins with a letter d_i, this branch is assigned states from {p_i, q_i, p, q}. In particular, we see that \(\boldsymbol {\mathcal {U}}\) is unambiguous.

A scenario for the automaton \(\boldsymbol {\mathcal {U}}\): The automaton ({p₁, p₂, q₁, q₂, p, q,⊤},Γ, μ, ν) over the ranked alphabet Γ = {a₁, a₂, b, c, d₁, d₂} where c ∈Γ⁽²⁾, \(a_{1},a_{2},b \in {{\varGamma }}^{(1)}\), and \(d_{1},d_{2} \in {{\varGamma }}^{(0)}\). All unspecified weights are assumed to be \(-\infty \). The states p and q are 2-rivals

Full size image

The states p and q are 2-rivals as we see from the p-q-reacher u = b(a₁(d₁)) and the 2-p-q-distinguisher s = b(◇). By considering the trees \(t_{n} = c(b({a_{1}^{n}}(d_{1})), b({a_{2}^{n}}(d_{2})))\), we see that runs exist where p and q occur prefix-independently and the weight of coordinate 2 is arbitrarily larger than the weights of coordinates 1 and 3 since we have \(\llbracket {{\mathcal {U}}}\rrbracket (t_{n}) = (-n, 0, -n)\). However, in t_n the subtrees below p and q are distinct, thus a deterministic automaton can distinguish between them.

In fact, if \(\boldsymbol {\mathcal {U}}\) is given this way, we can construct a finitely sequential representation of \(\llbracket {\mathcal {A}}\rrbracket \) as follows. All trees of the form \(c(b^{k}({a_{1}^{m}}(d_{1})), b^{l}({a_{1}^{n}}(d_{1})))\) are assigned the weight (−m − n + k + l − 2,k − l, k + l − 2), so coordinate 3 is always dominant. Similarly, coordinate 1 is dominant for trees of the form \(c(b^{k}({a_{2}^{m}}(d_{2})), b^{l}({a_{2}^{n}}(d_{2})))\). These trees can be handled by the two deterministic max-plus-WTA obtained from \(\boldsymbol {\mathcal {U}}\) by removing the states q₁ and q₂, letting μ(p, p, c,⊤) = (0,0,0), and replacing μ with π₃ ∘ μ and π₁ ∘ μ, respectively. For trees of the form \(c(b^{k}({a_{1}^{m}}(d_{1})), b^{l}({a_{2}^{n}}(d_{2})))\), we remove the states p₂ and q₁ from \(\boldsymbol {\mathcal {U}}\) and then construct three deterministic max-plus-WTA by replacing μ by π₁ ∘ μ, π₂ ∘ μ, and π₃ ∘ μ, respectively. For the trees \(c(b^{k}({a_{2}^{m}}(d_{2})), b^{l}({a_{1}^{n}}(d_{1})))\) we can proceed similarly. The pointwise maximum of the automata constructed this way is then equivalent to \(\llbracket {\mathcal {A}}\rrbracket \). This example shows in particular that if \(\boldsymbol {\mathcal {U}}\) satisfies the A-Fork property, \(\llbracket {\mathcal {A}}\rrbracket \) can still be finitely sequential.

Our fundamental idea to adapt the A-Fork property to tree automata is to formulate our version not for \(\boldsymbol {\mathcal {U}}\) but for a covering of \(\boldsymbol {\mathcal {U}}\). Oversimplifying, a covering of an automaton is a new automaton obtained by enhancing the states of the original automaton with additional capacities to store information. A prominent example of a covering construction is the Schützenberger covering of an automaton. The Schützenberger covering in particular has already been employed in a number of decidability results for max-plus automata [10, 25, 26, 34, 42]. For more background on the Schützenberger covering and coverings in general, see [46].

Here, we construct from \({\mathcal {U}}\) an unambiguous automaton \({\boldsymbol {\mathcal {U}}}\) with the same behavior as \({\mathcal {U}}\) and whose states are tuples from \({Q} \times \mathcal {P}({Q} ) \times \mathcal {P}({Q}^{4} \times \mathcal {P}({Q}^{2} ) )\). Every run r of \({\boldsymbol {\mathcal {U}}}\) on a tree t ∈ T_Γ will correspond uniquely to a run of \({\mathcal {U}}\) on t, given by projecting to the first entry. For a position w, the second entry of r(w) will be the set of all states q ∈ Q which can be reached by \(t \!\!\upharpoonright _{w}\), i.e., for which \(\text {Run}_{{\mathcal {U}}}(t\!\!\upharpoonright _{w}, {q})\) is non-empty. The third entry of r(w) will consist of all tuples \(({p}, {q}, {p}^{\prime }, {q}^{\prime }, Y)\) such that (1) there exist runs \(r_{p} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{w}, p)\) and \(r_{q} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{w}, q)\) where (2) for some position below w, i.e., some position \(v \in \text {pos}(t \!\!\upharpoonright _{w})\), we have \(r_{p}(v) = p^{\prime }\) and \(r_{q}(v) = q^{\prime }\) and (3) Y is the set of all pairs of states (r_p(vu),r_q(vu)) with \(u \in \text {pos}(t\!\!\upharpoonright _{wv})\). Intuitively, the third entry of r(w) contains a tuple \((p, q, p^{\prime }, q^{\prime }, Y)\) if and only if \(t\!\!\upharpoonright _{w}\) can reach p and q with two runs r_p and r_q, these runs visited \(p^{\prime }\) and \(q^{\prime }\) simultaneously at some position v in the past, and Y consists of all pairs of states which these runs visited simultaneously up to v.

Our intention of considering the covering \({\boldsymbol {\mathcal {U}}}\) is to increase the knowledge we have about each pair of rivals. For two rivals of \({\mathcal {U}}\), all we know is what the definition of rivals specifies. For two rivals of \(\boldsymbol {\mathcal {U}}\) on the other hand, we will show that they are necessarily of the form (p, P, V ) and (q, P, V ) where p and q are rivals of \({\mathcal {U}}\). This allows us to infer statements about the rivals of \({\boldsymbol {\mathcal {U}}}\) which are not necessarily true for the rivals of \({\mathcal {U}}\). The precise construction of \(\boldsymbol {\mathcal {U}}\) is as follows.

Construction 1

We define \({\boldsymbol {\mathcal {U}}} = ({\mathbf {Q}}, {{\varGamma }}, {{\boldsymbol {\mu }}}, {{\boldsymbol {\nu }}})\) as the trim part of the automaton \({\boldsymbol {\mathcal {U}}}^{\prime } = ({\mathbf {Q}}^{\prime }, {{\varGamma }}, {{\boldsymbol {\mu }}}^{\prime }, {{\boldsymbol {\nu }}}^{\prime })\) defined as follows. We let \({\mathbf {Q}}^{\prime } = {Q} \times \mathcal {P}({Q} ) \times \mathcal {P}({Q}^{4} \times \mathcal {P}({Q}^{2} ) )\) and for subsets \(P_{1}, \ldots , P_{m} \subseteq {Q}\) and a letter a ∈Γ with rk_Γ(a) = m, we let

\(\text {succ}(P_{1}, \ldots , P_{m},a) = \{ q_{0} \mid \exists (q_{1}, \ldots , q_{m}) \in P_{1} \times {\ldots } \times P_{m} \text { with } {\mu }(q_{1}, \ldots , q_{m}, a, q_{0}) \in \mathbb {Q}^{M}\}\).

For i ∈{1,…,rk_Γ(a)} and a tuple \((p, q, p^{\prime }, q^{\prime }, Y) \in {Q}^{4} \times \mathcal {P}({Q}^{2})\), we let

\(\text {succ}(P_{1}, \ldots , P_{m},(p, q, p^{\prime }, q^{\prime }, Y),i,a) = \text {succ}(P_{1}, \ldots , P_{i-1}, \{ p \}, P_{i+1}, \ldots , P_{m}, a) \times \text {succ}(P_{1}, \ldots , P_{i-1}, \{ q \}, P_{i+1}, \ldots , P_{m}, a) \times \{ p^{\prime } \} \times \{ q^{\prime } \} \times \{Y\}\).

For \(V \subseteq {Q}^{4} \times \mathcal {P}({Q}^{2} )\) and p, q ∈ Q, we let

Then for a ∈Γ with rk_Γ(a) = m and \((p_{0}, P_{0}, V_{0}), \ldots , (p_{m}, P_{m}, V_{m}) \in {\mathbf {Q}}^{\prime }\), we define \({{\boldsymbol {\nu }}}^{\prime }(p_{0}, P_{0}, V_{0}) = {\nu }(p_{0})\) and

We let π₁: Q → Q, \(\pi _{2} \colon {\mathbf {Q}} \to \mathcal {P}(Q)\), and \(\pi _{3} \colon {\mathbf {Q}} \to \mathcal {P}({Q}^{4} \times \mathcal {P}({Q}^{2} ) )\) be the projections, and let wt_i and \({\mathbf {wt}}_{i}^{{\diamond }}\) be defined for \({\boldsymbol {\mathcal {U}}}\) in the same way we defined wt_i and \({\text {wt}}{}_{i}^{\diamond }\) for \({\mathcal {U}}\). Furthermore, we note that the concepts of rivals, reachers, distinguishers, and forks as defined for \({{\mathcal {U}}}\) in Definition 2 apply to \(\boldsymbol {\mathcal {U}}\) in a similar fashion.

We have the following lemma stating that \({\boldsymbol {\mathcal {U}}}\) indeed possesses the properties we described earlier.

Lemma 5

Let t ∈ T_Γ be a tree. Then the following statements hold.

1. (i)

   For every run \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\) and position w ∈pos(t), we have q ∈ π₂ ∘r(w) if and only if there exists a run \({r} \in \text {Run}_{{\mathcal {U}}}(t \!\!\upharpoonright _{w}, {q})\).

2. (ii)

   For every run \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\) and position w ∈pos(t), we have \((p, q, p^{\prime }, q^{\prime },Y) \in \pi _{3} \circ \mathbf {r}(w)\) if and only if there exist runs \({r}^{p} \in \text {Run}_{{\mathcal {U}}}(t \!\!\upharpoonright _{w}, {p})\) and \(r^{q} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{w}, q)\) such that for some \(v \in \text {pos}(t \!\!\upharpoonright _{w})\) we have \(r^{p}(v) = p^{\prime }\), \(r^{q}(v) = q^{\prime }\), and \(Y = \{ (r^{p}(vu), r^{q}(vu)) \in {Q}^{2} \mid u \in \text {pos}(t \!\!\upharpoonright _{wv})\}\).

3. (iii)

   The projection π₁ induces a bijection \(\pi _{1} \colon \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t) \to \text {Run}_{\mathcal {U}}(t)\) by r↦π₁ ∘r.

4. (iv)

   \({\boldsymbol {\mathcal {U}}}\) is trim, unambiguous, and satisfies \(\llbracket {{\boldsymbol {\mathcal {U}}}}\rrbracket = \llbracket {\mathcal {U}}\rrbracket \).

5. (v)

   Let p, q ∈Q be rivals. Then p and q are of the form (p, P, V ) and (q, P, V ), respectively, for two states p, q ∈ Q and sets \(P \subseteq {Q}, V \subseteq {Q}^{4} \times \mathcal {P}({Q}^{2} )\). Moreover, for every tree u ∈ T_Γ we have \(\text {Run}_{{\boldsymbol {\mathcal {U}}}}(u,{\mathbf {p}}) = \emptyset \) if and only if \(\text {Run}_{{\boldsymbol {\mathcal {U}}}}(u,{\mathbf {q}}) = \emptyset \).

Proof

(i) Let t ∈ T_Γ and \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\) and for contradiction, let w ∈pos(t) be a prefix-maximal position for which (i) does not hold. We deduce that (i) holds for w. We let a = t(w), m = rk_Γ(a), and write r(w) = (p₀, P₀, V₀) and r(wi) = (p_i, P_i, V_i) for i ∈{1,…,m}.

First, let q ∈ P₀, then there are states (q₁,…,q_m) ∈ P₁ ×… × P_m with \({\mu }(q_{1}, \ldots , q_{m}, a, q) \neq -\infty \). By assumption, for every i ∈{1,…,m} we find a run \(r_{i} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{wi}, q_{i})\). Then the quasi-run \(r \colon \text {pos}(t \!\!\upharpoonright _{w}) \to {Q}\) defined by r(ε) = q and r(iv) = r_i(v) is a run of \({\mathcal {U}}\) on \(t \!\!\upharpoonright _{w}\) with r(ε) = q.

On the other hand, let \(r \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{w}, q)\). Then for every i ∈{1,…,m} we have \(r \!\!\upharpoonright _{i} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{wi})\), so by assumption r(i) ∈ P_i. Moreover, \({\mu }(r(1), \ldots , r(m), a, q) \neq -\infty \), so q ∈ P₀. Thus, (i) holds for w, which is a contradiction, so w does not exist.

(ii) Let t ∈ T_Γ and \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\) and for contradiction, let w ∈pos(t) be a prefix-maximal position for which Lemma 5 does not hold. We deduce that (ii) holds for w. We let a = t(w), m = rk_Γ(a), and write \({\mathbf {r}}(w) = (p_{0}^{\prime \prime },P_{0},V_{0})\) and \({\mathbf {r}}(wi) = (p_{i}^{\prime \prime }, P_{i}, V_{i})\) for i ∈{1,…,m}. Furthermore, we let \(V = \bigcup _{i = 1}^{m} \bigcup _{({p}, {q}, {p}^{\prime }, {q}^{\prime }, Y) \in V_{i}} \text {succ}(P_{1}, \ldots , P_{m},(p, q, p^{\prime }, q^{\prime }, Y),i,a)\).

We first make the following observation. If \((p, q, p^{\prime }, q^{\prime }, Y) \in V\), then for some i ∈{1,…,m} and \((p_{i}, q_{i}, p^{\prime }, q^{\prime }, Y) \in V_{i}\) we have \((p, q, p^{\prime }, q^{\prime }, Y) \in \text {succ}(P_{1}, \ldots , P_{m},(p_{i}, q_{i}, p^{\prime }, q^{\prime }, Y),i,a)\). Thus, there exist (p₁,…,p_i− 1, p_i+ 1,…,p_m),(q₁,…,q_i− 1, q_i+ 1,…,q_m) ∈ P₁×…×P_i− 1×P_i+ 1×…×P_m with \({\mu }(p_{1}, \ldots , p_{m}, a, p) \in \mathbb {Q}^{M}\) and \({\mu }(q_{1}, \ldots , q_{m}, a, q) \in \mathbb {Q}^{M}\). By Lemma 5, there exist runs \(r^{p}_{j} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{wj}, p_{j})\) and \(r^{q}_{j} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{wj}, q_{j})\) for every j ∈{1,…,m}∖{i}. Furthermore, we assume that (ii) holds for wi, so there exist runs \(r^{p}_{i} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{wi}, p_{i})\) and \(r^{q}_{i} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{wi}, q_{i})\) and a position \(v \in \text {pos}(t \!\!\upharpoonright _{wi})\) with \(r^{p}_{i}(v) = p^{\prime }\), \(r^{q}_{i}(v) = q^{\prime }\), and \(Y = \{ (r^{p}_{i}(vu), r^{q}_{i}(vu)) \in {Q}^{2} \mid u \in \text {pos}(t \!\!\upharpoonright _{wiv})\}\). Thus, for the runs r^p and r^q defined by r^p(ε) = p, r^q(ε) = q, \(r^{p}(ju) = r^{p}_{j}(u)\), and \(r^{q}(ju) = r^{q}_{j}(u)\) for every position \(ju \in \text {pos}(t \!\!\upharpoonright _{w})\), we have \(r^{p}(iv) = p^{\prime }\), \(r^{q}(iv) = q^{\prime }\), and \(Y = \{ (r^{p}(ivu), r^{q}(ivu)) \in {Q}^{2} \mid u \in \text {pos}(t \!\!\upharpoonright _{wiv})\}\).

♣ Now let \((p, q, p^{\prime }, q^{\prime }, Y) \in V_{0}\). If \((p, q, p^{\prime }, q^{\prime }, Y) \in V\), Lemma 5 follows easily from the observation above. If \((p, q, p^{\prime }, q^{\prime }, Y) = (p, q, p, q, Y)\) with p, q ∈ P₀ and Y = visited(p, q, V )∪{(p, q)}, we see by (i) that there exist runs \(r^{p} \in \text {Run}_{\mathcal {U}}\)(\(t \!\!\upharpoonright _{w}\), p) and \(r^{q} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{w}, q)\). We show that Y ={\( (r^{p}(u), r^{q}(u)) \in {Q}^{2} \mid u \in \text {pos}(t \!\!\upharpoonright _{w})\)}.

Let \((p^{\prime }, q^{\prime }) \in Y\). If \((p^{\prime }, q^{\prime }) = (p, q)\), we have \((p^{\prime }, q^{\prime }) = (r^{p}(\varepsilon ), r^{q}(\varepsilon ))\). Otherwise, there exists \(Y^{\prime } \subseteq {Q}^{2}\) with \(({p},{q},{p}^{\prime },{q}^{\prime },Y^{\prime }) \in V\). The observation above together with the unambiguity of \(\boldsymbol {\mathcal {U}}\) then yields i ∈{1,…,m} and \(v \in \text {pos}(t \!\!\upharpoonright _{wi})\) with \((r^{p}(iv),r^{q}(iv)) = (p^{\prime },q^{\prime })\).

Now let \(u \in \text {pos}(t \!\!\upharpoonright _{w})\), p_i = r^p(i), and q_i = r^q(i) for every i ∈{1,…,m}. For every i ∈{1,…,m}, we have \(r^{p} \!\!\upharpoonright _{i}, r^{q} \!\!\upharpoonright _{i} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{wi})\), so we have p_i, q_i ∈ P_i by Lemma 5. For u = ε, we have (r^p(u),r^q(u)) = (p, q) ∈ Y. Otherwise, we have u = iv for some i ∈{1,…,m}. It follows that \(({r}^{p}(u), {r}^{q}(u)) = ({r}^{p}\!\!\upharpoonright _{i}(v), {r}^{q}\!\!\upharpoonright _{i}(v))\). We assume that (ii) holds for wi, so we have \(({p}_{i},{q}_{i},{r}^{p}(u), {r}^{q}(u),Y^{\prime }) \in V_{i}\) for some \(Y^{\prime } \subseteq {Q}^{2}\). Since \({{\mu }}({p}_{1}, \ldots , {p}_{m}, a, {p}) \in \mathbb {Q}^{M}\) and \({\mu }(q_{1}, \ldots , q_{m}, a, q) \in \mathbb {Q}^{M}\), we see that \((p,q,r^{p}(u), r^{q}(u),Y^{\prime }) \in V\). In particular, we have \(({r}^{p}(u), {r}^{q}(u)) \in \text {visited}({p}, {q}, V) \subseteq Y\).

♣ Conversely, we let \((p,q,p^{\prime },q^{\prime },Y) \in {Q}^{4} \times \mathcal {P}(Q^{2})\) satisfying that there exist runs \(r^{p} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{w}, p)\) and \(r^{q} \in \text {Run}_{\mathcal {U}}(t \!\!\upharpoonright _{w}, q)\) such that for some \(v \in \text {pos}(t \!\!\upharpoonright _{w})\) we have \(r^{p}(v) = p^{\prime }\), \(r^{q}(v) = q^{\prime }\), and \(Y = \{ (r^{p}(vu), r^{q}(vu)) \in {Q}^{2} \mid u \in \text {pos}(t \!\!\upharpoonright _{wv})\}\). We let p_i = r^p(i) and q_i = r^q(i) for i ∈{1,…,m}. For v≠ε, we have \(v = iv^{\prime }\) for some i ∈{1,…,m}. We assume that Lemma 5 holds for wi, so we have \(({p}_{i}, {q}_{i}, {p}^{\prime }, {q}^{\prime }, Y) \in V_{i}\). By (i), we see that (p₁,…,p_m),(q₁,,…,q_m) ∈ P₁ ×… × P_m, so \((p,q, p^{\prime }, q^{\prime }, Y) \in \text {succ}(P_{1}, \ldots , P_{m},(p_{i}, q_{i}, p^{\prime }, q^{\prime }, Y),i,a) \subseteq V_{0}\).

For v = ε, we note that we have (p, q, p, q,visited(p, q, V )∪{(p, q)}) ∈ V₀. We show Y = visited(p, q, V )∪{(p, q)}. Let \(u \in \text {pos}(t \!\!\upharpoonright _{w})\). For u = ε, we have (r^p(u),r^q(u)) = (p, q). Otherwise, we have \(u = iu^{\prime }\) for some i ∈{1,…,m}. We assume that (ii) holds for wi, so for some \(Y^{\prime } \subseteq {Q}^{2}\) we have \(({p}_{i},{q}_{i},{r}^{p}(u), {r}^{q}(u),Y^{\prime }) \in V_{i}\). It follows that \(({p},{q},{r}^{p}(u), {r}^{q}(u),Y^{\prime }) \in V\), so (r^p(u),r^q(u)) ∈visited(p, q, V ). On the other hand, for \(({p}^{\prime \prime },{q}^{\prime \prime }) \in \text {visited}({p}, {q}, V)\), there exists \(({p}, {q}, {p}^{\prime \prime }, {q}^{\prime \prime }, Y^{\prime }) \in V\). The observation above together with the unambiguity of \({\mathcal {U}}\) thus yields i ∈{1,…,m} and \(v^{\prime } \in \text {pos}(t \!\!\upharpoonright _{wi})\) with \((r^{p}(iv^{\prime }),r^{q}(iv^{\prime })) = (p^{\prime \prime },q^{\prime \prime })\).

(iii) ow Let t ∈ T_Γ. By definition of μ, it is clear that for \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\) we have \(\pi _{1} \circ {\mathbf {r}} \in \text {Run}_{\mathcal {U}}(t)\). The injectivity of \(\pi _{1} \colon \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t) \to \text {Run}_{\mathcal {U}}(t)\) follows from (i) and (ii), as all runs on t coincide on their second and third entries. For surjectivity, note that given a run \(r \in \text {Run}_{\mathcal {U}}(t)\), the definition of μ provides an obvious way to define a run \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\) with π₁ ∘r = r.

(iv) \({\boldsymbol {\mathcal {U}}}\) is trim by definition. Let t ∈ T_Γ. By definition of μ, for every run \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\) we have \(\text {wt}_{{\boldsymbol {\mathcal {U}}}}(t, {\mathbf {r}}) = \text {wt}_{\mathcal {U}}(t, \pi _{1} \circ {\mathbf {r}})\). By definition of ν, we also have ν(r(ε)) = ν(π₁ ∘r(ε)). By (iii), we thus have \(|\text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t)| = |\text {Acc}_{\mathcal {U}}(t)| \leq 1\), which means that \({\boldsymbol {\mathcal {U}}}\) is unambiguous, and \(\llbracket {\boldsymbol {\mathcal {U}}}\rrbracket (t) = \llbracket {{\mathcal {U}}}\rrbracket (t)\).

(v) Let p, q ∈Q be rivals and let u ∈ T_Γ be a p-q-reacher. Then there exist runs \({\mathbf {r}}^{p} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(u, {\mathbf {p}})\) and \({\mathbf {r}}^{q} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(u, {\mathbf {q}})\). We write p = (p, P_p, V_p) and q = (q, P_q, V_q). From (i) and Lemma (ii), we obtain \(P_{p} = \pi _{2} \circ \mathbf {r}^{p}(\varepsilon ) = \pi _{2} \circ \mathbf {r}^{q}(\varepsilon ) = P_{q}\) and \(V_{p} = \pi _{3} \circ {\mathbf {r}}^{p}(\varepsilon ) = \pi _{3} \circ {\mathbf {r}}^{q}(\varepsilon ) = V_{q}\). Moreover, by (i), we see that p ∈ P_p and q ∈ P_q.

For the second statement, let u ∈ T_Γ such that \({\mathbf {r}}^{p} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(u, {\mathbf {p}})\) exists. Since q ∈ P_q = P_p, we see by (i) that there exists a run \(r^{q} \in \text {Run}_{\mathcal {U}}(u, q)\). By (iii), there thus exists a run \({\mathbf {r}}^{q} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(u)\) with \(\pi _{1} \circ {\mathbf {r}}^{q}(\varepsilon ) = q\). From (i) and Lemma (ii), we obtain \(\pi _{2} \circ {\mathbf {r}}^{q}(\varepsilon ) = P_{p} = P_{q}\) and \(\pi _{3} \circ {\mathbf {r}}^{q}(\varepsilon ) = V_{p} = V_{q}\), so we have r^q(ε) = q. By symmetry, the stated equivalence holds. □

Finally, we introduce our version of the A-Fork property. To allow for easier proofs, we use a different formulation and consequently a different name. But in fact, \({\boldsymbol {\mathcal {U}}}\) satisfies the separation property if and only if it satisfies the A-Fork property in the way we translated it to trees earlier.

Definition 3

Let \(C \in \mathbb {N}\). We call a set \(I \subseteq \{1, \ldots , M\}\) C-separable if there exists a tree t ∈ T_Γ and a run \({\mathbf {r}} \in \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t)\) such that

1. (i)

   if i ∈ I, then (t, r) is i-broken and

2. (ii)

   if j ∈{1,…,M}∖ I, then wt_j(t, r) ≤wt_i(t, r) − C for all i ∈ I.

In this case, we also say that (t, r) is I-C-separated. We call I separable if it is C-separable for every \(C \in \mathbb {N}\) and define \(\mathcal {I}\) as the set of all separable subsets \(I \subseteq \{1, \ldots , M\}\). If \(\mathcal {I}\) is non-empty, we say that \(\boldsymbol {\mathcal {U}}\) satisfies the separation property or, for short, that \(\boldsymbol {\mathcal {U}}\) is broken.

Our main result is to prove the following theorem relating the separation property to the finite sequentiality problem of finitely ambiguous max-plus-WTA.

Theorem 2

The behavior \(\llbracket {\mathcal {A}}\rrbracket \) of \(\mathcal {A}\) is finitely sequential if and only if \({\boldsymbol {\mathcal {U}}}\) is not broken. Moreover, it is decidable whether \({\boldsymbol {\mathcal {U}}}\) is broken. In particular, it is decidable whether \(\llbracket {\mathcal {A}}\rrbracket \) is finitely sequential.

We separate the proof of Theorem 2 into three parts. We show in Section 3.1 that it is decidable whether \({\boldsymbol {\mathcal {U}}}\) is broken. In Section 3.2, we show that if \(\boldsymbol {\mathcal {U}}\) is broken, then \(\llbracket {\mathcal {A}}\rrbracket \) is not finitely sequential. Finally, in Section 3.3, we show how to construct finitely many deterministic max-plus-WTA whose pointwise maximum is equivalent to \(\llbracket {\mathcal {A}}\rrbracket \) in case that \({\boldsymbol {\mathcal {U}}}\) is not broken.

For all of our proofs, it will be crucial that for every two states of \({\boldsymbol {\mathcal {U}}}\), we can decide whether they are rivals [47, Section 4], [48, Section 5.4]. For two rivals of an unambiguous automaton, it is in fact quite easy to give an upper bound on the size of their smallest distinguisher. The same applies to reachers and forks. Thus, deciding whether two states are rivals reduces to checking for finitely many trees whether they can reach both states and checking for finitely many Γ-words whether they are a distinguisher for these two states. For Section 3.3, we require an even more precise statement, namely that if s is a distinguisher for two rivals p and q, then we can obtain a p-q-distinguisher of height at most 4|Q|² by removing loops from the unique runs looping in p and q. For this, we employ the notion of a truncation. Simply put, for a Γ-word s and a run r on s, a truncation of (s, r) is any pair \((s^{\prime },{\mathbf {r}}^{\prime })\) of a Γ-word \(s^{\prime }\) and a run \({\mathbf {r}}^{\prime }\) on \(s^{\prime }\) which can be obtained by repeatedly cutting loops from (s, r).

Definition 4

Let \(s,s^{\prime } \in T_{{{\varGamma }}_{{\diamond }}}\) be Γ-words, \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}(s)\), and \({\mathbf {r}}^{\prime } \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}(s^{\prime })\). We say that \((s^{\prime }, {\mathbf {r}}^{\prime })\) is a truncation of (s, r), denoted by , if there exists a mapping \(g \colon \text {pos}(s^{\prime }) \to \text {pos}(s)\) such that g(ε) = ε, \(g({\Diamond }_{1}(s^{\prime })) = {\Diamond }_{1}(s)\), and for all \(w \in \text {pos}(s^{\prime })\) and \(l \in \text {rk}_{{{\varGamma }}_{{\diamond }}}(s^{\prime }(w))\) we have \(\mathbbm {t}(s^{\prime },{\mathbf {r}}^{\prime },w) = \mathbbm {t}(s,{\mathbf {r}},g(w))\) and g(w)l ≤_pg(wl).

We observe as follows that removing a loop from a pair (s, r) yields a truncation, that “being a truncation of” is a transitive relation, and that every truncation is the result of removing loops from a pair (s, r).

Lemma 6

Let \(s \in T_{{{\varGamma }}_{{\diamond }}}\) be a Γ-word and \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}(s)\), then the following holds.

1. (i)

   For every two positions w₁, w₂ ∈pos(s) with w₁ ≤_pw₂ and r(w₁) = r(w₂) and \((s^{\prime },{\mathbf {r}}^{\prime }) = (s,{\mathbf {r}})\langle (s,{\mathbf {r}}) \!\!\upharpoonright _{w_{2}} \to w_{1} \rangle \), we have by defining \(g \colon \text {pos}(s^{\prime }) \to \text {pos}(s)\) through g(w) = w₂v if w = w₁v for some \(v \in \mathbb {N}^{*}\) and g(w) = w otherwise.

2. (ii)

   If and , then by concatenating the mappings \(g \colon \text {pos}(s^{\prime }) \to \text {pos}(s)\) and \(g^{\prime } \colon \text {pos}(s^{\prime \prime }) \to \text {pos}(s^{\prime })\) to \(g \circ g^{\prime } \colon \text {pos}(s^{\prime \prime }) \to \text {pos}(s)\).

3. (iii)

   If and \(g \colon \text {pos}(s^{\prime }) \to \text {pos}(s)\) a respective mapping, then \(\text {wt}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}(s, {\mathbf {r}}) = \text {wt}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}(s^{\prime }, {\mathbf {r}}^{\prime }) + {\sum }_{w \in \text {pos}(s^{\prime })} {\sum }_{l = 1}^{\text {rk}_{{{\varGamma }}_{{\diamond }}}(s^{\prime }(w))} \text {wt}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}((s, {\mathbf {r}}) \langle ({\diamond }, {\mathbf {r}}(g(wl))) \to g(wl) \rangle \!\!\upharpoonright _{g(w)l})\).

Proof

(ii) We only show the last condition for \(g \circ g^{\prime }\). Let \(s \in \text {pos}(s^{\prime \prime })\) and l ∈ \(\text {rk}_{{{\varGamma }}_{{\diamond }}}(s^{\prime \prime }(w))\), then \(g^{\prime }(w)l \leq _{\textsc {p}} g^{\prime }(wl)\), so \(g^{\prime }(wl) = g^{\prime }(w)l l_{1} {\cdots } l_{n}\). It follows that \(g(g^{\prime } (w))l\leq _{\textsc {p}} g(g^{\prime }(w)l) \leq _{\textsc {p}} g(g^{\prime }(w)l) l_{1} \leq _{\textsc {p}} g(g^{\prime }(w)l l_{1}) \leq _{\textsc {p}} {\ldots } \leq _{\textsc {p}} g(g^{\prime }(w)l l_{1} {\cdots } l_{n}) = g(g^{\prime }(wl))\).

(iii) First, we show that g is injective. Let \(v^{\prime },w^{\prime } \in \text {pos}(s^{\prime })\) with \(v^{\prime } \neq w^{\prime }\), let \(u^{\prime }\) be the longest common prefix of \(v^{\prime }\) and \(w^{\prime }\), and let \(v^{\prime } = u^{\prime } k_{1} {\cdots } k_{m}\) and \(w^{\prime } = u^{\prime } l_{1} {\cdots } l_{n}\). Then \(g(u^{\prime }) k_{1} \leq _{\textsc {p}} g(u^{\prime } k_{1}) \leq _{\textsc {p}} g(u^{\prime } k_{1}) k_{2} \leq _{\textsc {p}} g (u^{\prime } k_{1} k_{2}) \leq _{\textsc {p}} {\ldots } \leq _{\textsc {p}} g(u^{\prime } k_{1} {\cdots } k_{m}) = g(v^{\prime })\) and similarly \(g(u^{\prime }) l_{1} \leq _{\textsc {p}} g(w^{\prime })\). If \(v^{\prime } <_{\textsc {p}} w^{\prime }\), we have \(g(v^{\prime }) l_{1} \leq _{\textsc {p}} g(w^{\prime })\), so \(g(v^{\prime }) \neq g(w^{\prime })\). If \(v^{\prime }\) and \(w^{\prime }\) are prefix-independent, we obtain \(g(v^{\prime }) \neq g(w^{\prime })\) from k₁≠l₁.

Now let w ∈pos(s) with \(w \notin g(\text {pos}(s^{\prime }))\). We show that there exists exactly one \(w^{\prime } \in \text {pos}(s^{\prime })\) with \(g(w^{\prime }) \leq _{\textsc {p}} w\) and \(\lnot (g(w^{\prime }k) \leq _{\textsc {p}} w)\), where \(k \in \{1, \ldots , \text {rk}_{{{\varGamma }}_{{\diamond }}}(s^{\prime }(w^{\prime }))\}\) is such that \(g(w^{\prime })k \leq _{\textsc {p}} w\). Let \(w^{\prime } \in \text {pos}(s^{\prime })\) such that \(g(w^{\prime })\) is prefix-maximal in the set \(\{v \in g(\text {pos}(s^{\prime })) \mid v \leq _{\textsc {p}} w\}\); note that this set is non-empty due to g(ε) = ε ≤_pw. Since \(w \notin g(\text {pos}(s^{\prime }))\), we have \(g(w^{\prime })k \leq _{\textsc {p}} w\) for some \(k \in \{1, \ldots , \text {rk}_{{{\varGamma }}_{{\diamond }}}(s^{\prime }(w^{\prime }))\}\), and since \(g(w^{\prime })\) is prefix-maximal and \(g(w^{\prime }) <_{\textsc {p}} g(w^{\prime })k \leq _{\textsc {p}} g(w^{\prime }k)\), we have \(\lnot (g(w^{\prime }k) \leq _{\textsc {p}} w)\).

Now assume that \(v^{\prime } \in \text {pos}(s^{\prime })\) with \(g(v^{\prime }) \leq _{\textsc {p}} w\) and \(v^{\prime } \neq w^{\prime }\) and let \(l \in \{1, \ldots , \text {rk}_{{{\varGamma }}_{{\diamond }}}(s^{\prime }(v^{\prime }))\}\) such that \(g(v^{\prime })l \leq _{\textsc {p}} w\). We show that \(g(v^{\prime }l) \leq _{\textsc {p}} g(w^{\prime })\) which together with \(g(w^{\prime }) \leq _{\textsc {p}} w\) implies \(g(v^{\prime }l) \leq _{\textsc {p}} w\). For the longest common prefix \(u^{\prime }\) of \(v^{\prime }\) and \(w^{\prime }\), we have \(v^{\prime } = u^{\prime }k_{1} {\cdots } k_{m}\) and \(w^{\prime } = u^{\prime } l_{1} {\cdots } l_{n}\). As above, it follows that \(g(u^{\prime })k_{1} \leq _{\textsc {p}} g(v^{\prime })\) and \(g(u^{\prime })l_{1} \leq _{\textsc {p}} g(w^{\prime })\). Since \(g(v^{\prime }) \leq _{\textsc {p}} w\) and \(g(w^{\prime }) \leq _{\textsc {p}} w\), both \(g(v^{\prime })\) and \(g(w^{\prime })\) are prefix-dependent, so this can only hold if either m = 0 or n = 0. For n = 0, the prefix-maximal choice of \(g(w^{\prime })\) implies \(g(w^{\prime }) = g(u^{\prime }) <_{\textsc {p}} g(u^{\prime }) k_{1} \leq _{\textsc {p}} g(v^{\prime }) \leq _{\textsc {p}} g(w^{\prime })\), so m = 0 holds. From \(g(v^{\prime })l_{1} = g(u^{\prime })l_{1} \leq _{\textsc {p}} g(w^{\prime }) \leq _{\textsc {p}} w\) and \(g(v^{\prime })l \leq _{\textsc {p}} w\), we see that l₁ = l. We obtain \(g(v^{\prime }l) = g(u^{\prime }l_{1}) \leq _{\textsc {p}} g(u^{\prime }l_{1}) l_{2} \leq _{\textsc {p}} g(u^{\prime } l_{1} l_{2}) \leq _{\textsc {p}} {\ldots } \leq _{\textsc {p}} g(u^{\prime }l_{1} {\cdots } l_{n}) = g(w^{\prime })\).

♣ Due to the injectivity of g, we obtain

Let \(w^{\prime } \in \text {pos}(s^{\prime })\), \(l \in \{1, \ldots , \text {rk}_{{{\varGamma }}_{{\diamond }}}(s^{\prime }(w^{\prime }))\}\), and \(W(w^{\prime },l) = \{ w \in \text {pos}(s) \mid g(w^{\prime })l \leq _{\textsc {p}} w \land \lnot (g(w^{\prime }l) \leq _{\textsc {p}} w) \}\). We have

By the observation above, we have \(\text {pos}(s) \setminus g(\text {pos}(s^{\prime })) = \bigcup _{w^{\prime } \in \text {pos}(s^{\prime })} \bigcup _{l = 1}^{\text {rk}_{{{\varGamma }}_{{\diamond }}}(s^{\prime }(w^{\prime }))} W(w^{\prime },l)\) and this union is disjoint. We obtain

□

We can use truncations to bound the size of distinguishers as follows.

Lemma 7

[48, Lemma 5.10], [34] Let p, q ∈Q be i-rivals for some i ∈{1,…, M}, let \(s \in T_{{{\varGamma }}_{{\diamond }}}\) be an i-p-q-distinguisher, and let \(\mathbf {r}_{\mathbf {p}} \in \text {Run}^{\diamond }_{\boldsymbol {\mathcal {U}}}(\mathbf {p},s,\mathbf {p})\) and \({\mathbf {r}}_{{\mathbf {q}}} \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {q}},s,{\mathbf {q}})\). Then there exists an i-p-q-distinguisher \(s^{\prime }\) with \(\text {height}(s^{\prime }) \leq 4|\mathbf {Q}|^{2}\) such that for the runs \({\mathbf {r}}_{{\mathbf {p}}}^{\prime } \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {p}},s^{\prime },{\mathbf {p}})\) and \({\mathbf {r}}_{{\mathbf {q}}}^{\prime } \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {q}},s^{\prime },{\mathbf {q}})\), \((s^{\prime },{\mathbf {r}}_{{\mathbf {p}}}^{\prime })\) is a truncation of (s, r_p) and \((s^{\prime },{\mathbf {r}}_{{\mathbf {q}}}^{\prime })\) is a truncation of (s, r_q).

Proof

Let p, q, s, r_p, r_q be as in the statement of the lemma. If height(s) ≤ 4|Q|², the statement is clear as both (s, r_p) and (s, r_q) are each truncations of themselves. Otherwise, we let w ∈pos(s) such that |w| = height(s) > 4|Q|² and we let \(w^{\prime } \in \text {pos}(s)\) be the longest common prefix of w and ◊₁(s). Then either \(|w^{\prime }| > 2|\mathbf {Q}|^{2}\) or \(|w|-|w^{\prime }| > 2|\mathbf {Q}|^{2}\), or both. In the first case, there exist two disjoint simultaneous loops in r_p and r_q above ◊₁(s). More precisely, by pigeonhole principle we can find positions w₁ <_pw₂ ≤_pw₃ <_pw₄ with \(w_{4} \leq _{\textsc {p}} w^{\prime } \leq _{\textsc {p}} {\Diamond }_{1}(s)\) for which (r_p(w₁),r_q(w₁)) = (r_p(w₂),r_q(w₂)) and (r_p(w₃),r_q(w₃)) = (r_p(w₄),r_q(w₄)). In the second case, there exist two disjoint simultaneous loops in r_p and r_q which are prefix-independent from ◊₁(s). That is, there exist positions w₁ <_pw₂ ≤_pw₃ <_pw₄ with \(w^{\prime } <_{\textsc {p}} w_{1}\) and w₄ ≤_pw in pos(s) for which (r_p(w₁),r_q(w₁)) = (r_p(w₂),r_q(w₂)) and (r_p(w₃),r_q(w₃)) = (r_p(w₄),r_q(w₄)).

We let \(x = \text {wt}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}(s, {\mathbf {r}}_{{\mathbf {p}}})\) and \(y = \text {wt}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}(s, {\mathbf {r}}_{{\mathbf {q}}})\), we let x₁₂ and x₃₄ be the weights of the loops in the run r_p, and we let y₁₂ and y₃₄ be the weights of the loops in the run r_q. We obtain truncations of (s, r_p) and (s, r_q) by removing either one of the two loops or both loops as follows. If x − x₁₂≠y − y₁₂, we remove the w₁-w₂ loop by \((s,{\mathbf {r}}_{{\mathbf {p}}})\langle (s,{\mathbf {r}}_{{\mathbf {p}}}) \!\!\upharpoonright _{w_{2}} \to w_{1} \rangle \) and \((s,{\mathbf {r}}_{{\mathbf {q}}})\langle (s,{\mathbf {r}}_{{\mathbf {q}}}) \!\!\upharpoonright _{w_{2}} \to w_{1} \rangle \). Otherwise, if x − x₃₄≠y − y₃₄, we remove the w₃-w₄ loop in the same fashion. If we have both x − x₁₂ = y − y₁₂ and x − x₃₄ = y − y₃₄, we obtain that 2x − x₁₂ − x₃₄ = 2y − y₁₂ − y₃₄. From x≠y, it follows that x − x₁₂ − x₃₄≠y − y₁₂ − y₃₄, so we remove both loops. We continue this procedure until we arrive at truncations of height at most 4|Q|². The transitivity of truncations ensures that the distinguisher and runs we obtain eventually are indeed truncations of the original distinguisher and runs. □

Using similar arguments, we can also bound the sizes of reachers and forks.

Lemma 8 (34)

Let p, q ∈Q be rivals, u ∈ T_Γ be a p-q-reacher, and \(f \in T_{{{\varGamma }}_{{\diamond }}}\) be a p-q-fork. Then there exists a p-q-reacher \(u^{\prime }\) with \(\text {height}(u^{\prime }) \leq |{\mathbf {Q}}|^{2}\) and a p-q-fork \(f^{\prime }\) with \(\text {height}(f^{\prime }) \leq 2|\mathbf {Q}|^{2}\). In particular, for every two states p, q ∈Q, it is decidable whether p and q are rivals.

3.1 Decidability

In this section, we show that it is decidable whether \({\boldsymbol {\mathcal {U}}}\) is broken. For this, we employ Parikh’s Theorem and the decidability of the satisfiability of systems of linear inequalities over the rationals with integer solutions [37, 38]. Note that this part of the proof does not follow any idea from [26] as in his proof, Bala reduces the decidability of the A-Fork property to the decidability of a decidable fragment of Presburger arithmetic. We begin by recalling Parikh’s Theorem and the concepts it involves.

Let Σ = {a₁,…,a_n} be an alphabet. The Parikh vector \(\mathbbm {p}(w) \in \mathbb {N}^{n}\) of a word w ∈Σ^∗ is the vector \(\mathbbm {p}(w) = (|w|_{a_{1}}, |w|_{a_{2}}, \ldots , |w|_{a_{n}})\). For a language \(L \subseteq {{\varSigma }}^{*}\), the Parikh image of L is the set \(\mathbbm {p}(L) = \{ \mathbbm {p}(w) \mid w \in L \}\).

A set of vectors \(J \subseteq \mathbb {N}^{n}\) is called linear if there exist k ≥ 0, a vector α, and a matrix \(\beta \in \mathbb {N}^{n \times k}\) such that

The set J is called semilinear if it is the union of finitely many linear subsets of \(\mathbb {N}^{n}\).

A context-free grammar (short: CFG) [49] is a tuple (N, Σ, P, S) where (1) N is a finite set of nonterminal symbols, (2) Σ is a finite set of terminal symbols with N ∩Σ = ∅, (3) \(P \subseteq N \times (N \boldsymbol {\cup } {{\varSigma }})^{*}\) is a finite set of productions or rules, and (4) S ∈ N is the initial symbol. We usually denote a rule (A, w) ∈ P by A → w.

Let G = (N, Σ, P, S) be a context-free grammar. For u, v ∈ (N∪Σ)^∗ we write u ⇒_Gv if there exists \(u^{\prime },u^{\prime \prime } \in (N \boldsymbol {\cup } {{\varSigma }})^{*}\) and a production A → w ∈ P such that \(u = u^{\prime } A u^{\prime \prime }\) and \(v = u^{\prime } w u^{\prime \prime }\). The language generated by G is the language \({\mathscr{L}}(G) =\)

A language \(L \subseteq {{\varSigma }}^{*}\) is called context-free if there exists a context-free grammar G with \(L = {\mathscr{L}}(G)\). By Parikh’s Theorem, the Parikh image of every context-free language is semilinear.

Theorem 3

[35, Theorem 2], [36] For every context-free language L, the set \(\mathbbm {p}(L)\) is semilinear. Furthermore, integers k, k₁,…,k_k, vectors α^(l), and matrices \(\beta ^{(l)} \in \mathbb {N}^{n \times k_{l}} (l \in \{1, \ldots , k\})\) with

can be effectively found from every context-free grammar generating L.

We will employ Parikh’s Theorem to show that the image \(\llbracket {{\boldsymbol {\mathcal {U}}}}\rrbracket (T_{{{\varGamma }}} )\) of T_Γ under \(\llbracket {{\boldsymbol {\mathcal {U}}}}\rrbracket \) is the image of a semilinear set under a matrix over the rationals. From this matrix, we will be able to infer a constant \(\tilde {C}\) such that every set \(I \subseteq \{1, \ldots , M\}\) is separable if and only if it is \(\tilde {C}\)-separable. We then reduce the \(\tilde {C}\)-separability of such a set I to deciding the satisfiability of finitely many systems of inequalities over the rationals with an integer solution. As the latter problem is decidable [37, 38], deciding the brokenness of \(\boldsymbol {\mathcal {U}}\) boils down to deciding the \(\tilde {C}\)-separability of every set \(I \subseteq \{1, \ldots , M\}\). We will employ the following notion of the Parikh image of an automaton.

In the following, let \({\mathscr{B}} = ({Q}_{{\mathscr{B}}}, {{\varGamma }}, {\mu }_{{\mathscr{B}}}, {\nu }_{{\mathscr{B}}})\) be a WTA over a commutative semiring and Γ and let d₁,…,d_D be an enumeration of \({\Delta }_{{\mathscr{B}}}\). For a run r of \({\mathscr{B}}\) on a tree t, we define the transition Parikh vector of (t, r) by

We define the Parikh image of \({\mathscr{B}}\) as the set \(\mathbbm {p}({\mathscr{B}}) = \{ \mathbbm {p}(t,r) \mid t \in T_{{{\varGamma }}}, r \in \text {Acc}_{{\mathscr{B}}}(t) \}\). As the following lemma shows, the Parikh image of every WTA coincides with the Parikh image of a context-free language.

Lemma 9

There exists a context-free language L over the alphabet \({\Delta }_{{\mathscr{B}}}\) such that \(\mathbbm {p}(L) = \mathbbm {p}({\mathscr{B}})\). A context-free grammar G generating L can be found effectively from \({\mathscr{B}}\).

Proof

We define the context-free grammar \(G = ({Q}_{{\mathscr{B}}} \boldsymbol {\cup } \{S\}, {\Delta }_{{\mathscr{B}}}, P, S)\), where S is a new symbol, by

Then \(L = {\mathscr{L}}(G)\) is context-free and we see as follows that \(\mathbbm {p}(L) = \{ \mathbbm {p}(t,r) \mid t \in T_{{{\varGamma }}}, r \in \text {Acc}_{{\mathscr{B}}}(t) \}\).

“\(\subseteq \)”: Let w ∈ L. We construct a tree t ∈ T_Γ and a run \(r \in \text {Acc}_{{\mathscr{B}}}(t)\) such that \(\mathbbm {p}(w) = \mathbbm {p}(t,r)\). Since w ∈ L, we find words \(u_{1}, \ldots , u_{n} \in ({Q}_{{\mathscr{B}}} \boldsymbol {\cup } {\Delta }_{{\mathscr{B}}})^{*}\) such that u_n = w and S ⇒_Gu₁ ⇒_G… ⇒_Gu_n. We construct by induction for every i ∈{1,…,n} a Γ-context \(t_{i} \in T_{{{\varGamma }}_{{\diamond }}}\) and a run \(r_{i} \in \text {Run}_{{\mathscr{B}}}^{\diamond }(t_{i})\) such that and for every p ∈ Q and \(d \in {\Delta }_{{\mathscr{B}}}\) we have

For i = 1, we know by the definition of G that u₁ = p with , so we let t₁ = ◇ and r₁(ε) = p. Now assume we have constructed t_i and r_i with the properties above. We have u_i ⇒_Gu_i+ 1, so by definition of G, there exists a transition \(d = (p_{1}, \ldots , p_{m}, a, p) \in {\Delta }_{{\mathscr{B}}}\) with and words \(u^{\prime },u^{\prime \prime } \in ({Q}_{{\mathscr{B}}} \boldsymbol {\cup } {\Delta }_{{\mathscr{B}}})^{*}\) such that \(u_{i} = u^{\prime } p u^{\prime \prime }\) and \(u_{i+1} = u^{\prime } d p_{1} {\cdots } p_{m} u^{\prime \prime }\). Thus |u_i|_p ≥ 1, so by induction we find v ∈pos(t_i) with t_i(v) = ◇ and r_i(v) = p. We let t_i+ 1 = t_i〈a(◇,…,◇) → v〉 and define r_i+ 1 by \(r_{i+1}(v^{\prime }) = r_{i}(v^{\prime })\) for \(v^{\prime } \in \text {pos}(t_{i})\) and r_i+ 1(vj) = p_j for j ∈{1,…,m}. It is easy to check that t_i+ 1 and r_i+ 1 satisfy all of the above properties.

Since \(u_{n} = w \in {\Delta }_{{\mathscr{B}}}^{*}\), the Γ-context t_n is actually a Γ-tree, the run \(r_{n} \in \text {Run}_{{\mathscr{B}}}^{{\diamond }}(t_{n})\) is an accepting run of \({\mathscr{B}}\) on t_n, and we have \(\mathbbm {p}(w) = \mathbbm {p}(u_{n}) = \mathbbm {p}(t_{n},r_{n})\). Thus, we have \(\mathbbm {p}(L) \subseteq \{ \mathbbm {p}(t,r) \mid t \in T_{{{\varGamma }}}, r \in \text {Acc}_{{\mathscr{B}}}(t) \}\).

“\(\supseteq \)”: Now let t ∈ T_Γ and \(r \in \text {Acc}_{{\mathscr{B}}}(t)\). We construct a word w ∈ L with \(\mathbbm {p}(w) = \mathbbm {p}(t,r)\). For this, we construct by induction for every v ∈pos(t) words u₁,…,u_n such that r(v) ⇒_Gu₁ ⇒_G… ⇒_Gu_n, \(u_{n} \in {\Delta }_{{\mathscr{B}}}^{*}\), and \(\mathbbm {p}(u_{n}) = \mathbbm {p}(t\!\!\upharpoonright _{v}, r\!\!\upharpoonright _{v})\). We proceed by a reverse induction on the length of v. For |v| = height(t), we let n = 1 and \(u_{1} = \mathbbm {t}(t,r,v)\), then we have r(v) ⇒_Gu₁, \(u_{n} \in {\Delta }_{{\mathscr{B}}}^{*}\), and \(\mathbbm {p}(u_{n}) = \mathbbm {p}(t\!\!\upharpoonright _{v}, r\!\!\upharpoonright _{v})\).

For |v| < height(t), we assume that \(\mathbbm {t}(t,r,v) = d = (p_{1}, \ldots , p_{m}, a, p)\) and that for every i ∈{1,…,m} we have words \(u_{1}^{(i)}, \ldots , u_{n_{i}}^{(i)}\) with \(p_{i} \Rightarrow _{G} u_{1}^{(i)} \Rightarrow _{G} {\ldots } \Rightarrow _{G} u_{n_{i}}^{(i)}\), \(u_{n_{i}}^{(i)} \in {\Delta }_{{\mathscr{B}}}^{*}\), and \(\mathbbm {p}(u_{n_{i}}^{(i)}) = \mathbbm {p}(t\!\!\upharpoonright _{vi}, r\!\!\upharpoonright _{vi})\). Since , we have , so by the definition of G, we have p ⇒_Gdp₁⋯p_m. Thus, we see that

From this, we obtain words \(u_{1}, \ldots , u_{n} \in ({Q}_{{\mathscr{B}}} \boldsymbol {\cup } {\Delta }_{{\mathscr{B}}})^{*}\) with p ⇒_Gu₁ ⇒_G… ⇒_Gu_n such that \(u_{n} = d u_{n_{1}}^{(1)} {\cdots } u_{n_{m}}^{(m)} \in {\Delta }_{{\mathscr{B}}}^{*}\), and therefore \(\mathbbm {p}(u_{n}) = \mathbbm {p}(d) + {\sum }_{i = 1}^{m} \mathbbm {p}(u_{n_{i}}^{(i)}) = \mathbbm {p}(d) + {\sum }_{i = 1}^{m} \mathbbm {p}(t\!\!\upharpoonright _{vi}, r\!\!\upharpoonright _{vi}) = \mathbbm {p}(t\!\!\upharpoonright _{v}, r\!\!\upharpoonright _{v})\).

For v = ε, we thus obtain words u₁,…,u_n such that r(ε) ⇒_Gu₁ ⇒_G… ⇒_Gu_n, \(u_{n} \in {\Delta }_{{\mathscr{B}}}^{*}\), and \(\mathbbm {p}(u_{n}) = \mathbbm {p}(t, r)\). Due to \(r \in \text {Acc}_{{\mathscr{B}}}(t)\) we have , which means that S ⇒_Gr(ε). Therefore u_n ∈ L, which shows that \(\mathbbm {p}(L) \supseteq \{ \mathbbm {p}(t,r) \mid t \in T_{{{\varGamma }}}, r \in \text {Acc}_{{\mathscr{B}}}(t) \}\). □

Lemma 9 shows in particular that the Parikh image of a WTA is semilinear.

Lemma 10

The set \(\mathbbm {p}({\mathscr{B}})\) is semilinear and integers k, k₁,…,k_k, vectors \(\alpha ^{(l)} \in \mathbb {N}^{D}\), and matrices \(\beta ^{(l)} \in \mathbb {N}^{D \times k_{l}} (l \in \{1, \ldots , k\})\) with

can be effectively found from \({\mathscr{B}}\). Furthermore, with \({{\varOmega }} = ({\mu }_{{\mathscr{B}}}(d_{1}), \ldots , {\mu }_{{\mathscr{B}}}(d_{D})) \in K^{D}\) we have \(\text {wt}_{{\mathscr{B}}}(t,r) = {{\varOmega }} \cdot \mathbbm {p}(t,r)\) for every t ∈ T_Γ and every \(r \in \text {Acc}_{{\mathscr{B}}}(t)\).

Proof

It follows from Theorem 3 and Lemma 9 that \(\mathbbm {p}({\mathscr{B}})\) is semilinear. The second statement follows from the definition of \(\text {wt}_{{\mathscr{B}}}\) and the commutativity of ⊕. □

In fact, we do not apply Lemma 10 directly to \({\boldsymbol {\mathcal {U}}}\) but to a covering of \({\boldsymbol {\mathcal {U}}}\). For this covering, we add a mechanism to \({\boldsymbol {\mathcal {U}}}\) to detect the broken coordinates of a run. More precisely, we add to each state of Q one entry containing all states reachable on the current subtree, one entry containing all states visited on the current run, one entry containing all pairs (p, q) of states such that q is reachable by a run which visited p at a position where our current run also visited p, and one entry containing a record of all broken coordinates. This allows us to infer the brokenness of a run directly from the state at its root. The precise construction is as follows.

Construction 2

Let \(\bar {Q} = {\mathbf {Q}} \times \mathcal {P}({\mathbf {Q}}) \times \mathcal {P}({\mathbf {Q}}) \times \mathcal {P}({\mathbf {Q}}^{2}) \times \{0,1\}^{M}\). For subsets \(P_{1}, \ldots , P_{m} \subseteq {\mathbf {Q}}\) and a letter a ∈Γ with rk_Γ(a) = m, we let \(\text {succ}(P_{1}, \ldots , P_{m},a) = \{ \mathbf {q}_{0} \mid \exists ({\mathbf {q}}_{1}, \ldots , {\mathbf {q}}_{m}) \in P_{1} \times {\ldots } \times P_{m} \text { with } {{{\mu }}}({\mathbf {q}}_{1}, \ldots , {\mathbf {q}}_{m}, a, {\mathbf {q}}_{0}) \in \mathbb {Q}^{M}\}\). For a set \(W \subseteq {\mathbf {Q}}^{2}\) and l ∈{1,…,m}, we let \(\text {succ}(P_{1}, \ldots , P_{m},W,l,a) = \bigcup _{{\mathbf {p}} \in {\mathbf {Q}}} \{{\mathbf {p}}\} \times \text {succ}(P_{1}, \ldots , P_{l-1}, \{{\mathbf {p}}^{\prime }\mid ({\mathbf {p}},{\mathbf {p}}^{\prime }) \in W\}, P_{l+1}, \ldots , P_{m}, a)\). Then we define the weight functions of the new automaton \(\bar {\mathcal {U}} = (\boldsymbol {\bar {Q}}, {{\varGamma }}, \bar {{\mu }}, \bar {{\nu }})\) by

We have the following lemma stating that the additional entries of the states of \(\bar {\mathcal {U}}\) realize the intuition behind its construction described earlier.

Lemma 11

Let t ∈ T_Γ, \(\bar {r} \in \text {Run}_{\bar {\mathcal {U}}}(t)\), w ∈pos(t), and \(\bar {r}(w) = ({\mathbf {q}},P,V,W,\bar {a})\). Then the following statements hold.

1. (i)

   \(P = \{ {\mathbf {p}} \in {\mathbf {Q}} \mid \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t \!\!\upharpoonright _{w}, {\mathbf {p}}) \neq \emptyset \}\)

2. (ii)

   \(V = \{ \pi _{{\mathbf {Q}}} \circ \bar {r}(wv) \mid v \in \text {pos}(t \!\!\upharpoonright _{w}) \}\), where \(\pi _{{\mathbf {Q}}} \colon \boldsymbol {\bar {Q}} \to {\mathbf {Q}}\) is the projection to the first coordinate.

3. (iii)

   \(W = \{ ({\mathbf {p}}_{1}, {\mathbf {p}}_{2}) \in {\mathbf {Q}}^{2} \mid \) for some \(v \in \text {pos}(t\!\!\upharpoonright _{w})\) we have \(\pi _{{\mathbf {Q}}} \circ \bar {r}(wv) = {\mathbf {p}}_{1}\) and \(\text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}({\mathbf {p}}_{1},t \langle {\diamond } \to wv \rangle \!\!\upharpoonright _{w} ,{\mathbf {p}}_{2}) \neq \emptyset \}\)

4. (iv)

   \(\bar {a}[i] = 1\) if and only if \((t, \pi _{{\mathbf {Q}}} \circ \bar {r})\!\!\upharpoonright _{w}\) is i-broken.

5. (v)

   \(\pi _{{\mathbf {Q}}} \colon \text {Acc}_{\bar {\mathcal {U}}}(t) \to \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t)\) is a bijection preserving weights of runs.

Proof

(i) See the proof of Lemma 5(i).

(ii) Let t ∈ T_Γ and \(\bar {r} \in \text {Run}_{\bar {\mathcal {U}}}(t)\) and for contradiction, let w ∈pos(t) be a prefix-maximal position for which (ii) does not hold. We deduce that (ii) holds for w. We let a = t(w), m = rk_Γ(a), and write \(\bar {r}(w) = ({\mathbf {q}}_{0}, P_{0}, V_{0}, W_{0}, \bar {a}_{0})\) and \(\bar {r}(wl) = ({\mathbf {q}}_{l}, P_{l}, V_{l}, W_{l}, \bar {a}_{l})\) for l ∈{1,…,m}.

First, let q ∈ V₀. If q = q₀, then \({\mathbf {q}} = \pi _{{\mathbf {Q}}} \circ \bar {r}(w)\). Otherwise, there exists l ∈{1,…,m} with q ∈ V_l. We assume that (ii) holds for wl, so there exists \(v \!\in \! \text {pos}(t \!\!\upharpoonright _{wl})\) with \(\pi _{\mathbf {Q}} \circ \bar {r} (wlv) = \mathbf {q}\).

On the other hand, let \(v \in \text {pos}(t \!\!\upharpoonright _{w})\). For v = ε, we have \(\pi _{{\mathbf {Q}}} \circ \bar {r}(wv) = {\mathbf {q}}_{0} \in V_{0}\). Otherwise, we have \(v = lv^{\prime }\) for some l ∈{1,…,m}. We assume that (ii) holds for wl, so we have \(\pi _{\mathbf {Q}} \circ \bar {r}(wlv^{\prime }) \in V_{l} \subseteq V_{0}\). Thus, (i) holds for w, which is a contradiction, so w does not exist.

(iii) Let t ∈ T_Γ and \(\bar {r} \in \text {Run}_{\bar {\mathcal {U}}}(t)\) and for contradiction, let w ∈pos(t) be a prefix-maximal position for which (iii) does not hold. We deduce that (iii) holds for w. We let a = t(w), m = rk_Γ(a), and write \(\bar {r}(w) = ({\mathbf {q}}_{0}, P_{0}, V_{0}, W_{0}, \bar {a}_{0})\) and \(\bar {r}(wl) = ({\mathbf {q}}_{l}, P_{l}, V_{l}, W_{l}, \bar {a}_{l})\) for l ∈{1,…,m}.

First, let \(({\mathbf {p}}, {\mathbf {p}}^{\prime }) \in W_{0}\). If \(({\mathbf {p}}, {\mathbf {p}}^{\prime }) = ({\mathbf {q}}_{0}, {\mathbf {q}}_{0})\), we choose v = ε. Then \(\pi _{{\mathbf {Q}}} \circ \bar {r}(wv) = {\mathbf {q}}_{0} = {\mathbf {p}}\) and \(\text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}({\mathbf {p}},t \langle {\diamond } \to wv \rangle \!\!\upharpoonright _{w} ,{\mathbf {p}}^{\prime }) = \text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}({\mathbf {q}}_{0}, {\diamond } ,{\mathbf {q}}_{0}) \neq \emptyset \). Otherwise, there exists l ∈{1,…,m} with \(({\mathbf {p}}, {\mathbf {p}}^{\prime }) \in \text {succ}(P_{1}, \ldots , P_{m},W_{l},l,a)\). Thus, there exist (p, p_l) ∈ W_l and (p₁,…,p_l− 1, p_l+ 1,…,p_m) ∈ P₁ ×… × P_l− 1 × P_l+ 1 ×… × P_m with \({{{\mu }}}({\mathbf {p}}_{1}, \ldots , {\mathbf {p}}_{m}, a, {\mathbf {p}}^{\prime }) \in \mathbb {Q}^{M}\). By (i), there exists \({\mathbf {r}}_{j} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t \!\!\upharpoonright _{wj}, {\mathbf {p}}_{j})\) for every j ∈{1,…,m}∖{l}. We assume that (iii) holds for wl, so there exists \(v \in \text {pos}(t \!\!\upharpoonright _{wl})\) with \(\pi _{{\mathbf {Q}}} \circ \bar {r}(wlv) = {\mathbf {p}}\) and \({\mathbf {r}}_{l} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}({\mathbf {p}},t \langle {\diamond } \to wlv \rangle \!\!\upharpoonright _{wl} ,{\mathbf {p}}_{l})\). Thus, we can define \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}({\mathbf {p}},t \langle {\diamond } \to wlv \rangle \!\!\upharpoonright _{w} ,{\mathbf {p}}^{\prime })\) through \({\mathbf {r}}(\varepsilon ) = {\mathbf {p}}^{\prime }\) and r(jv) = r_j(v).

On the other hand, let \(({\mathbf {p}}, {\mathbf {p}}^{\prime }) \in {\mathbf {Q}}^{2}\) such that there exists \(v \in \text {pos}(t \!\!\upharpoonright _{w})\) with \(\pi _{{\mathbf {Q}}} \circ \bar {r}(wv) = {\mathbf {p}}\) and \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}({\mathbf {p}},t \langle {\diamond } \to wv \rangle \!\!\upharpoonright _{w} ,{\mathbf {p}}^{\prime })\). If v = ε, it follows that \({\mathbf {p}}^{\prime } = {\mathbf {p}} = \pi _{{\mathbf {Q}}} \circ \bar {r}(w) = {\mathbf {q}}_{0}\), so \(({\mathbf {p}}, {\mathbf {p}}^{\prime }) \in W_{0}\). Otherwise, we have \(v = lv^{\prime }\) for some l ∈{1,…,m}. We assume that (iii) holds for wl, we have \(\pi _{\mathbf {Q}} \circ \bar {r}(wlv^{\prime }) = \mathbf {p}\), and \(\mathbf {r}\!\!\upharpoonright _{l} \in \text {Run}_{\boldsymbol {\mathcal {U}}}^{\diamond }(\mathbf {p},t \langle \diamond \to wlv^{\prime } \rangle \!\!\upharpoonright _{wl} ,{\mathbf {r}}(l))\), so we have (p, r(l)) ∈ W_l. Moreover, we have \({\mathbf {r}} \!\!\upharpoonright _{j} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t\!\!\upharpoonright _{wj})\) for every j ∈{1,…,m}∖{l}, so by (iii) we have r(j) ∈ P_j for every j ∈{1,…,m}∖{l}. It follows that \(({\mathbf {p}}, {\mathbf {p^{\prime }}}) \in \text {succ}(P_{1}, \ldots , P_{m},W_{l},l,a) \subseteq W_{0}\). Thus, (iii) holds for w, which is a contradiction, so w does not exist.

(iv) Let t ∈ T_Γ and \(\bar {r} \in \text {Run}_{\bar {\mathcal {U}}}(t)\) and for contradiction, let w ∈pos(t) be a prefix-maximal position for which (iv) does not hold. We deduce that (iv) holds for w. We let a = t(w), m = rk_Γ(a), and write \(\bar {r}(w) = ({\mathbf {q}}_{0}, P_{0}, V_{0}, W_{0}, \bar {a}_{0})\) and \(\bar {r}(wl) = ({\mathbf {q}}_{l}, P_{l}, V_{l}, W_{l}, \bar {a}_{l})\) for l ∈{1,…,m}.

First, assume that \(\bar {a}_{0}[i] = 1\). If \(\bar {a}_{l}[i] = 1\) for some l ∈{1,…,m}, then \((t, \pi _{{\mathbf {Q}}} \circ \bar {r})\!\!\upharpoonright _{wl}\) is i-broken since we assume that (iv) holds for wl, so \((t, \pi _{\mathbf {Q}} \circ \bar {r})\!\!\upharpoonright _{w}\) is i-broken as well. If there exists an i-rival p of q₀ with (p, p) ∈ W₀, we see by (iii) that there exists \(v \in \text {pos}(t\!\!\upharpoonright _{w})\) with \(\pi _{{\mathbf {Q}}} \circ \bar {r}(wv) = {\mathbf {p}}\) and \(\text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}({\mathbf {p}},t \langle {\diamond } \to wv \rangle \!\!\upharpoonright _{w} ,{\mathbf {p}}) \neq \emptyset \). It follows that \(t \langle {\diamond } \to wv \rangle \!\!\upharpoonright _{w}\) is an i-p-q₀-fork, so \((t, \pi _{{\mathbf {Q}}} \circ \bar {r})\!\!\upharpoonright _{w}\) is i-fork-broken. If there are l₁, l₂ ∈{1,…,m} with l₁≠l₂ and \(\mathbf {p} \in V_{l_{1}}, \mathbf {q} \in V_{l_{2}}\) such that p and q are i-rivals, we see by (ii) that there exist positions \(v_{1} \in \text {pos}(t \!\!\upharpoonright _{wl_{1}})\) and \(v_{2} \in \text {pos}(t \!\!\upharpoonright _{wl_{2}})\) with \({\mathbf {p}} = \pi _{{\mathbf {Q}}} \circ \bar {r}(wl_{1}v_{1})\) and \({\mathbf {q}} = \pi _{{\mathbf {Q}}} \circ \bar {r}(wl_{2}v_{2})\). Thus, \((t, \pi _{{\mathbf {Q}}} \circ \bar {r})\!\!\upharpoonright _{w}\) is i-split-broken.

On the other hand, assume that \((t, \pi _{{\mathbf {Q}}} \circ \bar {r})\!\!\upharpoonright _{w}\) is i-broken. If \((t, \pi _{{\mathbf {Q}}} \circ \bar {r})\!\!\upharpoonright _{w}\) is i-fork-broken, there exist two i-rivals p, q ∈Q and positions \(w_{p},w_{q} \in \text {pos}(t\!\!\upharpoonright _{w})\) such that w_q <_pw_p, \(\pi _{{\mathbf {Q}}} \circ \bar {r}(ww_{p}) = {\mathbf {p}}\), \(\pi _{{\mathbf {Q}}} \circ \bar {r}(ww_{q}) = {\mathbf {q}}\), and \((t \langle {\diamond } \to ww_{p} \rangle ) \!\!\upharpoonright _{ww_{q}}\) is an i-p-q-fork. It follows that \(\text {Run}_{{\boldsymbol {\mathcal {U}}}}^{{\diamond }}({\mathbf {p}}, (t \langle {\diamond } \to ww_{p} \rangle ) \!\!\upharpoonright _{ww_{q}}, {\mathbf {p}}) \neq \emptyset \), so for \(\bar {r}(ww_{q}) = ({\mathbf {q}}, P, V, W, \bar {a})\), we have (p, p) ∈ W by (iii). It follows that \(\bar {a}[i] = 1\), so by construction of \(\bar {{\mu }}\), also \(\bar {a}_{0}[i] = 1\). If \((t, \pi _{\mathbf {Q}} \circ \bar {r})\!\!\upharpoonright _{w}\) is i-split-broken, there exist two i-rivals p, q ∈Q and two prefix-independent positions \(w_{p},w_{q} \in \text {pos}(t\!\!\upharpoonright _{w})\) with \(\pi _{{\mathbf {Q}}} \circ \bar {r}(ww_{p}) = {\mathbf {p}}\) and \(\pi _{{\mathbf {Q}}} \circ \bar {r}(ww_{q}) = {\mathbf {q}}\). We let \(w^{\prime }\) be c w_p and w_q and write \(w_{p} = w^{\prime }j_{p}v_{p}\), \(w_{q} = w^{\prime }j_{q}v_{q}\), \(\bar {r}(ww^{\prime }) = ({\mathbf {q}}^{\prime }, P^{\prime }, V^{\prime }, W^{\prime }, \bar {a}^{\prime })\), and \(\bar {r}(ww^{\prime }j) = ({\mathbf {q}}_{j}^{\prime }, P_{j}^{\prime }, V_{j}^{\prime }, W_{j}^{\prime }, \bar {a}_{j}^{\prime })\) (j ∈{j_p, j_q}). By (ii), we have \({\mathbf {p}} \in V_{j_{p}}^{\prime }\) and \({\mathbf {q}} \in V_{j_{q}}^{\prime }\), so \(\bar {a}^{\prime }[i] = 1\). By construction of \(\bar {{\mu }}\), we thus have \(\bar {a}_{0}[i] = 1\). Thus, (iv) holds for w, which is a contradiction, so w does not exist.

(v) See the proofs of Lemma 5(iii) and Lemma 5(iv). □

Finally, we show the decidability of the separation property by applying Lemma 10 to \(\bar {\mathcal {U}}\).

Theorem 4

There exists an integer \(\tilde {C}\) such that every set of coordinates \(I \subseteq \{1, \ldots , M\}\) is separable if and only if it is \(\tilde {C}\)-separable. Moreover, it is decidable for every such I whether it is \(\tilde {C}\)-separable. In particular, it is decidable whether \(\boldsymbol {\mathcal {U}}\) is broken.

Proof

We let d₁,…,d_D be an enumeration of \({\Delta }_{\bar {\mathcal {U}}}\) and for \(\bar {\mathcal {U}}\), let \(k, k_{1}, \ldots , k_{k} \in \mathbb {N},\alpha ^{(l)} \in \mathbb {N}^{D}, \beta ^{(l)} \in \mathbb {N}^{D \times k_{l}}, {{\varOmega }} \in \mathbb {Q}^{M \times D} (l \in \{1, \ldots , k\})\) be as in Lemma 10. Furthermore, we let ω₁,…,ω_M be the rows of Ω, let \(\tilde {C} = 1 + \lceil {{\max \limits } \{ |\omega _{i}\alpha ^{(l)} - \omega _{j}\alpha ^{(l)}| \mid i,j \in \{1, \ldots , M\}, l \in \{1, \ldots , k\} \}}\rceil \), and for \(I \subseteq \{1, \ldots , M\}\), let D_I =

Let \(I \subseteq \{1, \ldots , M\}\) and J = {1,…,M}∖ I. First, assume that I is \(\tilde {C}\)-separable and let t ∈ T_Γ and \({\mathbf {r}} \in \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t)\) such that (t, r) is I-\(\tilde {C}\)-separated. Let \(\bar {r}\) be the unique accepting run of \(\bar {\mathcal {U}}\) on t. Then for some l ∈{1,…,k} and some \(\bar {X} \in \mathbb {N}^{k_{l}}\) we have \(\mathbbm {p}(t,\bar {r}) = \alpha ^{(l)} + \beta ^{(l)} \bar {X}\).

We let α^(l)[1],…,α^(l)[D] be the entries of α^(l) and β^(l)[1],…,β^(l)[D] be the rows of β^(l). Since (t, r) is i-broken exactly for the coordinates i ∈ I, we have \({\sum }_{d \in D_{I}} \alpha ^{(l)}[d] + \beta ^{(l)}[d] \bar {X} \geq 1\) and \({\sum }_{I \subsetneq I^{\prime } \subseteq M} {\sum }_{d \in D_{I^{\prime }}} \alpha ^{(l)}[d] + \beta ^{(l)}[d] \bar {X} = 0\). Moreover, for every two i ∈ I and j ∈ J we have \(\omega _{j} \alpha ^{(l)} + \omega _{j} \beta ^{(l)} \bar {X} = {\mathbf {wt}}_{j}(t,{\mathbf {r}}) \leq {\mathbf {wt}}_{i}(t,{\mathbf {r}}) - \tilde {C} = \omega _{i} \alpha ^{(l)} + \omega _{i} \beta ^{(l)} \bar {X} - \tilde {C}\). In conclusion, we see that there exists l ∈{1,…,k} such that the following system of linear inequalities possesses an integer solution.

Conversely, assume that there exists l ∈{1,…,k} such that the above system of linear inequalities possesses an integer solution \(\bar {X}\). Let \(C \in \mathbb {N}\) and let \(\bar {Y}\) be the scalar multiplication of \(\bar {X}\) with \(\tilde {C} + C\). Then there exists a tree t ∈ T_Γ and an accepting run \(\bar {r} \in \text {Acc}_{\bar {\mathcal {U}}}(t)\) such that \(\mathbbm {p}(t,\bar {r}) = \alpha ^{(l)} + \beta ^{(l)} \bar {Y}\). Let \({\mathbf {r}} = \pi _{{\mathbf {Q}}} \circ \bar {r} \in \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t)\) be the unique accepting run of \({\boldsymbol {\mathcal {U}}}\) on t. By choice of \(\tilde {C}\) and the linearity of matrix multiplication, we see that for every i ∈ I and every j ∈ J we have

It follows that \({\mathbf {wt}}_{j}(t,{\mathbf {r}}) = \omega _{j} \alpha ^{(l)} + \omega _{j} \beta ^{(l)} \bar {Y} \leq \omega _{i} \alpha ^{(l)} + \omega _{i} \beta ^{(l)} \bar {Y} - C = {\mathbf {wt}}_{i}(t,{\mathbf {r}}) - C\) for every i ∈ I and every j ∈ J. Moreover, since all entries in α^(l) and β^(l) are non-negative, we see that also \({\sum }_{d \in D_{I}} \alpha ^{(l)}[d] + \beta ^{(l)}[d] \bar {Y} \geq 1\) and \({\sum }_{I \subsetneq I^{\prime } \subseteq M} {\sum }_{d \in D_{I^{\prime }}} \alpha ^{(l)}[d] + \beta ^{(l)}[d] \bar {Y} \leq 0\) holds, so (t, r) is i-broken exactly for the coordinates i ∈ I. Thus, I is C-separable. As C was arbitrary, I is separable.

In conclusion, we see on the one hand that if I is \(\tilde {C}\)-separable, then for some l ∈{1,…,k} the above system of linear inequalities possesses an integer solution. On the other hand, if for some l ∈{1,…,k} the above system of linear inequalities possesses an integer solution, then I is separable. In particular, I is separable iff it is \(\tilde {C}\)-separable iff the above system of linear inequalities possesses an integer solution. The satisfiability of systems of linear inequalities over the rationals with integer solutions is a decidable problem ([37, 38], Theorem 3.4). As there are only finitely many such systems to consider, it is decidable whether I is separable. To decide whether \(\boldsymbol {\mathcal {U}}\) is broken, it suffices to check whether there exists a separable subset \(I \subseteq \{1, \ldots , M\}\). □

3.2 Necessity

In this section, we show that if \({\boldsymbol {\mathcal {U}}}\) is broken, then \(\llbracket {\mathcal {A}}\rrbracket \) is not finitely sequential. For this, we employ Ramsey’s Theorem, so we briefly recall Ramsey’s Theorem and the related concepts.

Let \(H,c \in \mathbb {N}\) be integers. For a set X, we denote by \(\left [\frac {X}{H}\right ]\) the set of all subsets of X of cardinality H, i.e., \(\left [\frac {X}{H}\right ] = \{ Y \subseteq X \mid |Y| = H\}\). A set \(Y \in \left [\frac {X}{H}\right ]\) is also called an H-subset of X. An H-c-coloring of X is a mapping \(g \colon \left [\frac {X}{H}\right ] \to \{1,\ldots , c\}\). We have Ramsey’s Theorem as follows.

Theorem 5 (33)

Let \(H,c,n \in \mathbb {N}\). Then there exists an integer \(R(H,c,n) \in \mathbb {N}\) such that for every set X of cardinality at least R(H, c, n) and every H-c-coloring g of X, there exists a subset \(Y \subseteq X\) of cardinality n such that \(|g(\left [\frac {Y}{H}\right ])| = 1\), i.e., all sets in \(\left [\frac {Y}{H}\right ]\) are colored by the same color.

Although not stated explicitly, Bala’s proof for words [26] most likely also involves some form of Ramsey’s Theorem as his proof of \(\boldsymbol {\mathcal {U}}\) being broken implying \(\llbracket {\mathcal {A}}\rrbracket \) to not be finitely sequential “deals with colorings of finite hypercubes”. In our proof for tree automata, we are able to handle fork-brokenness without employing Ramsey’s Theorem. This suggest that applying our approach to word automata yields a proof which is simpler than the corresponding one used in [26]. The reason for this is that our separation property considers sets of coordinates instead of the single coordinates which the A-Fork property considers. For the separable sets \(I \in \mathcal {I}\) which are minimal with respect to set inclusion, we are able to prove a statement for I-C-separated pairs (t, r) which greatly facilitates dealing with fork-brokenness and enables us to deal with split-brokenness in the first place. Namely, if (t, r) is I-C-separated for a sufficiently large C and no subset of I is separable, then the weights of all coordinates in I coincide for every loop which loops in a state occurring in r.

To prove this statement, we define Υ as the size of the largest Γ-word of height at most 4|Q|² and we define ξ as the smallest difference between the weights of two coordinates of a loop in a Γ-word of height at most 4|Q|². That is, we let

and \(\xi = {\min \limits } X \setminus \{0\}\). Moreover, we let \({\mu }_{\max \limits } \in \mathbb {Q}\) be a positive upper bound on the weights occurring in \({\boldsymbol {\mathcal {U}}}\), i.e., for \(R = \{ |\pi _{i}(\bar {x})| \mid i \in \{1, \ldots , M\}, \bar {x} \in ({{\boldsymbol {\mu }}}({\Delta }_{{\boldsymbol {\mathcal {U}}}}) \boldsymbol {\cup } {{\boldsymbol {\nu }}}({\mathbf {Q}})) \setminus \{(-\infty , \ldots , -\infty )\}\}\), we let \({\mu }_{\max \limits } = {\max \limits } R\). Then we have the following lemma.

Lemma 12

Let \(I \in \mathcal {I}\) be minimal with respect to set inclusion, let \(\tilde {C}\) be as in Theorem 4, and let \(n = \lceil {{2M\tilde {C}}{\xi ^{-1}}}\rceil \). Furthermore, let \(C \geq 2{\mu }_{\max \limits }n {{\varUpsilon }}\) and let t ∈ T_Γ and \({\mathbf {r}} \in \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t)\) be such that (t, r) is I-C-separated. Then for every p ∈r(pos(t)), every Γ-word s with height(s) ≤ 4|Q|² and \(\text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {p}}, s, {\mathbf {p}}) \neq \emptyset \), and every two coordinates i, j ∈ I we have \({\mathbf {\mathbf {wt}}}^{{\diamond }}_{i}({\mathbf {p}},s,{\mathbf {p}}) = {\mathbf {\mathbf {wt}}}^{{\diamond }}_{j}({\mathbf {p}},s,{\mathbf {p}})\).

Proof

Let I, C, n, t, r be as in the statement of the lemma. First, we see as follows that for every two i, j ∈ I we have \(|{\mathbf {{wt}}}_{i}(t,{\mathbf {r}}) - {\textbf {wt}}_{j}(t,{\mathbf {r}})| \leq M\tilde {C}\). Let i₁,…,i_|I| be an enumeration of I such that \({\text {wt}}_{i_{1}}(t,{\mathbf {r}}) \leq {\ldots } \leq {\text {wt}}_{i_{|I|}}(t,{\mathbf {r}})\). If for some k ∈{1,…,|I|− 1} we had \({\textbf {wt}}_{i_{k+1}}(t,{\mathbf {r}}) \geq {\textbf {wt}}_{i_{k}}(t,{\mathbf {r}}) + \tilde {C}\), then clearly \(I^{\prime } = I \setminus \{i_{1}, \ldots , i_{k}\}\) would be \(\tilde {C}\)-separable. By Theorem 4, we would therefore have \(I^{\prime } \in \mathcal {I}\), which would be a contradiction to the minimality of I. Thus, we have \({\textbf {wt}}_{i_{|I|}}(t,\mathbf {r}) - {\textbf {wt}}_{i_{1}}(t,\mathbf {r}) \leq (|I|-1)\tilde {C} \leq M\tilde {C}\).

Now assume for contradiction that there exists a state p ∈r(pos(t)), a Γ-word s of height at most 4|Q|², and two coordinates i, j ∈ I such that \(\text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {p}}, s, {\mathbf {p}}) \neq \emptyset \) and \({\textbf {wt}}^{{\diamond }}_{i}({\mathbf {p}}, s, {\mathbf {p}}) \neq {\textbf {wt}}^{{\diamond }}_{j}({\mathbf {p}}, s, {\mathbf {p}})\). We may assume that \({\textbf {wt}}^{{\diamond }}_{i}({\mathbf {p}}, s, {\mathbf {p}}) < {\textbf {wt}}^{{\diamond }}_{j}({\mathbf {p}}, s, {\mathbf {p}})\). Then by our choice of ξ, we have \({\mathbf {wt}}^{\diamond }_{i}(\mathbf {p}, s, \mathbf {p}) \leq {\mathbf {wt}}^{\diamond }_{j}(\mathbf {p}, s, \mathbf {p}) - \xi \). Let \(\mathbf {r}_{\mathbf {p}} \in \text {Run}^{\diamond }_{\boldsymbol {\mathcal {U}}}(\mathbf {p},s,\mathbf {p})\), w ∈pos(t) with r(w) = p, and let . Then \({\mathbf {r}}^{\prime } \in \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t^{\prime })\) satisfies

Now let i₁,…,i_|I| be an enumeration of I such that \({\textbf {wt}}_{i_{1}}(t^{\prime },{\mathbf {r}}^{\prime }) \leq {\ldots } \leq {\textbf {wt}}_{i_{|I|}}(t^{\prime },{\mathbf {r}}^{\prime })\). Since \({\textbf {wt}}_{j}(t^{\prime }, r^{\prime }) - {\textbf {wt}}_{i}(t^{\prime }, r^{\prime }) \geq M\tilde {C}\), there must exist some k ∈{1,…,|I|− 1} with \(\text {wt}_{i_{k+1}}(t,\mathbf {r}) \geq \text {wt}_{i_{k}}(t,\mathbf {r}) + \tilde {C}\). Furthermore, for every ι ∈{1,…,M}∖ I we have

and similarly

By choice of C, we thus have

so \(I^{\prime } = I \setminus \{i_{1}, \ldots , i_{k}\}\) is \(\tilde {C}\)-separable. By Theorem 4, we therefore have \(I^{\prime } \in \mathcal {I}\), which is a contradiction to the minimality of I. □

We are now ready to prove the main result of this section, i.e., that \(\llbracket {\mathcal {A}}\rrbracket \) is not finitely sequential if \({\boldsymbol {\mathcal {U}}}\) is broken. We will assume that a finitely sequential representation \(\llbracket {\mathcal {A}}\rrbracket = \max \limits _{n=1}^{N} \llbracket {\mathcal {A}_{n}}\rrbracket \) of \(\mathcal {A}\) exists, choose a C-separated pair (t, r) for a sufficiently large C, and then deduce a contradiction depending on whether (t, r) is fork-broken or split-broken.

Due to Lemma 12, our method to deal with fork-brokenness is quite similar to the method used to deal with fork-brokenness in [25] and [34]. As in those proofs, we construct from (t, r) new trees and runs with increasingly more alterations of forks and distinguishers and then show that at least N + 1 deterministic max-plus-WTA are necessary to assign the correct weight to all of these trees. The challenge we face in adapting the proof from [34] to our situation is that, in order to obtain a contradiction, we have to ensure that in the runs we construct the coordinates from I dominate the other coordinates. In our constructions we may therefore only make “small” modifications to (t, r). Our solution involves constructing more than the N + 1 trees sufficient for the proofs in [25, 34].

Dealing with split-brokenness is much more complicated and is in fact the only reason we have to use the covering automaton \({\boldsymbol {\mathcal {U}}}\) instead of \({\mathcal {U}}\). As split-brokenness does not apply to words, this was not an issue in [26]. We provide a detailed intuition of this part of our proof when we consider the case that (t, r) is split-broken. We prove the following lemma.

Lemma 13

If \({\boldsymbol {\mathcal {U}}}\) is broken, \(\mathcal {A}\) does not possess a finitely sequential representation.

Proof

For contradiction, we assume that \(\llbracket {\mathcal {A}}\rrbracket = \max \limits _{i=1}^{M} \pi _{i}(\llbracket {{\boldsymbol {\mathcal {U}}}}\rrbracket )\) is the maximum of the deterministic max-plus-WTA \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{N}\). For n ∈{1,…,N}, we write \(\mathcal {A}_{n} = ({Q}_{n}, {{\varGamma }}, {\mu }_{n}, {\nu }_{n})\) and let \(L = \max \limits _{n=1}^{N} \max \limits _{x \in {\mu }_{n}({\Delta }_{\mathcal {A}_{n}}) \setminus \{ -\infty \}} |x|\) and \(|{Q}_{\bullet }| = \max \limits _{n = 1}^{N} |{Q}_{n}|\).

Due to the determinism of \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{N}\), the set \(\text {Run}_{\mathcal {A}_{n}}(t)\) is either empty or a singleton for every n ∈{1,…,N} and t ∈ T_Γ. We may even assume that \(\text {Run}_{\mathcal {A}_{n}}(t)\) is always a singleton, i.e., that each \(\mathcal {A}_{n}\) is complete. If \(\mathcal {A}_{n}\) is not complete, we can simply add a dummy state with final weight \(-\infty \) to Q_n which the automaton can transition into whenever no valid transition is available.

We warn the reader that the roles of the constants defined in the following are likely not apparent until these constants are actually used. It may thus be wise to only take note of which constants are defined and then later verify the correctness of their choice. We let \({{\varXi }} = {Q}_{1} \times {\ldots } \times {Q}_{N} \times {Q}^{2}\) and

For H ∈{1,…,M} we let R_H be the Ramsey number R(2H, MN,2H + 2) from Theorem 5, i.e., such that for every set X of cardinality at least R_H and every 2H-MN-coloring of X, there exists a subset \(Y \subseteq X\) of cardinality 2H + 2 whose 2H-subsets are all colored with the same color. Then we let \(\bar {R} = {\max \limits } \{ R_{1}, \ldots , R_{M} \}\). Furthermore, we let D = N|Q_∙|² + 1 and define natural numbers N₁,…,N_D inductively as follows. We let N_D = 0 and if \(N_{k_{1}+1}, \ldots , N_{D}\) are defined, we choose \(N_{k_{1}}\) such that for all k₂ ∈{k₁ + 1,…,D} we have

Let \(I \in \mathcal {I}\) be minimal with respect to set inclusion, let \(\tilde {C}\) be as in Theorem 4 and for some

choose t ∈ T_Γ and \({\mathbf {r}} \in \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t)\) such that (t, r) is I-C-separated. We consider two cases.

Case 1: For some i ∈ I and i-rivals p, q ∈Q, (t, r) is i-p-q-fork-broken.

In this case, there exist two positions w_p, w_q ∈pos(t) such that w_q <_pw_p, r(w_p) = p, r(w_q) = q, and \(f^{\prime } = (t \langle \diamond \to w_{p} \rangle ) \!\!\upharpoonright _{w_{q}}\) is an i-p-q-fork. By Lemma 7 and Lemma 8, there exists an i-p-q-distinguisher s with height(s) ≤ 4|Q|² and a p-q-fork f with height(f) ≤ 2|Q|². We let \(u = t \!\!\upharpoonright _{w_{p}}\) and \(\hat {u} = t \langle \diamond \to w_{q} \rangle \), i.e., we have \(t = \hat {u}(f^{\prime } (u ) )\). We let s₀ = u and for k ∈{1,…,D − 1}, we let \(s_{k} = s^{N_{k}}(f (s_{k-1} ) )\). Then for k ∈{1,…,D}, we let \(t_{k} = \hat {u}(s^{N_{k}}(f^{\prime } (s_{k-1} ) ) )\). For clarity, for words we would have \(t_{1} = u f^{\prime } s^{N_{1}} \hat {u}\) and \(t_{k} = u f s^{N_{1}} {\cdots } f s^{N_{k-1}} f^{\prime } s^{N_{k}} \hat {u}\). For each k ∈{k₁ + 1,…,D}, we let r_k be the unique accepting run of \({\boldsymbol {\mathcal {U}}}\) on t_k.

Due to the choice of I and C, the heights of s and f, and Lemma 12, we have \({\text {wt}}^{{\diamond }}_{i}({\mathbf {p}},f,{\mathbf {p}}) = {\text {wt}}^{{\diamond }}_{j}({\mathbf {p}},f,{\mathbf {p}})\), \({\text {wt}}^{{\diamond }}_{i}({\mathbf {p}},s,{\mathbf {p}}) = {\text {wt}}^{{\diamond }}_{j}({\mathbf {p}},s,{\mathbf {p}})\), and \({\text {wt}}^{{\diamond }}_{i}({\mathbf {q}},s,{\mathbf {q}}) = {\text {wt}}^{{\diamond }}_{j}({\mathbf {q}},s,{\mathbf {q}})\) for every two i, j ∈ I. Let i ∈ I such that wt_i(t, r) ≥wt_j(t, r) for all j ∈ I. Then, for every k ∈{1,…,D} and every j ∈ I, we have

Furthermore, for every k ∈{1,…,D} and j ∈{1,…,M}∖ I, we have by choice of C that

Thus, we have \(\max \limits _{j = 1}^{M} \text {wt}_{j}(t_{k}, {\mathbf {r}}_{k}) = \text {wt}_{i}(t_{k}, {\mathbf {r}}_{k})\) for every k ∈{1,…,D}. By choice of N₁,…,N_D, it follows that for every two k₁, k₂ ∈{1,…,D} with k₂ > k₁ we have

Here, the first inequality is an application of the reverse triangle inequality. We assume that \(\llbracket {\mathcal {A}}\rrbracket = \max \limits _{n = 1}^{N} \llbracket {\mathcal {A}_{n}}\rrbracket \), so for every k ∈{1,…,D} there exists some n_k ∈{1,…,N} with \(\llbracket {\mathcal {A}}\rrbracket (t_{k}) = \llbracket {\mathcal {A}_{n_{k}}}\rrbracket (t_{k})\). For every k ∈{1,…,D}, we let \(r_{k} \in \text {Run}_{\mathcal {A}_{n_{k}}}(t_{k})\) be the unique run of \(\mathcal {A}_{n_{k}}\) on t_k. Furthermore, we let \(\hat {v} = \Diamond _{1}(\hat {u})\) and \(v_{k} = \Diamond _{1}(\hat {u}(s^{N_{k}}(f^{\prime })))\). We have D = N|Q_∙|² + 1 many trees and every automaton \(\mathcal {A}_{n}\) has at most |Q_∙| many states, so by pigeonhole principle there are at least two distinct indices k₁, k₂ ∈{1,…,D} such that \((n_{k_{1}},r_{k_{1}}(\hat {v}),r_{k_{1}}(v_{k_{1}})) = (n_{k_{2}},r_{k_{2}}(\hat {v}),r_{k_{2}}(v_{k_{2}}))\). We may assume that k₂ > k₁. We let \(n = n_{k_{1}}\), then due to the assumption that \(\mathcal {A}_{n}\) is deterministic, we have

Clearly, this is a contradiction to (♠) above.

Case 2: For some i ∈ I and i-rivals p, q ∈Q, (t, r) is i-p-q-split-broken.

As the proof for this case is rather involved, we first provide an intuitive description of the main ideas behind our approach. First, assume that M = N = 1 and that two rivals p, q occur at prefix-independent positions w_p, w_q ∈pos(t) as in Fig. 2. We let s be a p-q-distinguisher and u a p-q-reacher. Then we substitute the subtrees at w_p and w_q in t by the tree \(s^{|{Q}_{\bullet }|}(u)\) to obtain a tree \(t^{\prime }\) as in Fig. 2. We easily obtain an accepting run \({\mathbf {r}}^{\prime }\) of \({\boldsymbol {\mathcal {U}}}\) on \(t^{\prime }\) and this run loops s in p below w_p with some weight x and it loops s in q below w_q with some weight y such that x ≠ y.

The tree t and the trees obtained by substituting the subtrees at w_p and w_q by powers of s

Full size image

Since M = N = 1, we have \(\text {wt}_{{\boldsymbol {\mathcal {U}}}}(t^{\prime }, {\mathbf {r}}^{\prime }) = \llbracket {\mathcal {A}_{1}}\rrbracket (t^{\prime })\). As \(\mathcal {A}_{1}\) is deterministic, the one accepting run of \(\mathcal {A}_{1}\) on \(t^{\prime }\) is identical on the subtrees below w_p and w_q. Furthermore, as \(\mathcal {A}_{1}\) has at most |Q_∙| states, this run loops some sub-Γ-word sⁿ of \(s^{|{Q}_{\bullet }|}\) in a state of \(\mathcal {A}_{1}\). We let z be the weight of this loop in \(\mathcal {A}_{1}\). Then we consider the tree t^+p obtained by substituting the subtree at w_p in \(t^{\prime }\) by \(s^{|{Q}_{\bullet }|+n}(u)\) and the tree t^+q obtained by substituting the subtree at w_q in \(t^{\prime }\) by \(s^{|{Q}_{\bullet }|+n}(u)\), see also Fig. 2. Clearly, we have \(\llbracket {\mathcal {A}_{1}}\rrbracket (t^{+p}) = \llbracket {\mathcal {A}_{1}}\rrbracket (t^{+q}) = \llbracket {\mathcal {A}_{1}}\rrbracket (t^{\prime }) + z\).

We also easily obtain accepting runs r^+p, r^+q of \({\boldsymbol {\mathcal {U}}}\) on the trees t^+p and t^+q and for these runs we have \(\text {wt}_{{\boldsymbol {\mathcal {U}}}}(t^{+p}, {\mathbf {r}}^{+p}) = \text {wt}_{{\boldsymbol {\mathcal {U}}}}(t^{\prime }, {\mathbf {r}}^{\prime }) + nx\) and \(\text {wt}_{{\boldsymbol {\mathcal {U}}}}(t^{+q}, {\mathbf {r}}^{+q}) = \text {wt}_{{\boldsymbol {\mathcal {U}}}}(t^{\prime }, {\mathbf {r}}^{\prime }) + ny\). Again, since M = N = 1, we obtain \(\llbracket {\mathcal {A}_{1}}\rrbracket (t^{\prime }) + z = \llbracket {\mathcal {A}_{1}}\rrbracket (t^{+p}) = \text {wt}_{{\boldsymbol {\mathcal {U}}}}(t^{\prime }, {\mathbf {r}}^{\prime }) + nx = \llbracket {\mathcal {A}_{1}}\rrbracket (t^{\prime }) + nx\) and \(\llbracket {\mathcal {A}_{1}}\rrbracket (t^{\prime }) + z = \llbracket {\mathcal {A}_{1}}\rrbracket (t^{+q}) = \text {wt}_{{\boldsymbol {\mathcal {U}}}}(t^{\prime }, {\mathbf {r}}^{\prime }) + ny = \llbracket {\mathcal {A}_{1}}\rrbracket (t^{\prime }) + ny\), i.e., nx = z = ny. This is a contradiction to x≠y.

For M = 1 and N arbitrary, our earlier argument breaks as we cannot guarantee anymore that exactly one deterministic automaton assigns the maximum weight to the trees \(t^{\prime }, t^{+p}\), and t^+q. There are two approaches to solve this problem. One is described in [34], the other employs Ramsey’s theorem. We outline the latter approach as it is easier to generalize to the scenario where M is arbitrary. As above, we substitute the trees below w_p and w_q by the tree \(s^{|{Q}_{\bullet }|^{N}}(u)\). By considering the runs of all the deterministic automata on \(t^{\prime }\) in parallel, we see that some sub-Γ-word sⁿ of \(s^{|{Q}_{\bullet }|^{N}}\) loops in all the deterministic automata in parallel. More precisely, there exist integers m and n such that each automaton \(\mathcal {A}_{i}\), after reading s^m(u), is in a state q_i which loops in sⁿ. For each automaton \(\mathcal {A}_{i}\), we let z_i be the weight of \(\mathcal {A}_{i}\)’s loop in sⁿ.

We then consider the Ramsey number R = R(2,N,4), i.e., for every set X of cardinality at least R and every 2-N-coloring of X, there exists a subset \(Y \subseteq X\) of cardinality 4 whose 2-subsets are all colored with the same color. For every 2-subset \(\{\zeta _{1}, \zeta _{2}\} \subseteq \{1,\ldots ,R\}\) with ζ₁ < ζ₂, we define the tree \(t_{\zeta _{1},\zeta _{2}}\) by substituting the subtree below w_p by \(s^{|{Q}_{\bullet }|^{N} + \zeta _{1} n}(u)\) and the subtree below w_q by \(s^{|{Q}_{\bullet }|^{N} + \zeta _{2} n}(u)\). We let \(\mathbf {r}_{\zeta _{1},\zeta _{2}}\) be the unique accepting run of \(\boldsymbol {\mathcal {U}}\) on \(t_{\zeta _{1},\zeta _{2}}\) and define the color of {ζ₁, ζ₂} as the smallest index i ∈{1,…,N} such that \(\text {wt}_{{\boldsymbol {\mathcal {U}}}}(t_{\zeta _{1},\zeta _{2}}, {\mathbf {r}}_{\zeta _{1},\zeta _{2}}) = \llbracket {\mathcal {A}_{i}}\rrbracket (t_{\zeta _{1},\zeta _{2}})\). By choice of R, we find 4 integers ζ₁ < ζ₂ < ζ₃ < ζ₄ in {1,…,R} such that {ζ₁, ζ₃}, {ζ₂, ζ₃}, and {ζ₁, ζ₄} are all colored with the same color i ∈{1,…,N}. We derive that \((\zeta _{2} - \zeta _{1})z_{i} = \llbracket {\mathcal {A}_{i}}\rrbracket (t_{\zeta _{2},\zeta _{3}}) - \llbracket {\mathcal {A}_{i}}\rrbracket (t_{\zeta _{1},\zeta _{3}}) = \text {wt}_{{\boldsymbol {\mathcal {U}}}}(t_{\zeta _{2},\zeta _{3}}, {\mathbf {r}}_{\zeta _{2},\zeta _{3}}) - \text {wt}_{{\boldsymbol {\mathcal {U}}}}(t_{\zeta _{1},\zeta _{3}}, {\mathbf {r}}_{\zeta _{1},\zeta _{3}}) = (\zeta _{2} - \zeta _{1})nx\) and similarly \((\zeta _{4} - \zeta _{3})z_{i} = \llbracket {\mathcal {A}_{i}}\rrbracket (t_{\zeta _{1},\zeta _{4}}) - \llbracket {\mathcal {A}_{i}}\rrbracket (t_{\zeta _{1},\zeta _{3}}) = \text {wt}_{{\boldsymbol {\mathcal {U}}}}(t_{\zeta _{1},\zeta _{4}}, {\mathbf {r}}_{\zeta _{1},\zeta _{4}}) - \text {wt}_{{\boldsymbol {\mathcal {U}}}}(t_{\zeta _{1},\zeta _{3}}, {\mathbf {r}}_{\zeta _{1},\zeta _{3}}) = (\zeta _{4} - \zeta _{3})ny\). As above, we obtain the contradiction x = y.

Assume that both M and N are arbitrary. For M = 1, we substituted the subtrees below w_p and w_q by the same tree \(s^{|{Q}_{\bullet }|^{N}}(u)\) to make use of the fact that each deterministic automaton then treats both subtrees in the same way. However, if M > 1, the subtrees present below w_p and w_q may be indispensable to ensure that the weights of the coordinates not in I are small. That is, replacing these subtrees may cause a coordinate for which p and q are not rivals to become dominant. This is evidenced by the automaton in Example 1, where we cannot simply replace these subtrees. To overcome the problem of not being able to substitute the subtrees, we employ the properties of \(\boldsymbol {\mathcal {U}}\) proved in Lemma 5 and construct a run of \({\mathcal {U}}\) into which we insert powers of distinguishers. The general outline of our approach is depicted in Fig. 3.

The general outline of our proof of case 2

Full size image

First, we realize that it suffices to substitute only one subtree. By Lemma 5(v), the subtree t_p at w_p is a p-q-reacher. Thus, substituting t_p and the subtree t_q at w_q by a tree of the form s^m(t_p) allows us to create a scenario as above while changing the weights below w_p only “slightly”, i.e., dependent only on s^m. However, depending on the sizes of t_p and t_q, this operation may still significantly change the coordinate-wise weights below w_q. This is the case for the automaton from Example 1. We thus need to bound the size of both the substituting and the substituted tree below w_q.

Our idea to bound the size of the substituted tree is to move parts of t_q from t_q to t_p, thereby shrinking t_q. More precisely, we want to cut loops from \(\mathbf {r}_{q}^{q} \in \text {Run}_{\boldsymbol {\mathcal {U}}}(t_{q},\mathbf {q})\) and insert them into \(\mathbf {r}_{p}^{p} \in \text {Run}_{\boldsymbol {\mathcal {U}}}(t_{p},\mathbf {p})\). If t_q is of height at least |Q|², there exists a loop in \(\mathbf {r}_{q}^{q}\), so we can shrink t_q to height |Q|² by moving loops. However, in order for this to work, the state \(\mathbf {r}_{q}^{q}\) loops in has to occur in \(\mathbf {r}_{p}^{p}\). This is not always the case, as seen in the automaton from Example 1. We resolve this problem as follows. We let \(\mathbf {r}_{p}^{q} \in \text {Run}_{\boldsymbol {\mathcal {U}}}(t_{p}, \mathbf {q})\) and \(\mathbf {r}_{q}^{p} \in \text {Run}_{\boldsymbol {\mathcal {U}}}(t_{q}, \mathbf {p})\), such runs exist by Lemma 5(v), and let \(r_{p}^{p},r_{p}^{q},r_{q}^{q},r_{q}^{p}\) be the projections of \({\mathbf {r}}_{p}^{p},{\mathbf {r}}_{p}^{q},{\mathbf {r}}_{q}^{q},{\mathbf {r}}_{q}^{p}\) to the first coordinate. Then from Lemma 5(ii), we see that \(\{ (r_{p}^{p}(w), r_{p}^{q}(w)) \mid w \in \text {pos}(t_{p}) \} = \{ (r_{q}^{p}(w), r_{q}^{q}(w)) \mid w \in \text {pos}(t_{q}) \}\). Thus, if we have a simultaneous loop in \({\mathbf {r}}_{q}^{p}\) and \({\mathbf {r}}_{q}^{q}\), i.e., two positions w₁ <_pw₂ in pos(t_q) with \(({\mathbf {r}}_{q}^{p}(w_{1}),{\mathbf {r}}_{q}^{q}(w_{1})) = ({\mathbf {r}}_{q}^{p}(w_{2}),{\mathbf {r}}_{q}^{q}(w_{2}))\), then this is also a simultaneous loop in \(r_{q}^{p}\) and \({r}_{q}^{q}\) and there exists a position w ∈pos(t_p) with \((r_{p}^{p}(w), r_{p}^{q}(w)) = (r_{q}^{p}(w_{1}), r_{q}^{q}(w_{1}))\) at which we can insert this loop into both runs on t_p. This approach would work if we could guarantee that \(\mathbf {r}_{q}^{p}(w_{1})\) and \(\mathbf {r}_{q}^{q}(w_{1})\) are never rivals, as then, the simultaneous loops in \(\mathbf {r}_{q}^{p}\) and \(\mathbf {r}_{q}^{q}\) coincide on their weights and removing a loop from \(\mathbf {r}_{q}^{q}\) and moving the simultaneous loop from \({r}_{q}^{p}\) to \({r}_{p}^{p}\) would be weight-preserving.

In fact, our only concern is to not reduce the gap between the weights of the coordinates in I and the non-broken coordinates. Therefore, we consider all positions w ∈pos(t_q) such that \({\mathbf {r}}_{q}^{p}(w)\) and \({\mathbf {r}}_{q}^{q}(w)\) are i-rivals for some i ∈ I, let v_q be prefix-maximal among these positions, and shrink only the subtree at v_q in the way just described, see also Fig. 4. By Lemma 5(ii), there exists a position v_p ∈pos(t_p) such that \((r_{p}^{p}(v_{p}), r_{p}^{q}(v_{p})) = (r_{q}^{p}(v_{q}), r_{q}^{q}(v_{q}))\) and \(\{ (r_{p}^{p}(v_{p}u), r_{p}^{q}(v_{p}u)) \mid u \in \text {pos}(t_{p}\!\!\upharpoonright _{v_{p}}) \} = \{ (r_{q}^{p}(v_{q}u), r_{q}^{q}(v_{q}u)) \mid u \in \text {pos}(t_{q}\!\!\upharpoonright _{v_{q}}) \}\). We let \(\tau _{q}, {\boldsymbol {\rho }}_{q}^{p}, {\boldsymbol {\rho }}_{q}^{q},\rho _{q}^{p},\rho _{q}^{q}\) be the restrictions of \(t_{q}, {\mathbf {r}}_{q}^{p},{\mathbf {r}}_{q}^{q},r_{q}^{p},r_{q}^{q}\) to v_q and we let \(\tau _{p}, {\boldsymbol {\rho }}_{p}^{p}, {\boldsymbol {\rho }}_{p}^{q},\rho _{p}^{p},\rho _{p}^{q}\) be the restrictions of \(t_{p}, {\mathbf {r}}_{p}^{p},{\mathbf {r}}_{p}^{q},r_{p}^{p},r_{p}^{q}\) to v_p. Thus, if we have two positions u₁ <_pu₂ in pos(τ_q) with \(({\boldsymbol {\rho }}_{q}^{p}(u_{1}),{\boldsymbol {\rho }}_{q}^{q}(u_{1})) = ({\boldsymbol {\rho }}_{q}^{p}(u_{2}),{\boldsymbol {\rho }}_{q}^{q}(u_{2}))\), there exists a position u_p ∈pos(τ_p) with \((\rho _{p}^{p}(u_{p}), \rho _{p}^{q}(u_{p})) = (\rho _{q}^{p}(u_{1}), \rho _{q}^{q}(u_{1}))\), see also Fig. 5. Moreover, the weights of the simultaneous loops in \(\boldsymbol {\rho }_{q}^{p}\) and \(\boldsymbol {\rho }_{q}^{q}\) now coincide by construction for all coordinates in I.

The subtrees t_p at w_p and t_q at w_q of t are both p-q-reachers, so there exist runs \({\mathbf {r}}_{p}^{p},{\mathbf {r}}_{p}^{q}\) on t_p reaching p and q, respectively, and runs \(\mathbf {r}_{q}^{p},\mathbf {r}_{q}^{q}\) on t_q reaching p and q, respectively. The position v_q ∈pos(t_q) is prefix-maximal among all positions w for which \({\mathbf {r}}_{q}^{p}(w)\) and \({\mathbf {r}}_{q}^{q}(w)\) are i-rivals

Full size image

Top: There exists a position v_p ∈pos(t_p) such that \((r_{p}^{p}(v_{p}), r_{p}^{q}(v_{p})) = (r_{q}^{p}(v_{q}), r_{q}^{q}(v_{q}))\) and such that for every \(u_{q} \in \text {pos}(t_{q}\!\!\upharpoonright _{v_{q}})\), there exists a position \(u_{p} \in \text {pos}(t_{p}\!\!\upharpoonright _{v_{p}})\) with \(({r}_{p}^{p}(v_{p}u_{p}), {r}_{p}^{q}(v_{p}u_{p})) = ({r}_{q}^{p}(v_{q}u_{q}), {r}_{q}^{q}(v_{q}u_{q}))\). Bottom: Moving a loop from \(\boldsymbol {\rho }_{q}^{p}\) and \(\boldsymbol {\rho }_{q}^{q}\) on τ_q to \({\rho }_{p}^{p}\) and \({\rho }_{p}^{q}\) on τ_p

Full size image

In particular, removing a loop from \({\boldsymbol {\rho }}_{q}^{q}\) and moving the corresponding simultaneous loop from \(\boldsymbol {\rho }_{q}^{p}\) to \(\boldsymbol {\rho }_{p}^{p}\) does not influence the weights for the coordinates in I. We let J = {j₁,…,j_H} be the set of all coordinates such that for some position w ∈pos(τ_q), the state \(\boldsymbol {\rho }_{q}^{q}(w)\) is a j-rival. We note that \(I \subseteq J\) due to ε ∈pos(τ_q) and Lemma 12.

Assume that by moving loops as above we have transformed our trees and runs \(\tau _{q},\tau _{p},\rho _{p}^{p},\rho _{p}^{q}\) into trees and runs \(\tau _{q}^{\prime },\tau _{p}^{\prime },\rho _{p}^{p\prime },\rho _{p}^{q\prime }\) where now \(\text {height}(\tau _{q}^{\prime }) \leq |{\mathbf {Q}}|^{2}\). Intuitively, we will now shrink the tree \(\tau _{p}^{\prime }\) and replace \(\tau _{q}^{\prime }\) by the resulting tree. However, we still need to ensure that for every coordinate j ∈ J, there exists some position w in \(\text {pos}(\tau _{p}^{\prime })\) such that \(\rho _{p}^{p\prime }(w)\) and \(\rho _{p}^{q\prime }(w)\) are j-rivals and such that for some j-\(\rho _{p}^{p\prime }(w)\)-\(\rho _{p}^{q\prime }(w)\)-distinguisher s, all deterministic automata reach w with a state which can loop in s. We do so by choosing for every j_k ∈ J a position w such that \(\rho _{p}^{p\prime }(w)\) and \(\rho _{p}^{q\prime }(w)\) are j_k-rivals and a j_k-\(\rho _{p}^{p\prime }(w)\)-\(\rho _{p}^{q\prime }(w)\)-distinguisher s_k and inserting \(s_{k}^{|{{\varXi }}|}\) at w, where we recall that \({{\varXi }} = {Q}_{1} \times {\ldots } {Q}_{N} \times {Q}^{2}\). This results in a tree \(\tau _{p}^{\prime \prime }\) with runs \({\rho }_{p}^{p\prime \prime }\) and \({\rho }_{p}^{q\prime \prime }\). We assume the deterministic automata \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{N}\) to be complete, so each deterministic automaton \(\mathcal {A}_{n}\) possesses a run ρ_n on \(\tau _{p}^{\prime \prime }\). We consider the runs \(\rho _{1},\ldots ,\rho _{N},{\rho }_{p}^{p\prime \prime },{\rho }_{p}^{q\prime \prime }\) in parallel as a quasi-run \(\bar {\rho }\) on \(\tau _{p}^{\prime \prime }\) with states in Ξ. By pigeonhole principle, for each j_k the quasi-run \(\bar {\rho }\) loops with a state \(\bar {p}_{k}\) in a Γ-word \(\bar {s}_{k} = s_{k}^{n_{k}}\) with 1 ≤ n_k ≤|Ξ|, see also Fig. 6.

Some power \(\bar {s}_{k}\) of s_k loops a state \(\bar {p}_{k}\) in all runs \(\rho _{1},\ldots ,\rho _{N},\rho _{p}^{p\prime \prime },\rho _{p}^{q\prime \prime }\) simultaneously. Each state \(\bar {p}_{k}\) still occurs in \(\bar {\rho }^{\prime }\) after removing loops from \(\bar {\rho }\) to obtain from \(\tau _{p}^{\prime \prime }\) a tree \(\tau _{p}^{\prime \prime \prime }\) of height at most |Ξ|²

Full size image

For our final substitution, we remove loops from \(\bar {\rho }\) while ensuring that such a removal does not influence the set of states visited by our quasi-run. This allows us to shrink \(\tau _{p}^{\prime \prime }\) and \(\bar {\rho }\) to a tree \(\tau _{p}^{\prime \prime \prime }\) of height at most |Ξ|² and a quasi-run \(\bar {\rho }^{\prime }\).

In t, we substitute \(\tau _{p}^{\prime \prime }\) into v_p and \(\tau _{p}^{\prime \prime \prime }\) into v_q to obtain a tree \(t^{\prime }\) with an accepting run \(r^{\prime } \in \text {Acc}_{\mathcal {U}}(t^{\prime })\). The runs on the substituted subtrees are given by \(\rho _{p}^{p\prime \prime }\) and the last entry of \(\bar {\rho }^{\prime }\). For every j_k ∈ J, there exist positions \({u_{k}^{p}} \in \text {pos}(\tau _{p}^{\prime \prime })\) and \({u_{k}^{q}} \in \text {pos}(\tau _{p}^{\prime \prime \prime })\) such that \(\bar {s}_{k}\) is a j_k-\({r}^{\prime }(w_{p}v_{p}{u_{k}^{p}})\)-\({r}^{\prime }(w_{q}v_{q}{u_{k}^{q}})\)-distinguisher, each deterministic automaton \(\mathcal {A}_{n}\) reaches \(w_{p}v_{p}{u_{k}^{p}}\) and \(w_{q}v_{q}{u_{k}^{q}}\) with the same state, and each \(\mathcal {A}_{n}\) loops in this state with \(\bar {s}_{k}\). We then consider the Ramsey number R = R(2|J|,MN,2|J| + 2), i.e., for every set X of cardinality at least R and every 2|J|-MN-coloring of X, there exists a subset \(Y \subseteq X\) of cardinality 2|J| + 2 whose 2|J|-subsets are all colored with the same color. For every 2|J|-subset \(\zeta = \{\zeta _{1}, \ldots , \zeta _{2|J|}\} \subseteq \{1,\ldots ,R\}\) with ζ₁ < … < ζ_2|J|, we define the tree t_ζ by inserting \(\bar {s}_{k}^{\zeta _{2k-1}}\) at \(w_{p}v_{p}{u_{k}^{p}}\) and \(\bar {s}_{k}^{\zeta _{2k}}\) at \(w_{q}v_{q}{u_{k}^{q}}\) for each j_k ∈ J. Then we define the color of ζ as the pair (j, n) ∈{1,…,M}×{1,…,N} such that the unique accepting run of \({\mathcal {U}}\) on t_ζ has its maximum weight in coordinate j and such that \(\mathcal {A}_{n}\) assigns the maximum weight to t_ζ among all the deterministic automata. We can show that in fact, all colors assigned this way are from J ×{1,…,N}. By choice of R, we find 2|J| + 2 integers ζ₁ < ⋯ < ζ_2|J|+ 2 in {1,…,R} such that {ζ₁,⋯ ,ζ_2|J|+ 2}∖{ζ_2k, ζ_2k+ 2}, {ζ₁,⋯ ,ζ_2|J|+ 2}∖{ζ_2k− 1, ζ_2k+ 2}, and {ζ₁,⋯ ,ζ_2|J|+ 2}∖{ζ_2k, ζ_2k+ 1} are all colored with the same color (j_k, n). With the same reasoning as earlier, we obtain the contradiction that \(\bar {s}_{k}\) is not a j_k-distinguisher.

We now give a more detailed presentation of the proof. By assumption, there exist two prefix-independent positions w_p, w_q ∈pos(t) with r(w_p) = p and r(w_q) = q. We may assume that w_p <_lw_q. We let \((t_{p},{\mathbf {r}}_{p}^{p}) = (t,{\mathbf {r}}) \!\!\upharpoonright _{w_{p}}\) and \((t_{q},{\mathbf {r}}_{q}^{q}) = (t,{\mathbf {r}}) \!\!\upharpoonright _{w_{q}}\). Furthermore, by Lemma 5(v) we may write p = (p, P, V ) and q = (q, P, V ) with p, q ∈ Q, \(P \subseteq {Q}\), and \(V \subseteq {Q}^{4} \times \mathcal {P}({Q}^{2} )\).

By Lemma 5(v), there exist runs \({\mathbf {r}}_{p}^{q} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t_{p}, {\mathbf {q}})\) and \({\mathbf {r}}_{q}^{p} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t_{q}, {\mathbf {p}})\). We consider the set \(\{w \in \text {pos}(t_{q}) \mid {\mathbf {r}}_{q}^{p}(w)\) and \({\mathbf {r}}_{q}^{q}(w)\) are i-rivals for some i ∈ I} and let v_q be a prefix-maximal position from this set. Note that this set is non-empty as it contains ε. We let \(\tau _{q} = t_{q} \!\!\upharpoonright _{v_{q}}\), \({\boldsymbol {\rho }}_{q}^{p} = {\mathbf {r}}_{q}^{p} \!\!\upharpoonright _{v_{q}}\), and \({\boldsymbol {\rho }}_{q}^{q} = {\mathbf {r}}_{q}^{q} \!\!\upharpoonright _{v_{q}}\). Furthermore, we let \({\mathbf {p}}^{\prime } = {\boldsymbol {\rho }}_{q}^{p}(\varepsilon )\), \({\mathbf {q}}^{\prime } = {\boldsymbol {\rho }}_{q}^{q}(\varepsilon )\), \(p^{\prime } = \pi _{1}({\mathbf {p}}^{\prime })\), and \(q^{\prime } = \pi _{1}({\mathbf {q}}^{\prime })\), see also Fig. 4. Also, we let J = {j ∈{1,…,M}∣ there exists u ∈pos(τ_q) such that \({\boldsymbol {\rho }}_{q}^{p}(u)\) and \({\boldsymbol {\rho }}_{q}^{q}(u)\) are j-rivals}. Note that \({\mathbf {p}}^{\prime }\) and \({\mathbf {q}}^{\prime }\) are i-rivals for some i ∈ I, so by Lemma 7 there exists an i-\(\mathbf {p}^{\prime }\)-\(\mathbf {q}^{\prime }\)-distinguisher of height at most 4|Q|². Thus, we obtain \(I \subseteq J\) from Lemma 12.

We let \(r_{q}^{q} = \pi _{1} \circ {\mathbf {r}}_{q}^{q}\), \(r_{q}^{p} = \pi _{1} \circ {\mathbf {r}}_{q}^{p}\), and \(Y = \{ (r_{q}^{p}(v_{q}u), r_{q}^{q}(v_{q}u)) \in {Q}^{2} \mid u \in \text {pos}(\tau _{q})\}\), then by Lemma 5(ii) we have \((p, q, p^{\prime }, q^{\prime }, Y) \in V\). Therefore, again by Lemma 5(ii), there exist runs \(r_{p}^{p} \in \text {Run}_{\mathcal {U}}(t_{p}, p)\) and \(r_{p}^{q} \in \text {Run}_{\mathcal {U}}(t_{p}, q)\) and a position v_p ∈pos(t_p) with \(r_{p}^{p}(v_{p}) = p^{\prime }\) and \(r_{p}^{q}(v_{p}) = q^{\prime }\) such that \(Y = \{ (r_{p}^{p}(v_{p}u), r_{p}^{q}(v_{p}u)) \in {Q}^{2} \mid u \in \text {pos}(t_{p} \!\!\upharpoonright _{v_{p}})\}\).

Since \(\boldsymbol {\mathcal {U}}\) is unambiguous, the sets \(\text {Run}_{\mathcal {U}}(t_{p}, p)\) and \(\text {Run}_{\mathcal {U}}(t_{p}, q)\) are singletons. It follows that \(r_{p}^{p} = \pi _{1} \circ {\mathbf {r}}_{p}^{p}\) and \(r_{p}^{q} = \pi _{1} \circ {\mathbf {r}}_{p}^{q}\).

We let \(\tau _{p} = t_{p} \!\!\upharpoonright _{v_{p}}\), \(\rho _{p}^{p} = r_{p}^{p} \!\!\upharpoonright _{v_{p}}\), and \(\rho _{p}^{q} = r_{p}^{q} \!\!\upharpoonright _{v_{p}}\). Then in conclusion, we see that for every position u_q ∈pos(τ_q), there exists a position u_p ∈pos(τ_p) with \((\rho _{p}^{p}(u_{p}), \rho _{p}^{q}(u_{p})) = (\rho _{q}^{p}(u_{q}), \rho _{q}^{q}(u_{q}))\), see also Fig. 5.

♣ We now remove cycles from \({\boldsymbol {\rho }}_{q}^{p}\) and \({\boldsymbol {\rho }}_{q}^{q}\) in parallel as follows. If height(τ_q) ≤|Q|², we do nothing. Otherwise, by pigeonhole principle, there exist two positions u₁, u₂ ∈pos(τ_q) with u₁ <_pu₂ such that \(({\boldsymbol {\rho }}_{q}^{p}(u_{1}),{\boldsymbol {\rho }}_{q}^{q}(u_{1})) = ({\boldsymbol {\rho }}_{q}^{p}(u_{2}), {\boldsymbol {\rho }}_{q}^{q}(u_{2}))\). On the Γ-word \(s = \tau _{q}\langle {\diamond } \to u_{2} \rangle \!\!\upharpoonright _{u_{1}}\), we thus obtain two runs looping in a state by defining \({\boldsymbol {\rho }}^{p}(w) = {\boldsymbol {\rho }}_{q}^{p}(u_{1}w)\) and \({\boldsymbol {\rho }}^{q}(w) = {\boldsymbol {\rho }}_{q}^{q}(u_{1}w)\).

We let \(\rho ^{p} = \pi _{1} \circ {\boldsymbol {\rho }}^{p}\) and \(\rho ^{q} = \pi _{1} \circ {\boldsymbol {\rho }}^{q}\), then there exists u_p ∈pos(τ_p) with \((\rho _{p}^{p}(u_{p}), \rho _{p}^{q}(u_{p})) = (\rho ^{p}(\varepsilon ),\rho ^{p}(\varepsilon ))\). We insert the Γ-word s into τ_p at u_p to obtain a tree \(\tau _{p}^{\prime }\) and two runs \(\rho _{p}^{p\prime }\) and \(\rho _{p}^{q\prime }\) on \(\tau _{p}^{\prime }\) by and . Moreover, we remove the loops on s from the runs on τ_q by \((\tau _{q}^{\prime },{\boldsymbol {\rho }}_{q}^{p\prime }) = (\tau _{q},{\boldsymbol {\rho }}_{q}^{p}) \langle (\tau _{q},{\boldsymbol {\rho }}_{q}^{p}) \!\!\upharpoonright _{u_{2}} \to u_{1} \rangle \) and \((\tau _{q}^{\prime },{\boldsymbol {\rho }}_{q}^{q\prime }) = (\tau _{q},{\boldsymbol {\rho }}_{q}^{q}) \langle (\tau _{q},{\boldsymbol {\rho }}_{q}^{q}) \!\!\upharpoonright _{u_{2}} \to u_{1} \rangle \).

For every i ∈{1,…,M}∖ J, we have \({\textbf {wt}}_{i}^{{\diamond }}(s, {\boldsymbol {\rho }}^{p}) = {\textbf {wt}}_{i}^{{\diamond }}(s, {\boldsymbol {\rho }}^{q})\). Likewise, by choice of v_q, we have \(\text {wt}_{i}^{{\diamond }}(s, {\boldsymbol {\rho }}^{p}) = \text {wt}_{i}^{{\diamond }}(s, {\boldsymbol {\rho }}^{q})\) for every i ∈ I. This implies in particular that for every i ∈ I∪({k₁ + 1,…,M}∖ J) we have \(\text {wt}_{i}(\tau _{p}^{\prime }, \rho _{p}^{p\prime }) + {\textbf {wt}}_{i}(\tau _{q}^{\prime }, {\boldsymbol {\rho }}_{q}^{q\prime }) = \text {wt}_{i}(\tau _{p}, \rho _{p}^{p}) + {\textbf {wt}}_{i}(\tau _{q}, {\boldsymbol {\rho }}_{q}^{q})\).

We continue this procedure of moving loops until we arrive at a tree \(\tau _{q}^{\prime }\) with \(\text {height}(\tau _{q}^{\prime }) \leq |{\mathbf {Q}}|^{2}\). We then have two runs \({\boldsymbol {\rho }}_{q}^{p\prime } \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(\tau _{q}^{\prime }, {\mathbf {p}}^{\prime })\) and \({\boldsymbol {\rho }}_{q}^{q\prime } \in \text {Run}_{{\boldsymbol {\mathcal {U}}}} (\tau _{q}^{\prime }, {\mathbf {q}}^{\prime })\) on \(\tau _{q}^{\prime }\) and a tree \(\tau _{p}^{\prime }\) with runs \(\rho _{p}^{p\prime } \in \text {Run}_{\mathcal {U}}(\tau _{p}^{\prime }, p^{\prime })\) and \(\rho _{p}^{q\prime } \in \text {Run}_{\mathcal {U}}(\tau _{p}^{\prime }, q^{\prime })\).

♣ We let j₁,…,j_H be an enumeration of J. We let k ∈{1,…,H} and let u ∈pos(τ_q) be position such that \({\boldsymbol {\rho }}_{q}^{p}(u)\) and \({\boldsymbol {\rho }}_{q}^{q}(u)\) are j_k-rivals. Then by Lemma 7, there exists a j_k-\({\boldsymbol {\rho }}_{q}^{p}(u)\)-\({\boldsymbol {\rho }}_{q}^{q}(u)\)-distinguisher s_k with height(s_k) ≤ 4|Q|². We let \({\mathbf {r}}_{k}^{p} \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\boldsymbol {\rho }}_{q}^{p}(u), s_{k}, {\boldsymbol {\rho }}_{q}^{p}(u))\) and \({\mathbf {r}}_{k}^{q} \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\boldsymbol {\rho }}_{q}^{q}(u), s_{k}, {\boldsymbol {\rho }}_{q}^{q}(u))\). Furthermore, we let \(u_{k} \in \tau _{p}^{\prime }\) be a position with \((\rho _{p}^{p\prime }(u_{k}), \rho _{p}^{q\prime }(u_{k})) = (\rho _{q}^{p}(u), \rho _{q}^{q}(u))\). We know that such a position exists from the way we obtained \(\tau _{p}^{\prime },\rho _{p}^{p\prime }\), and \(\rho _{p}^{q\prime }\) from \(\tau _{p},\rho _{p}^{p}\), and \(\rho _{p}^{q}\).

We may assume that j₁,…,j_H are ordered such that u₁ ≤_l… ≤_lu_H. Then for every k ∈{1,…,H}, we insert \((s_{k},\pi _{1} \circ {\mathbf {r}}_{k}^{p})^{|{{\varXi }}|}\) into \((\tau _{p}^{\prime },\rho _{p}^{p\prime })\) and \((s_{k},\pi _{1} \circ {\mathbf {r}}_{k}^{q})^{|{{\varXi }}|}\) into \((\tau _{p}^{\prime },\rho _{p}^{q\prime })\) at u_k by and . For sake of simplicity, we assume that the Γ-words we inserted are still below the positions u₁,…,u_H.

♣ We assume that the deterministic automata \(\mathcal {A}_{1}, \ldots , \mathcal {A}_{N}\) are all complete, thus for every n ∈{1,…,N} there exists a run \(\rho _{n} \in \text {Run}_{\mathcal {A}_{n}}(\tau _{p}^{\prime \prime })\). We define \(\bar {\rho } \colon \text {pos}(\tau _{p}^{\prime \prime }) \to {{\varXi }}\) by \(\bar {\rho }(w) = (\rho _{1}(w), \ldots , \rho _{N}(w), \rho _{p}^{p\prime \prime }(w), \rho _{p}^{q\prime \prime }(w))\) and let v_k = ◊₁(s_k). For every k ∈{1,…,H}, we can find by pigeonhole principle two integers m, n ∈{0,…,|Ξ|} with m < n such that \(\bar {\rho }(u_{k}{v_{k}^{m}}) = \bar {\rho }(u_{k}{v_{k}^{n}})\). We let \({u_{k}^{p}} = u_{k}{v_{k}^{m}}\), \(\bar {p}_{k} = \bar {\rho }(u_{k}{v_{k}^{m}})\), n_k = m − n, and \(\bar {s}_{k} = s_{k}^{n_{k}}\), see also Fig. 6. We remove loops from \(\tau _{p}^{\prime \prime }\) and \(\bar {\rho }\) as follows. If \(\text {height}(\tau _{p}^{\prime \prime }) \leq |{{\varXi }}|^{2}\), we do nothing. Otherwise, we let \(\text {seen}(w) = \{ \bar {\rho }(ww^{\prime }) \mid w^{\prime } \in \text {pos}(\tau _{p}^{\prime \prime }\!\!\upharpoonright _{w})\}\) for \(w \in \text {pos}(\tau _{p}^{\prime \prime })\) and choose \(w \in \text {pos}(\tau _{p}^{\prime \prime })\) with \(|w| = \text {height}(\tau _{p}^{\prime \prime }) > |{{\varXi }}|^{2}\). Then for every two positions \(w_{1}, w_{2} \in \text {pos}(\tau _{p}^{\prime \prime })\) with w₁ <_pw₂, we have \(\emptyset \neq \text {seen}(w_{2}) \subseteq \text {seen}(w_{1}) \subseteq {{\varXi }}\). Thus, there exist by pigeonhole principle two positions \(w_{1},w_{2} \in \text {pos}(\tau _{p}^{\prime \prime })\) such that w₁ <_pw₂ ≤_pw and \((\bar {\rho }(w_{1}),\text {seen}(w_{1})) = (\bar {\rho }(w_{2}),\text {seen}(w_{2}))\). We cut this cycle from \(\tau _{p}^{\prime \prime }\) by defining \((\tau _{p}^{\prime \prime \prime },\bar {\rho }^{\prime }) = (\tau _{p}^{\prime \prime },\bar {\rho }) \langle (\tau _{p}^{\prime \prime },\bar {\rho }) \!\!\upharpoonright _{w_{2}} \to w_{1} \rangle \). We continue this procedure until we obtain a tree \(\tau _{p}^{\prime \prime \prime }\) with \(\text {height}(\tau _{p}^{\prime \prime \prime }) \leq |{{\varXi }}|^{2}\) together with a quasi-run \(\bar {\rho }^{\prime }\). We note that by construction, we have \(\bar {\rho }^{\prime }(\text {pos}(\tau _{p}^{\prime \prime \prime })) = \bar {\rho }(\text {pos}(\tau _{p}^{\prime \prime }))\), so for every k ∈{1,…,H}, there exists \({u_{k}^{q}} \in \text {pos}(\tau _{p}^{\prime \prime \prime })\) with \(\bar {\rho }^{\prime }({u_{k}^{q}}) = \bar {p}_{k}\). We denote the projections on Ξ to the respective coordinates by π₁,…,π_N+ 2. Then we also have \(\pi _{n} \circ \bar {\rho }^{\prime } \in \text {Run}_{\mathcal {A}_{n}}(\tau _{p}^{\prime \prime \prime })\) for every n ∈{1,…,N}, \(\pi _{N+1} \circ \bar {\rho }^{\prime } \in \text {Run}_{\mathcal {U}}(\tau _{p}^{\prime \prime \prime }, p^{\prime })\), and \(\pi _{N+2} \circ \bar {\rho }^{\prime } \in \text {Run}_{\mathcal {U}}(\tau _{p}^{\prime \prime \prime }, q^{\prime })\).

We now consider the tree \(t^{\prime }\) and the accepting run \(r^{\prime } \in \text {Acc}_{\mathcal {U}}(t^{\prime })\) defined by \((t^{\prime }, r^{\prime }) = (t, \pi _{1} \circ {\mathbf {r}}) \langle (\tau _{p}^{\prime \prime }, \rho _{p}^{p\prime \prime }) \to w_{p}v_{p} \rangle \langle (\tau _{p}^{\prime \prime \prime }, \pi _{N+2} \circ \bar {\rho }^{\prime }) \to w_{q}v_{q} \rangle \). Let k ∈{0,…,H}. We have \((r^{\prime }(w_{p} v_{p} {u_{k}^{p}}),r^{\prime }(w_{q} v_{q} {u_{k}^{q}})) = (\pi _{N+1} \circ \bar {\rho }({u_{k}^{p}}), \pi _{N+2} \circ \bar {\rho }^{\prime }({u_{k}^{q}})) = (\pi _{1} \circ {\mathbf {r}}_{k}^{p}(\varepsilon ), \pi _{1} \circ {\mathbf {r}}_{k}^{q}(\varepsilon ))\). Moreover, for every n ∈{1,…,N} we see that for the unique run r_n of \(\mathcal {A}_{n}\) on \(t^{\prime }\) we have \((r_{n}(w_{p} v_{p} {u_{k}^{p}}), r_{n}(w_{q} v_{q} {u_{k}^{q}})) = (\pi _{n} \circ \bar {\rho }({u_{k}^{p}}), \pi _{n} \circ \bar {\rho }^{\prime }({u_{k}^{q}})) = (\pi _{n} (\bar {p}_{k} ),\pi _{n} (\bar {p}_{k} ))\). Also, the Γ-word \(\bar {s}_{k}\) loops in \(\pi _{n} (\bar {p}_{k})\).

We consider the weight of \(r^{\prime }\) on \(t^{\prime }\). By construction, we have for every i ∈{1,…,M} that \({\text {wt}}_{i}(t, {\mathbf {r}}) - \text {wt}_{i}(\tau _{p}, \rho _{p}^{p}) - \text {wt}_{i}(\tau _{q}, \rho _{q}^{q}) = \text {wt}_{i}(t^{\prime },r^{\prime }) - \text {wt}_{i}(\tau _{p}^{\prime \prime }, \rho _{p}^{p\prime \prime }) - \text {wt}_{i}(\tau _{p}^{\prime \prime \prime }, \pi _{N+2} \circ \bar {\rho }^{\prime }).\) Let i ∈ I∪({1,…,M}∖ J), then we have

and

Thus, we see that

We write \((\kappa _1, \ldots , \kappa _M) = \text {wt}_{\mathcal {U}}(t^{\prime }, r^{\prime })\) and recall that \(I \subseteq J\). Then for every i ∈ I and \(i^{\prime } \in \{1, \ldots , M\} \setminus J\), we have by choice of C that

We consider the Ramsey number R_H as above and the set {1,…,R_H}. For every 2H-subset \(\zeta \subseteq \{1, \ldots , R_H\}\), we define a color in {1,…,M}×{1,…,N} as follows. We assume that ζ = {ζ₁,…,ζ_2H} with ζ₁ < … < ζ_2H and let t_ζ be the tree obtained from \(t^{\prime }\) by inserting the Γ-word \(\bar {s}_k^{\zeta _{2k-1}}\) at \(w_p v_p u_k^p\) and the Γ-word \(\bar {s}_k^{\zeta _{2k}}\) at \(w_q v_q u_k^q\) for every k ∈{1,…,H}. Then writing \(\llbracket {\mathcal {U}}\rrbracket (t_{\zeta }) = ({\kappa }_{1}^{\zeta }, \ldots , {\kappa }_{M}^{\zeta })\), we let the color of ζ be the pair (j, n) consisting of the smallest j ∈{1,…,M} with \({\kappa }_{j}^{\zeta } = {\max \limits } \{ {\kappa }_{1}^{\zeta }, \ldots , {\kappa }_{M}^{\zeta }\}\) and the smallest n ∈{1,…,N} with \(\llbracket {\mathcal {A}_n}\rrbracket (t_{\zeta }) = {\kappa }_{j}^{\zeta }\). We note that for every i ∈{1,…,M}, we have

Thus, for every i ∈ I and \(i^{\prime } \in \{1, \ldots , M\} \setminus J\), we have

In particular, all 2H-subsets are colored with a color from J ×{1,…,N}.

By assumption on R_H, there now exists a subset \(Y \subseteq \{1, \ldots , R_H\}\) of cardinality 2H + 2 whose 2H-subsets are all colored with the same color. Let ζ₁ < … < ζ_2H+ 2 be the an enumeration of Y and let (j, n) ∈ J ×{1,…,N} such that all 2H-subsets of Y are colored by (j, n).

We let k ∈{1,…,H} with j_k = j and let ζ = {ζ₁,…,ζ_2H+ 2}∖{ζ_2k, ζ_2k+ 2}. Furthermore, we let ζ^+p = {ζ_2k}∪ζ ∖{ζ_2k− 1} and ζ^+q = {ζ_2k+ 2}∪ζ ∖{ζ_2k+ 1}. With \(z = \text {wt}^{{\diamond }}_{\mathcal {A}_n}(\pi _n(\bar {p}_k), \bar {s}_k, \pi _n(\bar {p}_k))\), we then have

and

Thus, we obtain \(n_k{\textbf {wt}}_j(s_k, {\mathbf {r}}_k^p) = z = n_k{\textbf {wt}}_j(s_k, {\mathbf {r}}_k^q)\), which is a contradiction to the choice of s_k. □

3.3 Sufficiency

In this section, we show that if \({\boldsymbol {\mathcal {U}}}\) is not broken, then \(\llbracket {\mathcal {A}}\rrbracket \) is finitely sequential. Although our approach is inspired by an idea in [26], we are not sure whether we employ this idea in the same way. Our general strategy is to show that, if \(\boldsymbol {\mathcal {U}}\) is not broken, then we can construct M unambiguous max-plus-WTA which all do not satisfy the tree fork property and whose pointwise maximum is equivalent to \(\llbracket {\mathcal {A}}\rrbracket \). By Theorem 1, we obtain a finitely sequential representation of \(\mathcal {A}\) by constructing one for each of the unambiguous max-plus-WTA. We essentially construct the unambiguous automata by removing problematic runs from \(\boldsymbol {\mathcal {U}}\) and then projecting to the coordinates 1,…,M.

Our fundamental idea is the following. Assume that p and q are i-rivals, that (t, r) is i-p-q-broken, and that the maximum of \(\text {wt}_{\boldsymbol {\mathcal {U}}}(t,\mathbf {r})\) is in coordinate i. Furthermore, assume that in r, some i-p-q-distinguisher s loops N times in p, where \(N \in \mathbb {N}\) is some integer, and that s loops in p with a smaller weight, in coordinate i, than in q. By removing the loops of s in p from (t, r) and inserting them back as loops in q, we increase the weight of coordinate i, but leave the weights of all non-broken coordinates unchanged. If height(s) ≤ 4|Q|², we can even assert that the weight of coordinate i increases by Nξ, where ξ is defined as in Section 3.2. Thus, in this latter case, coordinate i then dominates all non-broken coordinates by a margin of at least Nξ. We know that i cannot dominate all non-broken coordinates by an arbitrarily large margin, so N cannot be arbitrarily large. In turn, this means that if N is sufficiently large, then \(\text {wt}_{{\boldsymbol {\mathcal {U}}}}(t,{\mathbf {r}})\) cannot take its maximum weight in coordinate i. This implies that the weight of coordinate i can be discarded if some distinguisher loops in both of its rivals too many times.

We employ this idea in the following way. First, we identify an integer N such that looping in an i-distinguisher more than N times ensures coordinate i to be dominated by other coordinates. Then we construct for every coordinate an automaton which checks every run of \(\boldsymbol {\mathcal {U}}\) for i-brokenness and detects for every i-distinguisher of height at most 4|Q|² whether it is looped N + 1 times. Finally, we restrict the runs of \(\boldsymbol {\mathcal {U}}\) to those which are not detected, simply using a product construction, and apply the i-th projection to all weight vectors. As we will show, the resulting automata are unambiguous and do not satisfy the tree fork property. We do not need to detect loops of arbitrarily large distinguishers since by Lemma 7, every large distinguisher contains a distinguisher of height at most 4|Q|² by truncating. We begin by introducing the following notions.

We define the set \(R = \{ (i,{\mathbf {p}},{\mathbf {q}},s) \in \{1, \ldots , M\} \times {\mathbf {Q}}^2 \times T_{{{\varGamma }}_{\diamond }} \mid i \in \{1, \ldots , M\}\), s is an i-p-q-distinguisher, height(s) ≤ 4|Q|²}, let \(\tilde {C}\) be as in Theorem 4, let ξ be as in Section 3.2, and define the constant \(N = \lceil {M\tilde {C}\xi ^{-1}}\rceil \).

Definition 5

Let t ∈ T_Γ, \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\), (i, p, q, s) ∈ R, \({\mathbf {r}}_{{\mathbf {p}}} \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {p}},s,{\mathbf {p}})\), and \({\mathbf {r}}_{{\mathbf {q}}} \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {q}},s,{\mathbf {q}})\). We call (t, r)

• (i, p, q, s)-fork-broken if there exist positions u_p, v_p, w_p, w_q, u_q, v_q ∈pos(t) with v_q <_pu_q ≤_pw_q <_pw_p ≤_pv_p <_pu_p such that \((t, \mathbf {r})\langle (\diamond , \mathbf {r}(u_{\mathbf {p}})) \rightarrow \) r(w_q) = q, and \(t \langle {\diamond } \to w_{{\mathbf {p}}} \rangle \!\!\upharpoonright _{w_{{\mathbf {q}}}}\) is a p-q-fork.

• (i, p, q, s)-split-broken if there exist positions u_p, v_p, u_q, v_q ∈pos(t) such that v_p <_pu_p, v_q <_pu_q, v_p and v_q are prefix-independent, \((t, \mathbf {r})\langle (\diamond , \mathbf {r}(u_{\mathbf {p}})) \rightarrow \), and .

For an illustration, see also Fig. 7.

An illustration of (i, p, q, s)-fork-brokenness and (i, p, q, s)-split-brokenness

Full size image

The first observation we make is that if some (t, r) is (i, p, q, s)-broken for a tuple (i, p, q, s) ∈ R, then the weight of coordinate i is strictly dominated by another coordinate.

Lemma 14

Let t ∈ T_Γ and \({\mathbf {r}} \in \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t)\). If (t, r) is (i, p, q, s)-broken for some (i, p, q, s) ∈ R, then \({\mathbf {wt}}_i(t,\mathbf {r}) < \llbracket {\mathcal {A}}\rrbracket (t)\).

Proof

Let t ∈ T_Γ and \({\mathbf {r}} \in \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t)\) be such that (t, r) is (i, p, q, s)-broken for (i, p, q, s) ∈ R. Furthermore, let u_p, v_p, u_q, v_q ∈pos(t) be as in the definition of (i, p, q, s)-brokenness. We may assume that \({\text {wt}}^{{\diamond }}_i({\mathbf {p}},s,{\mathbf {p}}) < {\text {wt}}^{{\diamond }}_i({\mathbf {q}},s,{\mathbf {q}})\), let \({\mathbf {r}}_{{\mathbf {p}}} \in \text {Run}^{\diamond }_{\boldsymbol {\mathcal {U}}}(\mathbf {p},s,\mathbf {p})\), \({\mathbf {r}}_{{\mathbf {q}}} \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {q}},s,{\mathbf {q}})\), and let \(g \colon \text {pos}(s^{N+1}) \to \text {pos}((t, {\mathbf {r}}) \langle ({\diamond }, {\mathbf {p}}) \to u_{{\mathbf {p}}} \rangle \!\!\upharpoonright _{v_{{\mathbf {p}}}})\) be as in the definition of a truncation. We let (s₁, r₁), …, (s_n, r_n) be an enumeration of the family \(\left ((t,{\mathbf {r}})\langle ({\diamond },{\mathbf {r}}(v_{{\mathbf {p}}}g(wl)))\to v_{{\mathbf {p}}}g(wl) \rangle \!\!\!\!\upharpoonright _{v_{{\mathbf {p}}}g(w)l}\right )_{w \in \text {pos}(s^{N+1}), l \in \{1, \ldots , \text {rk}_{{{\varGamma }}_{\diamond }}(s^{N+1}(w))\}}\) and we let \((t^{\prime },{\mathbf {r}}^{\prime }) = (t,{\mathbf {r}}) \langle (t,{\mathbf {r}})\!\!\!\!\!\!\upharpoonright _{u_{\mathbf {p}}} \to v_{\mathbf {p}} \rangle \). Then by Lemma 6(iii), we have \(\text {wt}_{{\boldsymbol {\mathcal {U}}}}(t,{\mathbf {r}}) = \text {wt}_{{\boldsymbol {\mathcal {U}}}}(t^{\prime },{\mathbf {r}}^{\prime })\) + \((N+1)\text {wt}_{{\boldsymbol {\mathcal {U}}}}^{\diamond }(s, {\mathbf {r}}_{{\mathbf {p}}}) + {\sum }_{k = 1}^n \text {wt}_{{\boldsymbol {\mathcal {U}}}}^{\diamond }(s_k, {\mathbf {r}}_k)\). Note that by the definition of a truncation, we have r_k(ε) = r_k(◊₁(s_k)) for all k ∈{1,…,n}. By construction, for every k ∈{1,…,n}, there exists a position u_k ∈pos(s) such that r_k(ε) = r_p(u_k). We may assume that u₁ ≤_l… ≤_lu_n and let . Then with we have \(\text {wt}_{\boldsymbol {\mathcal {U}}}(t,\mathbf {r}) = \text {wt}_{\boldsymbol {\mathcal {U}}}(t^{\prime \prime },\mathbf {r}^{\prime \prime }) + N\text {wt}_{\boldsymbol {\mathcal {U}}}^{\diamond }(s, r_{\mathbf {p}})\).

By choice of t and r, there exists a position \(v \in \text {pos}(t^{\prime \prime })\) with \({\mathbf {r}}^{\prime \prime }(v) = {\mathbf {q}}\). We let . Then we have \({\textbf {wt}}_i(t^{\prime \prime \prime },{\mathbf {r}}^{\prime \prime \prime }) = {\textbf {wt}}_i(t,{\mathbf {r}}) + N ({\textbf {wt}}^{{\diamond }}_i({\mathbf {q}},s,{\mathbf {q}}) - {\textbf {wt}}^{{\diamond }}_i({\mathbf {p}},s,{\mathbf {p}})) \geq {\textbf {wt}}_i(t,{\mathbf {r}}) + M\tilde {C}\). Since \((t^{\prime \prime \prime },{\mathbf {r}}^{\prime \prime \prime })\) is i-p-q-broken, \({\mathbf {r}}^{\prime \prime \prime } \in \text {Acc}_{{\boldsymbol {\mathcal {U}}}}(t^{\prime \prime \prime })\), and we assume \({\boldsymbol {\mathcal {U}}}\) to not be broken, there exists a coordinate j ∈{1,…,M} such that \((t^{\prime \prime \prime },{\mathbf {r}}^{\prime \prime \prime })\) is not j-broken and \({\text {wt}}_j(t^{\prime \prime \prime },{\mathbf {r}}^{\prime \prime \prime }) > {\text {wt}}_i(t^{\prime \prime \prime },{\mathbf {r}}^{\prime \prime \prime }) - M\tilde {C}\); otherwise, we could construct a \(\tilde {C}\)-separable set I like in the proof of Lemma 12, which by Theorem 4 would imply that \(\boldsymbol {\mathcal {U}}\) is broken. Since \((t,\mathbf {r}^{\prime \prime \prime })\) is not j-p-q-broken, we have \({\textbf {wt}}_j(t,{\mathbf {r}}) = {\textbf {wt}}_j(t^{\prime \prime \prime },{\mathbf {r}}^{\prime \prime \prime }) > {\textbf {wt}}_i(t^{\prime \prime \prime },{\mathbf {r}}^{\prime \prime \prime }) - M\tilde {C} \geq {\textbf {wt}}_i(t,{\mathbf {r}})\). □

Next, we show that for every i ∈{1,…,M}, it is a recognizable property whether for a run \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\) on a tree t ∈ T_Γ, (t, r) is (i, p, q, s)-broken for some (i, p, q, s) ∈ R. More precisely, we show the following lemma.

Lemma 15

For every i ∈{1,…,M}, there exists a complete and deterministic FTA \({\mathscr{B}}_i\) over the alphabet Γ ×Q which accepts a tree (t, r) ∈ T_Γ×Q if and only if there does not exist (i, p, q, s) ∈ R such that (t, r) is (i, p, q, s)-broken.

Proof

We employ the generalization of Büchi’s theorem to trees [50,51,52], namely that a tree language is definable using the MSO logic given by the grammar

if and only if it is recognizable by a (complete and deterministic) FTA over Γ ×Q. Here (a, p) ∈Γ×Q, l ∈{1,…,rk(Γ)}, x, y are first order variables, and X is a second order variable, and (t, r) as above corresponds to the structure with universe pos(t) where the interpretation of label_{(a, p)} is the set {w ∈pos(t)∣(t(w),r(w)) = (a, p)} and the interpretation of edge_l is the set {(w, wl)∣w, wl ∈pos(t)} for every l ∈{1,...,rk(Γ)}. We note that the prefix order ≤_p is definable using this logic, so we may use it as well as its strict version <_p in our formulas.

We let (i, p, q, s) ∈ R, \({\mathbf {r}}_{{\mathbf {p}}} \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {p}},s,{\mathbf {p}})\), and \({\mathbf {r}}_{{\mathbf {q}}} \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {q}},s,{\mathbf {q}})\). We let \((s^{\prime },{\mathbf {r}}_{{\mathbf {p}}}^{\prime }) = (s, {\mathbf {r}}_{{\mathbf {p}}})^{N+1}\) and \((s^{\prime },{\mathbf {r}}_{{\mathbf {p}}}^{\prime }) = (s, {\mathbf {r}}_{{\mathbf {q}}})^{N+1}\). We let d₁,…,d_|D| be an enumeration of \(D = \{ d \in {\Delta }_{{\boldsymbol {\mathcal {U}}}} \mid {{{\mu }}}(d) \in \mathbb {Q}^M\}\) and let w₁,…,w_n be an enumeration of \(\text {pos}(s^{\prime })\). Furthermore, we let D(q) = {(q₁,…,q_m, a, q) ∈ D} and D_l(q) = {(q₁,…,q_m, a, q₀) ∈ D∣q_l = q} for q ∈Q and l ∈{1,…,rk(Γ)}. We first define a formula fork(y_q, y_p) which checks for two positions y_q, y_p ∈pos(t) that r(y_q) = q, r(y_p) = p, and that p can loop in the Γ-word \(t \langle {\diamond } \to y_{{\mathbf {p}}} \rangle \!\!\upharpoonright _{y_{{\mathbf {q}}}}\) by

Then we define the formula φ_{(s, p, q)} to check for (i, p, q, s)-brokenness by

Finally, we let \(\varphi _i = \lnot \bigvee _{(i,{\mathbf {p}},{\mathbf {q}},s) \in R} \varphi _{(s,{{\mathbf {p}}},{{\mathbf {q}}})}\) and we let \({\mathscr{B}}_i\) be a complete and deterministic FTA with \({\mathscr{L}}(\varphi _i) = {\mathscr{L}}({\mathscr{B}}_i)\), then \({\mathscr{B}}_i\) accepts (t, r) if and only if there does not exist (i, p, q, s) ∈ R such that (t, r) is (i, p, q, s)-broken. □

In the following, we define M max-plus-WTA \(\mathcal {C}_1, \ldots , \mathcal {C}_M\) over Γ which we claim to all not satisfy the tree fork property and whose pointwise maximum we claim to be equivalent to \(\llbracket {\mathcal {A}}\rrbracket \).

Construction 3

For i ∈{1,…,M}, we let \({\mathscr{B}}_i = (B_i, {{\varGamma }} \times {\mathbf {Q}}, \delta _i, F_i)\) be the automaton we find by Lemma 15. We define \(\mathcal {C}_i = (C_i, {{\varGamma }}, {\mu }_i, {\nu }_i)\) over \(\mathbb {Q}\max\) as the trim part of the automaton \(\mathcal {C}_i^{\prime } = ({\mathbf {Q}} \times B_i, {{\varGamma }}, {\mu }_i^{\prime }, {\nu }_i^{\prime })\) defined for a ∈Γ with rk_Γ(a) = m and (q₀, b₀),…,(q_m, b_m) ∈Q × B_i by

We let π_Q: Q × B_i →Q and \(\pi _{B_i} \colon {\mathbf {Q}} \times B_i \to B_i\) be the projections.

We make the following observations about \(\mathcal {C}_1, \ldots , \mathcal {C}_M\).

Proposition 1

For every tree t ∈ T_Γ and every \(r \in \text {Run}_{\mathcal {C}_i}(t)\), we have \(\pi _{{\mathbf {Q}}} \circ r \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\), \(\text {wt}_{\mathcal {C}_i}(t, r) = {\text {wt}}_i(t, \pi _{{\mathbf {Q}}} \circ r)\), and \(\pi _{B_i} \circ r\) is the unique run of \({\mathscr{B}}_i\) on (t, π_Q ∘ r). In particular, we have \(\llbracket {\mathcal {C}_i}\rrbracket (t) \leq \pi _i(\llbracket {{\boldsymbol {\mathcal {U}}}}\rrbracket (t))\).

We first show that \(\max \limits _{i=1}^M \llbracket {\mathcal {C}_i}\rrbracket = \llbracket {\mathcal {A}}\rrbracket \).

Lemma 16

For every t ∈ T_Γ, we have \(\max \limits _{i=1}^M \llbracket {\mathcal {C}_i}\rrbracket (t) = \llbracket {\mathcal {A}}\rrbracket (t)\).

Proof

Let t ∈ T_Γ. By construction of \({\boldsymbol {\mathcal {U}}}\) we have \(\llbracket {\mathcal {A}}\rrbracket (t) = \max \limits _{i=1}^M \pi _i(\llbracket {{\boldsymbol {\mathcal {U}}}}\rrbracket (t))\). If \(\llbracket {\mathcal {A}}\rrbracket (t) = -\infty \), we have \(-\infty = \max \limits _{i=1}^M \pi _i(\llbracket {{\boldsymbol {\mathcal {U}}}}\rrbracket (t)) \geq \max \limits _{i=1}^M \llbracket {\mathcal {C}_i}\rrbracket (t)\). If \(\llbracket {\mathcal {A}}\rrbracket (t) \neq -\infty \), there exists a run \({\mathbf {r}} \in \text {Run}_{{\boldsymbol {\mathcal {U}}}}(t)\) and an index j ∈{1,…,M} with \({\text {wt}}_j(t,\mathbf {r}) = \pi _j(\llbracket {\boldsymbol {\mathcal {U}}}\rrbracket (t)) = \llbracket {\mathcal {A}}\rrbracket (t)\). By Lemma 14, this implies that (t, r) is not (j, p, q, s)-broken for any (j, p, q, s) ∈ R. From the definition of (j, p, q, s)-brokenness, it is easy to see that the same is true for every subtree \((t,\mathbf {r}) \!\!\upharpoonright _w\) with w ∈pos(t). As \({\mathscr{B}}_j\) is complete, there exists a run \(r_{{\mathscr{B}}_j} \in \text {Run}_{{\mathscr{B}}_j}(t,\mathbf {r})\). As \({\mathscr{B}}_j\) is deterministic and accepts every subtree of (t, r), it follows that \(r_{{\mathscr{B}}_j}(w) \in F_j\) for every w ∈pos(t). Thus, we can define a run \(r_j \in \text {Run}_{\mathcal {C}_j}(t)\) by \(r_j(w) = ({\mathbf {r}}(w), r_{{\mathscr{B}}_j}(w))\) and for this run we have \(\text {wt}_{\mathcal {C}_i}(t, r_j) = {\text {wt}}_j(t, {\mathbf {r}}) = \llbracket {\mathcal {A}}\rrbracket (t)\). Thus, we have \(\llbracket {\mathcal {C}_j}\rrbracket (t) \geq \text {wt}_{\mathcal {C}_j}(t,r_j) = \llbracket {\mathcal {A}}\rrbracket (t)\) and we have \(\llbracket {\mathcal {C}_i}\rrbracket (t) \leq \pi _i(\llbracket {{\boldsymbol {\mathcal {U}}}}\rrbracket (t)) \leq \llbracket {\mathcal {A}}\rrbracket (t)\) by construction for every i ∈{1,…,M}. Therefore, \(\max \limits _{i=1}^M \llbracket {\mathcal {C}_i}\rrbracket (t) = \llbracket {\mathcal {A}}\rrbracket (t)\). □

Finally, we show that the automata \(\mathcal {C}_1, \ldots , \mathcal {C}_M\) do not satisfy the tree fork property and therefore possess finitely sequential representations.

Lemma 17

The automata \(\mathcal {C}_1, \ldots , \mathcal {C}_M\) do not satisfy the tree fork property.

Proof

We prove the statement by contradiction and assume that for some i ∈{1,…,M}, the automaton \(\mathcal {C}_i\) satisfies the tree fork property. Then there exist rivals (p, b),(q, c) ∈Q × B_i which satisfy one of the conditions of the tree fork property together with a (p, b)-(q, c)-distinguisher \(s \in T_{{{\varGamma }}_{\diamond }}\). From the definition of \(\mathcal {C}_i\), it is easy to see that s is now also an i-p-q-distinguisher of \(\boldsymbol {\mathcal {U}}\). We let \(\mathbf {r}_{\mathbf {p}} \in \text {Run}^{\diamond }_{\boldsymbol {\mathcal {U}}}(\mathbf {p},s,\mathbf {p})\) and \({\mathbf {r}}_{{\mathbf {q}}} \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {q}},s,{\mathbf {q}})\). Then by Lemma 7, there exists an i-p-q-distinguisher \(s^{\prime } \in T_{{{\varGamma }}_{\diamond }}\) with \(\text {height}(s^{\prime }) \leq 4|{\mathbf {Q}}|^2\) and with runs \({\mathbf {r}}_{{\mathbf {p}}}^{\prime } \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {p}},s^{\prime },{\mathbf {p}})\) and \({\mathbf {r}}_{{\mathbf {q}}}^{\prime } \in \text {Run}^{{\diamond }}_{{\boldsymbol {\mathcal {U}}}}({\mathbf {q}},s^{\prime },{\mathbf {q}})\) such that and . We then also have and . Moreover, there exists a reacher u ∈ T_Γ with \(\text {Run}_{\mathcal {C}_i}(u,(\mathbf {p},b)) \neq \emptyset \) and \(\text {Run}_{\mathcal {C}_i}(u,(\mathbf {q},c)) \neq \emptyset \). We consider two cases.

If \(\mathcal {C}_i\) satisfies condition 1 of the tree fork property for (p, b) and (q, c), there exists a (p, b)-(q, c)-fork \(f \in T_{{{\varGamma }}_{\diamond }}\). Then f is also an i-p-q-fork in \(\boldsymbol {\mathcal {U}}\). We let t = s^N+ 1(f(s^N+ 1(u))), v_q = ε, w_q = u_q = ◊₁(s)^N+ 1, w_p = v_p = w_q◊₁(f), and u_p = v_p◊₁(s)^N+ 1. By assumption, the sets \(\text {Run}_{\mathcal {C}_i}(({\mathbf {p}},b),s,({\mathbf {p}},b))\), \(\text {Run}_{\mathcal {C}_i}(({\mathbf {q}},c),s,({\mathbf {q}},c))\), and \(\text {Run}_{\mathcal {C}_i}(({\mathbf {p}},b),f,({\mathbf {q}},c))\) are all non-empty, so there exists a unique run \(r_i \in \text {Run}_{\mathcal {C}_i}(t,({\mathbf {q}},c))\). We consider the run r = π_Q ∘ r_i, then we have \((s^{\prime }, \mathbf {r}_{\mathbf {q}}^{\prime })^{N+1}, r(w_{\mathbf {p}}) = \mathbf {p}, \mathbf {r}(w_{\mathbf {q}}) = \mathbf {q}\), and \(t \langle {\diamond } \to w_{{\mathbf {p}}} \rangle \!\!\upharpoonright _{w_{{\mathbf {q}}}}\) is a p-q-fork. Thus, (t, r) is \((i, {\mathbf {p}}, {\mathbf {q}}, s^{\prime })\)-broken and for the unique run \(r_{{\mathscr{B}}_i} \in \text {Run}_{{\mathscr{B}}_i}(t,{\mathbf {r}})\), we have \(r_{{\mathscr{B}}_i}(\varepsilon ) \notin F_i\). It follows that \(\pi _{B_i} \circ r_i(\varepsilon ) \notin F_i\) which implies that r_i is not valid in contradiction to our assumption.

If \(\mathcal {C}_i\) satisfies condition 1 of the tree fork property for (p, b) and(q, c), there exists a 2-Γ-context \(t^{\prime } \in T_{{{\varGamma }}_{\diamond }}\) and a run \(r_i^{\prime } \in \text {Run}_{\mathcal {C}_i}^{\diamond }(t^{\prime })\) with \(r_i^{\prime }(\Diamond _1(t^{\prime })) = (\mathbf {p}, b)\) and \(r_i^{\prime }(\Diamond _2(t^{\prime })) = (\mathbf {q}, c)\). We let \(t = t^{\prime }(s^{N+1}(u),s^{N+1}(u))\), \(v_{{\mathbf {p}}} = {\Diamond }_1(t^{\prime })\), \(v_{{\mathbf {q}}} = {\Diamond }_2(t^{\prime })\), u_p = v_p◊₁(s)^N+ 1, and u_q = v_q◊₁(s)^N+ 1. By our assumptions, there exists a unique run \(r_i \in \text {Run}_{\mathcal {C}_i}(t)\) with \(r_i(\varepsilon ) = r_i^{\prime }(\varepsilon )\). We consider the run r = π_Q ∘ r_i, then v_p and v_q are prefix-independent and we have and . As in the previous case, we see that (t, r) is \((i, {\mathbf {p}}, {\mathbf {q}}, s^{\prime })\)-broken and thus for the unique run \(r_{{\mathscr{B}}_i} \in \text {Run}_{{\mathscr{B}}_i}(t,\mathbf {r})\), we have \(r_{{\mathscr{B}}_i}(\varepsilon ) \notin F_i\). Therefore, \(\pi _{B_i} \circ r_i(\varepsilon ) \notin F_i\) which implies that r_i is not valid in contradiction to our assumption. □

To conclude, the proof of Theorem 2, we construct for every i ∈{1,…,M} deterministic max-plus-WTA \(\mathcal {A}_1^{(i)}, \ldots , \mathcal {A}_{n_i}^{(i)}\) with \(\max \limits _{j = 1}^{n_i} \llbracket {\mathcal {A}_j^{(i)}}\rrbracket = \llbracket {\mathcal {C}_i}\rrbracket \), which is possible by Theorem 1. Then \(\llbracket {\mathcal {A}}\rrbracket = \max \limits _{i=1}^M \llbracket {\mathcal {C}_i}\rrbracket = \max \limits _{i=1}^M \max \limits _{j = 1}^{n_i} \llbracket {\mathcal {A}_j^{(i)}}\rrbracket \), so \(\llbracket {\mathcal {A}}\rrbracket \) is finitely sequential.