Unambiguisability and Register Minimisation of Min-Plus Models

Weighted Finite Automata (WFAs) are a popular quantitative computational model, defining functions from words to values [11, 23, 9, 3]. The semantics of WFAs are typically defined over a semiring, with the most prominent settings being the field of rationals $(\mathbb{Q},+,\times )$, and the tropical semiring $(\mathbb{Z}\cup \{\mathrm{\infty }\},\min ,+)$. Both semirings yield WFAs that are useful for modelling certain aspects of systems, with a wide spectrum of applications (see [10, 11, 3] and references therein). For example, the rational field can be used to define probabilistic automata [22], whereas the tropical semiring allows reasoning about the optimal way of using resources (e.g., energy consumption), since the semantics is to take the minimal weighted run among all the runs on a word. Famously, tropical WFAs have been key to resolving the star-height conjecture [16, 13, 14, 19].

As with many computational models, reasoning about WFAs becomes harder in the presence of nondeterminism. For example, equivalence of tropical WFAs is undecidable for nondeterministic automata, but decidable for deterministic ones [18, 3]. Unlike Boolean automata, nondeterministic WFAs are strictly more expressive than their deterministic fragment for most semirings. Accordingly, a natural problem for WFAs is the determinisability problem: given a WFA $𝒜$, is there a deterministic WFA $𝒟$ such that $𝒜\equiv 𝒟$? This problem has a rich history dating back to the 1990s [20, 21] (see [2] for more details). It was recently shown to be decidable for the rational field [6, 15], and even more recently for the tropical semiring [2].

The “amount” of nondeterminism can be measured in various ways. The most prominent is ambiguity: a WFA is unambiguous if every word has at most one accepting run. We can similarly define $k$-ambiguous, finitely ambiguous and polynomially ambiguous [8]. Unambiguous WFAs are strictly more expressive than deterministic WFAs, but retain some nice closure and algorithmic properties [21]. As such, a natural question is unambiguisability¹¹1Equally fun mouthfuls include: “disambiguisability”, “unambiguousability”, etc.: given a WFA, is there an equivalent unambiguous WFA? For polynomially-ambiguous tropical automata, this problem was shown to be decidable in [17]. In addition, it is decidable over the rational field [6].

In this work, we resolve the decidability of this problem for tropical WFAs with unrestricted nondeterminism, by reducing it to the determinisability problem. Note that for most models, determinisability and unambiguisability have been resolved in tandem, by first deciding unambiguisability, and then deciding determinisability on the equivalent unambiguous, if it exists. Interestingly, for tropical WFAs determinisation is resolved directly, while unambiguisability remained open. It is somewhat surprising, therefore, that its solution is via reduction to determinisability.

Another measure of nondeterminism in WFAs stems from a closely related model – that of Cost Register Automata (CRAs) with linear register updates [5]. A cost register automaton has a deterministic control, equipped with several registers that hold values. At each step, the registers’ contents is manipulated according to some semiring actions (in our case, $(\min ,+)$). Over semirings, CRAs and WFAs are equally expressive [5]. A natural decision problem about CRAs is register minimisation: given a CRA with $k$ registers, is there an equivalent CRA with registers? We refine the results of [5] and show that the number of registers in a CRA corresponds to the width of a WFA: the maximal number of states that can be reached simultaneously (nondeterministically). This measure is incomparable with ambiguity as a measure for nondeterminism, but retains the flavour that width $1$ is exactly determinism. Using this equivalence, we show that register minimisation for CRAs is undecidable already for inputs with $7$ registers, and the construction extends to any larger fixed number of registers. We remark that for CRAs over the rational field, this problem is decidable [7].

For $k\in \mathbb{N}$ denote $[k]=\{1,\mathrm{\dots },k\}$. For an alphabet $\mathrm{\Sigma }$, we denote by ${\mathrm{\Sigma }}^{\ast }$ (resp. ${\mathrm{\Sigma }}^{+}$) the set of finite words (resp. non-empty finite words) over $\mathrm{\Sigma }$. For a word $w={\sigma }_1\mathrm{\cdots }{\sigma }_n\in {\mathrm{\Sigma }}^{\ast }$, we denote its length by $|w|=n$ and the set of its prefixes by $\mathrm{𝗉𝗋𝖾𝖿}(w)$. We write $w[i,j]={\sigma }_i\mathrm{\cdots }{\sigma }_j$ for the infix of $w$ corresponding to $1\le i\le j\le |w|$. For a letter $\sigma \in \mathrm{\Sigma }$ we denote by ${\mathrm{\#}}_{\sigma }(w)$ the number of occurrences of $\sigma$ in $w$.

We denote by ${\mathbb{N}}_{\mathrm{\infty }}$ and ${\mathbb{Z}}_{\mathrm{\infty }}$ the sets $\mathbb{N}\cup \{\mathrm{\infty }\}$ and $\mathbb{Z}\cup \{\mathrm{\infty }\}$, respectively. We extend the addition and $\min$ operations to $\mathrm{\infty }$ in the natural way: $a+\mathrm{\infty }=\mathrm{\infty }$ and $\min \{a,\mathrm{\infty }\}=a$ for all $a\in {\mathbb{Z}}_{\mathrm{\infty }}$. By $\arg \min \{f(x)\mid x\in A\}$ we mean the set of elements in $A$ for which $f(x)$ is minimal for some function $f$ and set $A$.

It is well-known that determinisability of WFA can be characterised by means of gaps [12, 2], namely by how far two potentially-minimal runs can get away from one another. We defer the discussion about this type of gaps to Section 4.1.

We now present an analogous characterisation for unambiguisability. To distinguish the terms, we dub this characterisation $𝔘$-type gaps (where $𝔘$ stands for “$𝔘$nambiguous”). Intuitively, we show that $𝒜$ is unambiguisable if and only if there is some bound $B\in \mathbb{N}$ such that any two accepting runs on a word $xy$ are no farther than $B$ apart after reading $x$, if the higher run can still become minimal after reading $y$. Conversely, $𝒜$ is not unambiguisable iff for every $B$ there exists a word $xy$ on which there exist two accepting runs that are farther than $B$ apart after reading $x$, and such that the higher run becomes minimal. We call $xy$ a witness to unambiguisability. Such a witness is depicted in Figure 3(a).

We say that a WFA $𝒜$ has $𝔘$-type gaps bounded by $B$ if there are no $𝔘$-type gap witnesses whose gap is greater than $B$; equivalently, there are no $𝔘$-type $(B+1)$-gap witnesses. For brevity, we refer to $𝔘$-type gaps simply as “gaps” throughout this section. In Section 4, we restore the $𝔘$-type notation as it is needed there.

The characterisation is as follows.

The detailed proof is given in the full version. We present the intuition here.

In this section we use our characterisation of unambiguisable WFAs to obtain our main contribution – a reduction from the unambiguisability problem to the determinisation problem. The latter was recently shown to be decidable in [2].

Tropical cost register automata (CRAs) with linear register updates provide an alternative representation of WFAs, where nondeterminism is captured in the behaviour of several registers, keeping the control deterministic. This view offers a natural measure of nondeterminism by the number of registers needed to capture a function. In this section we show that unfortunately, minimising the number of registers is generally undecidable already for inputs with $7$ registers, and therefore also for any larger fixed number of registers.

A fundamental result in [5] is that CRAs are expressively equivalent to WFAs. In the full version we formally define CRAs, and refine this result by showing that CRAs with $k$ registers are equivalent to WFAs in which, for every word, the maximal number of states simultaneously reachable is $k$. We refer to these as width-$k$ WFAs. Thus, our result is the following. The corresponding CRA statement and the full proof are in the full version, and we bring here only the core idea.

Consider a WFA $𝒜$ of width $6$, such that either $𝒜(w)\le 0$ for all $w$, or there is a word $w$ such that $\mathrm{𝗆𝗐𝗍}(q_0\stackrel{𝑤}{\to }{q}_0)=1$, so that⁵⁵5This actually requires further assumptions, see the detailed proof. the weight of $w^n$ is $n$. We want to separate the two cases using a reduction to the width-minimisation problem. We obtain from $𝒜$ a new WFA ${𝒜}^{\prime }$ as depicted in Figure 5. We add to the alphabet the letters $\{\$,\mathrm{①},\mathrm{\dots },\mathrm{⑥},a,\cancel{\mathrm{①}},\mathrm{\dots },\cancel{\mathrm{⑥}}\}$ and introduce new states $q_a,q_{\mathrm{①}},\mathrm{\dots },q_{\mathrm{⑥}}$. The behaviour is the following: we start both at $q_a$ and at $q_0$ (in $𝒜$). When $\$$ is read, runs from $q_0$ leave to all the $q_{\mathrm{ⓘ}}$. There, $q_{\mathrm{ⓘ}}$ loses $1$ on $\mathrm{ⓘ}$, and is not allowed to read $\cancel{\mathrm{ⓘ}}$. In addition component $q_a$ maintains weight $0$ but cannot read $a$.

The intuitive idea is the following. First, we claim that in any WFA equivalent to ${𝒜}^{\prime }$, the states $q_{\mathrm{ⓘ}}$ must be tracked separately, leading to width $6$ at least. This is because upon reading the word e.g., ${\mathrm{①}}^n{\mathrm{②}}^{2n}{\mathrm{③}}^{3n}{\mathrm{④}}^{4n}{\mathrm{⑤}}^{5n}{\mathrm{⑥}}^{6n}$ for large $n$, the gaps between the runs on the $q_{\mathrm{ⓘ}}$ states are very large. Then, we can use the “killing letters” $\cancel{\mathrm{ⓘ}}$ to eliminate all the runs but one, with a very short suffix (e.g., the suffix $\cancel{\mathrm{①}}\cancel{\mathrm{③}}\cancel{\mathrm{④}}\cancel{\mathrm{⑤}}\cancel{\mathrm{⑥}}$ leaves only the $q_{\mathrm{②}}$ run). For large enough $n$, a WFA of width 5 cannot track these values correctly.

Next, we look at the $q_a$ component. If $𝒜(w)\le 0$ for all $w$, the component $q_a$ is redundant, so we have an equivalent width-6 WFA. Otherwise, we claim that any equivalent WFA needs to track $q_a$ separately to all the $q_{\mathrm{ⓘ}}$. Here the reason is that using $w^n$ we can reach weight $n$ in the $𝒜$ component (so $q_a$ is far below it, with weight $0$), but upon reading $a$ the $q_a$ component is killed and the weight suddenly jumps to $n$, which again requires another component in any equivalent WFA. Thus, in this case any equivalent WFA must be of width at least $7$.

In order to turn this construction into a proper reduction we show that we can obtain such a WFA $𝒜$ for which the separation described above is undecidable. This uses the upper-boundedness construction of [3], which reduces the $0$-halting problem for two-counter machines to deciding whether the function described by a WFA is bounded from above. The detailed proof in the full version states the precise properties of that construction and then applies the gadget described here.

In a nutshell, our work maps out the borders of “nondeterminism minimisation” in WFAs, showing on the positive side that unambiguisability is decidable, and on the negative side that reducing the width (equivalently – minimising the number of registers in a CRA) is undecidable.

Note that our results hold for the closely related settings such as max-plus WFAs over ${\mathbb{Z}}_{\mathrm{\infty }}$ and min-plus or max-plus WFAs ${\mathbb{N}}_{\mathrm{\infty }}$. For max-plus over ${\mathbb{Z}}_{\mathrm{\infty }}$, the setting is completely symmetric – simply negate all the weights to obtain an analogous min-plus WFA. For ${\mathbb{N}}_{\mathrm{\infty }}$, note that adding a constant to all the transitions retains unambiguisability and determinisability (for both max-plus and min-plus). Therefore, we can start with a ${\mathbb{Z}}_{\mathrm{\infty }}$ WFA and increase the weights so that they are all in ${\mathbb{N}}_{\mathrm{\infty }}$, and the results stil hold. Note that “still holds” means that the general problem and the ${\mathbb{N}}_{\mathrm{\infty }}$ problem are computationally equivalent. The decidability already holds because this is a sub-case.

Our decidability proof of unambiguisability relies on the decidability of WFA determinisability. In particular, the current best known complexity bounds for determinisability are in the 6th level of the fast-growing hierarchy [1]. Since our reduction has a single-exponential blowup (and the fast-growing hierarchy is closed under single-exponential blowups) then the same complexity bounds hold for unambiguisability as well. For the lower bound, the best current bound is PSPACE-hardness, as per Theorem 10.

Two natural questions arise from our research. First, can we decide more relaxed ambiguity? E.g., can we decide if a given WFA has an equivalent 2-ambiguous/finitely ambiguous/polynomially-ambiguous WFA? The question of 2-ambiguisability seems very difficult, and currently out of reach. In particular, we do not know of a gap criterion that corresponds to 2-ambiguous WFAs. The second question is whether register minimisation becomes decidable for , which is perhaps of lesser importance, but it would nonetheless be nice to complete the picture.

In addition, now that some borders on decidability are in place, we can map out fragments, e.g., register minimisation for copyless CRAs [4].