Finite Ambiguity and Finite Sequentiality in Weighted Automata over Fields

Abstract

Infinite hierarchies of rational series realised by finitely ambiguous and finitely sequential weighted automata over fields, classifying them according to the ambiguity or sequentiality degree of realising automata, are examined. It is shown that both these hierarchies are strict if and only if the field under consideration is not locally finite; in that case, the hierarchies are strict already for series over a unary alphabet. Relations between finitely ambiguous and finitely sequential unary weighted automata are explored. It is also readily observed that polynomially ambiguous weighted automata over a field of characteristic zero are more powerful than finitely ambiguous weighted automata over the same field, again already over a unary alphabet. On the other hand, it is proved that unary alphabets are insufficient to separate the series realised by polynomially and finitely ambiguous weighted automata over algebraically closed fields of positive characteristic.

The work was supported by the grant VEGA 1/0601/20.

1 Introduction

Weighted automata of restricted ambiguity have recently attracted significant research attention. This was often motivated by the idea that certain problems undecidable – or not known to be decidable – for general weighted automata might admit reasonable decision algorithms when their scope is restricted to, e.g., finitely or polynomially ambiguous automata. Such questions have been studied for tropical automata in connection to their determinisation [14,15,16], as well as in the setting of probabilistic automata [4, 12]. Unary weighted automata of restricted ambiguity were also studied over the field of rational numbers [3], with motivation coming from the research dealing with decision problems for linear recurrences such as the Skolem problem. Moreover, classes of weighted automata with restricted ambiguity arise in connection with the weighted first-order logic of M. Droste and P. Gastin [8].

Various observations about the expressive power of weighted automata with restricted ambiguity have recently crystallised into its more systematic study. The so-called ambiguity hierarchy, composed by the classes of series realised by the unambiguous, finitely ambiguous, polynomially ambiguous, and unrestricted weighted automata, is observed to be strict over tropical semirings by A. Chattopadhyay et al. [6]. The same observation over the rational numbers is due to C. Barloy et al. [3] and is established already over unary alphabets; some of their results also follow, to some extent, from the findings of [8, 21]. Moreover, it is noted in [3] that the infinite hierarchy of series realised by k-ambiguous unary weighted automata over the rationals, for $k = 0,1,2,\ldots$, is strict.

Another restriction studied in the context of weighted finite automata is that of finite sequentiality [2] or multisequentiality [7]. Both terms have been used interchangeably, basically to describe deterministic weighted automata with possibly more than one initial state. A normal form of such automata, given by finite unions of deterministic automata, has been used as their definition as well. Every finitely sequential automaton is finitely ambiguous, but a finitely ambiguous automaton might not even admit a finitely sequential equivalent [2].

There has also been research on restricted ambiguity and finite sequentiality in weighted tree automata [20, 23,24,25,26].

The power of restricted ambiguity in weighted automata has thus mainly been examined over tropical semirings. On the contrary, its study for weighted automata over fields has so far been limited to the research dealing with the particular case of automata over the rationals. This is relatively surprising, as weighted automata over fields are particularly well explored and known for richness of their theory and abundance of appealing properties [5, 27]. The study of such automata has a long history going back to M.-P. Schützenberger [29]. To the author’s knowledge, finite sequentiality in weighted automata has been studied neither over fields in general, nor over any specific field such as the rationals.

The aim of this article is to explore some of the basic relations between classes of series realised by weighted automata with restricted ambiguity over general fields, in hope of later leading to a full understanding of ambiguity hierarchies over fields. In this respect, the article follows the same direction as the manuscript [17] examining relations between polynomially ambiguous and unrestricted weighted automata over fields. In particular, it is shown in [17] that unrestricted weighted automata over fields of characteristic zero that are not algebraically closed are more powerful than polynomially ambiguous weighted automata over the same field – already over unary alphabets. On the contrary, unary weighted automata over algebraically closed fields always admit polynomially ambiguous equivalents, regardless of the field’s characteristic.

The questions asked in this article are in a sense complementary to those considered in [17]. We mostly focus on finitely ambiguous weighted automata over fields – we study the hierarchy of series realised by k-ambiguous automata for $k = 0,1,2,\ldots$, as well as the relations between finitely ambiguous and polynomially ambiguous automata. In addition, we initiate the study of finitely sequential weighted automata over fields by examining the hierarchy of series realised by k-sequential automata for $k = 0,1,2,\ldots$, and observe some connections between finitely ambiguous and finitely sequential unary weighted automata.

In particular, we first observe that finitely ambiguous unary weighted automata over commutative semirings always admit finitely sequential equivalents, while the sequentiality degree of an equivalent automaton is linked to a structural measure of the original finitely ambiguous automaton. We next prove that the hierarchies of series realised by the k-ambiguous and k-sequential weighted automata over a field $\mathbb {F}$ for $k = 0,1,2,\ldots$ are strict whenever $\mathbb {F}$ is not locally finite; this also trivially is a necessary condition. Unary alphabets are sufficient to establish these results. Finally, we consider the relations between finitely and polynomially ambiguous weighted automata over fields. While it is essentially trivial to observe that already the unary polynomially ambiguous weighted automata over fields of characteristic zero are strictly more powerful than their finitely ambiguous counterparts, the case of a positive characteristic is far more interesting. We show that polynomially ambiguous unary weighted automata over algebraically closed fields of characteristic $p > 0$ always admit finitely ambiguous equivalents. Unary alphabets are thus insufficient to separate the series realised by finitely and polynomially ambiguous automata over such fields.

2 Preliminaries

Fields are understood to be commutative, and alphabets finite and nonempty. We denote by $\mathbb {N}$ the set of all nonnegative integers and write $[n] = \{1,\ldots ,n\}$ for each $n \in \mathbb {N}$. The set of all $m \times n$ matrices over a set S is denoted by $S^{m \times n}$, and the identity $n \times n$ matrix over any semiring by $\mathbf {I}_n$. A field (a semiring) is locally finite if its finitely generated subfields (subsemirings) are all finite. A field is locally finite if and only if it is locally finite as a semiring.

Consult, e.g., [5, 9, 10, 27, 28] for a reference on weighted automata and formal power series. We now briefly recall the most important concepts needed.

A (noncommutative) formal power series over a semiring S and alphabet $\varSigma$ is a mapping $r:\varSigma ^* \rightarrow S$ interpreted as follows: the value of r upon $w \in \varSigma ^*$ is denoted by (r, w) and called the coefficient of w in r; we then write

$$\begin{aligned} r = \sum _{w \in \varSigma ^*} (r,w)\,w. \end{aligned}$$

The set of all formal power series over S and $\varSigma$ is denoted by .

A weighted (finite) automaton over a semiring S and over an alphabet $\varSigma$ is a quadruple $\mathcal {A} = (Q,\sigma ,\iota ,\tau )$ with Q being a finite set of states, $\sigma :Q \times \varSigma \times Q \rightarrow S$ a transition weighting function, $\iota :Q \rightarrow S$ an initial weighting function, and $\tau :Q \rightarrow S$ a terminal weighting function.

A transition in the automaton $\mathcal {A}$ is a triple $(p,c,q) \in Q \times \varSigma \times Q$ such that $\sigma (p,c,q) \ne 0$. A run of $\mathcal {A}$ is a word $\gamma = q_0 c_1 q_1 c_2 q_2 \ldots q_{t-1} c_t q_t \in (Q\varSigma )^* Q$ with $q_0,\ldots ,q_t \in Q$ and $c_1,\ldots ,c_t \in \varSigma$ such that $(q_{k-1},c_k,q_k)$ is a transition for $k = 1,\ldots ,t$. We also say that $\gamma$ is a run on the word $c_1 \ldots c_t$ from $q_0$ to $q_t$. We say that $\gamma$ is successful if $\iota (q_0) \ne 0$ and $\tau (q_t) \ne 0$. The pure value of $\gamma$ is the element $\sigma (\gamma ) = \sigma (q_0,c_1,q_1)\sigma (q_1,c_2,q_2)\ldots \sigma (q_{t-1},c_t,q_t)$, and the complete value of $\gamma$ is given by $\overline{\sigma }(\gamma ) = \iota (q_0) \sigma (\gamma ) \tau (q_t)$. The length of $\gamma$ is given by $|\gamma |= t$. The set of all runs of $\mathcal {A}$ on w is denoted by $\mathcal {R}(\mathcal {A},w)$ and the set of all successful runs of $\mathcal {A}$ on w by $\mathcal {R}_s(\mathcal {A},w)$. We then also write

$$\begin{aligned} \mathcal {R}(\mathcal {A}) = \bigcup _{w \in \varSigma ^*} \mathcal {R}(\mathcal {A},w) \qquad \text { and } \qquad \mathcal {R}_s(\mathcal {A}) = \bigcup _{w \in \varSigma ^*} \mathcal {R}_s(\mathcal {A},w). \end{aligned}$$

The behaviour of a weighted automaton $\mathcal {A} = (Q,\sigma ,\iota ,\tau )$ over S and $\varSigma$ is a formal power series given by

$$\begin{aligned} \left( \Vert \mathcal {A}\Vert , w\right) = \sum _{\gamma \in \mathcal {R}_s(\mathcal {A},w)} \overline{\sigma }(\gamma ) = \sum _{\gamma \in \mathcal {R}(\mathcal {A},w)} \overline{\sigma }(\gamma ) \end{aligned}$$

for all $w \in \varSigma ^*$, both sums being obviously finite. We also say that the series $\Vert \mathcal {A}\Vert$ is realised by $\mathcal {A}$. A series is rational over S if it is realised by a weighted finite automaton over S and $\varSigma$.

A weighted automaton $\mathcal {A}$ over S and $\varSigma$ is said to be k-sequential for $k \in \mathbb {N}$ if there are at most k distinct states $q \in Q$ satisfying $\iota (q) \ne 0$, and if $\sigma (p,c,q) \ne 0$ with $\sigma (p,c,q') \ne 0$ imply $q = q'$ for all $p,q,q' \in Q$ and $c \in \varSigma$. In particular, 1-sequential automata are typically termed deterministic or sequential [19].¹ The automaton $\mathcal {A}$ is finitely sequential [2] if it is k-sequential for some $k \in \mathbb {N}$.²

The ambiguity degree of $\mathcal {A}$ is given by a function $\mathrm {amb}_{\mathcal {A}}:\varSigma ^* \rightarrow \mathbb {N}$ counting successful runs of $\mathcal {A}$ on words over $\varSigma$; that is, $\mathrm {amb}_{\mathcal {A}}(w) = |\mathcal {R}_s(\mathcal {A},w)|$ for all $w \in \varSigma ^*$. The automaton $\mathcal {A}$ is said to be k-ambiguous for $k \in \mathbb {N}$ if $\mathrm {amb}_{\mathcal {A}}(w) \le k$ for all $w \in \varSigma ^*$, while 1-ambiguous automata are called unambiguous. An automaton $\mathcal {A}$ is finitely ambiguous if it is k-ambiguous for some $k \in \mathbb {N}$ and polynomially ambiguous if there exists a polynomial function $p:\mathbb {N} \rightarrow \mathbb {N}$ such that $\mathrm {amb}_{\mathcal {A}}(w) \le p(|w|)$ for all $w \in \varSigma ^*$.

A weighted automaton $\mathcal {A} = (Q,\sigma ,\iota ,\tau )$ over S and $\varSigma$ is accessible if for each $q \in Q$, there exists a run of $\mathcal {A}$ from some p with $\iota (p) \ne 0$ to q; coaccessible if for each $p \in Q$, there exists a run of $\mathcal {A}$ from p to some q with $\tau (q) \ne 0$; and trim if it is both accessible and coaccessible.

In what follows, we often without loss of generality confine ourselves to automata with state sets [n] for $n \in \mathbb {N}$ – we then write $\mathcal {A} = (n,\sigma ,\iota ,\tau )$ instead of $\mathcal {A} = ([n],\sigma ,\iota ,\tau )$. Moreover, we apply the standard graph-theoretic terminology to weighted automata. This refers to a directed multigraph whose vertices are states of the automaton, while for each pair of states p, q, the transitions of the form (p, c, q) correspond bijectively to directed edges from p to q.

Weighted automata over a semiring S and alphabet $\varSigma$ can also be viewed as linear S-representations over $\varSigma$, i.e., quadruples $\mathcal {P} = (n,\mathbf {i},\mu ,\mathbf {f})$, where $n \in \mathbb {N}$, $\mathbf {i} \in S^{1 \times n}$ is a vector of initial weights, $\mu :(\varSigma ^*,\cdot ,\varepsilon ) \rightarrow (S^{n\times n},\cdot ,\mathbf {I}_n)$ is a monoid homomorphism, and $\mathbf {f} \in S^{n \times 1}$ is a vector of terminal weights. The series $\Vert \mathcal {P}\Vert$ realised by $\mathcal {P}$ is given by $\left( \Vert \mathcal {P}\Vert , w\right) = \mathbf {i}\mu (w)\mathbf {f}$ for all $w \in \varSigma ^*$. A series is recognisable over S if it is realised by a linear S-representation.

The classes of recognisable and rational series over words coincide by a well-known classical result [27]. In fact, every weighted automaton $\mathcal {A} = (n,\sigma ,\iota ,\tau )$ over S and $\varSigma$ corresponds to a linear S-representation $\mathcal {P}_{\mathcal {A}} = (n,\mathbf {i},\mu ,\mathbf {f})$, where $\mathbf {i} = (\iota (1),\ldots ,\iota (n))$, the matrix $\mu (c) = (c_{i,j})_{n \times n}$ is given by $c_{i,j} = \sigma (i,c,j)$ for every $c \in \varSigma$ and $i,j = 1,\ldots ,n$, and $\mathbf {f} = (\tau (1),\ldots ,\tau (n))^T$. Clearly $\Vert \mathcal {P}_{\mathcal {A}}\Vert = \Vert \mathcal {A}\Vert$.

Consider in addition a mapping $\nu :S \rightarrow \mathbb {N}$ given for all $a \in S$ by

$$\begin{aligned} \nu (a) = \left\{ \begin{array}{ll}1 &{} \text { if}\, a \ne 0, \\ 0 &{} \text { if}\, a = 0.\end{array}\right. \end{aligned}$$

(1)

Applying this mapping componentwise to vectors and matrices, it is clear that $\mathrm {amb}_{\mathcal {A}}(c_1\ldots c_t) = \nu (\mathbf {i})\nu (\mu (c_1))\ldots \nu (\mu (c_t))\nu (\mathbf {f})$ for all $t \in \mathbb {N}$ and $c_1,\ldots ,c_t \in \varSigma$.

We mostly work with linear representations over unary alphabets in what follows. We usually write a linear representation $\mathcal {P} = (n,\mathbf {i},\mu ,\mathbf {f})$ over $\varSigma = \{c\}$ as $\mathcal {P} = (n,\mathbf {i},A,\mathbf {f})$, where $A = \mu (c)$ is the only matrix needed to specify the homomorphism $\mu$. This means that given a weighted automaton $\mathcal {A}$ over a semiring S and unary alphabet $\varSigma = \{c\}$ with $\mathcal {P}_{\mathcal {A}} = (n,\mathbf {i},A,\mathbf {f})$,

$$\begin{aligned} \left( \Vert \mathcal {A}\Vert , c^t\right) = \mathbf {i} A^t \mathbf {f} \end{aligned}$$

holds for all $t \in \mathbb {N}$. The automaton $\mathcal {A}$ can thus also be interpreted as an initial value problem for the system of difference equations (i.e., recurrences)

$$\begin{aligned} \mathbf {x}_{t+1} = A\mathbf {x}_t \qquad \text { for all}\, t \in \mathbb {N}, \end{aligned}$$

the initial conditions being given by $\mathbf {x}_0 = \mathbf {f}$. When $S = \mathbb {F}$ is a field, the theory of difference equations [11] allows us to express the components of $\mathbf {x}_t$, and thus also $\left( \Vert \mathcal {A}\Vert , c^t\right)$, in closed form over the algebraic closure $\overline{\mathbb {F}}$ of $\mathbb {F}$. Indeed, by similarity of A to a matrix over $\overline{\mathbb {F}}$ in the Jordan canonical form, it follows that for all $t \in \mathbb {N}$,

$$\begin{aligned} \left( \Vert \mathcal {A}\Vert , c^t\right) = \sum _{\lambda \in \sigma }\sum _{j=0}^{\alpha (\lambda )-1}a_{\lambda ,j} {t \atopwithdelims ()j} \lambda ^{t - j}, \end{aligned}$$

(2)

where $\sigma$ denotes the spectrum of A over $\overline{\mathbb {F}}$, the algebraic multiplicity of each eigenvalue $\lambda$ of A is denoted by $\alpha (\lambda )$, and $a_{\lambda ,j} \in \overline{\mathbb {F}}$ are constants for $\lambda \in \sigma$ and $j = 0,\ldots ,\alpha (\lambda )-1$. Recall that the spectrum $\sigma$ contains precisely the roots over $\overline{\mathbb {F}}$ of the characteristic polynomial $\mathrm {ch}_A(x) = \det (x\mathbf {I}_n - A)$ of A, and that the algebraic multiplicity of $\lambda \in \sigma$ is its multiplicity as a root of $\mathrm {ch}_A(x)$.

The constants $a_{\lambda ,j}$ of (2) are always uniquely determined as a solution to a linear system of equations given by (2) for $t = 0,\ldots ,n-1$, in which they are the only unknowns. In particular, every choice of initial values on the left-hand sides uniquely determines the constants $a_{\lambda ,j}$ and conversely, every choice of the constants $a_{\lambda ,j}$ gives different initial values [11]. This observation can be established, e.g., as a consequence of the fact that the matrix of the above-mentioned linear system is the so-called Casorati matrix [11] of the functions ${t \atopwithdelims ()j} \lambda ^{t - j}$ for $\lambda \in \sigma$ and $j = 0,\ldots ,\alpha (\lambda )-1$. This is a generalised Vandermonde matrix [11, 13], so it is necessarily invertible. The linear system thus always has a unique solution. Moreover, any finite set of pairwise distinct functions of the form ${t \atopwithdelims ()j} \lambda ^{t - j}$ with $\lambda \in \overline{\mathbb {F}}$ and $j \in \mathbb {N}$ is linearly independent.

Similarly, consider a weighted automaton $\mathcal {A}$ over any semiring S and unary alphabet $\varSigma = \{c\}$, with $\mathcal {P}_{\mathcal {A}} = (n,\mathbf {i},A,\mathbf {f})$. Let $\nu :S \rightarrow \mathbb {N}$ be given by (1). Then

$$\begin{aligned} \mathrm {amb}_{\mathcal {A}}(c^t) = \nu (\mathbf {i}) \nu (A)^t \nu (\mathbf {f}) \end{aligned}$$

for all $t \in \mathbb {N}$, so that $\mathrm {amb}_{\mathcal {A}}(c^t)$ admits a closed form analogous to (2) over $\mathbb {C}$:

$$\begin{aligned} \mathrm {amb}_{\mathcal {A}}(c^t) = \sum _{\lambda \in \sigma '}\sum _{j=0}^{\alpha '(\lambda )-1}a'_{\lambda ,j} {t \atopwithdelims ()j} \lambda ^{t - j}, \end{aligned}$$

(3)

where $\sigma '$ denotes the spectrum of $\nu (A)$, the algebraic multiplicity of an eigenvalue $\lambda$ of $\nu (A)$ is denoted by $\alpha '(\lambda )$, and $a'_{\lambda ,j} \in \mathbb {C}$ for $\lambda \in \sigma '$ and $j = 0,\ldots ,\alpha '(\lambda )-1$. We call $\nu (A)$ the enumeration matrix of $\mathcal {A}$ in what follows.

3 Finite Ambiguity and Sequentiality in Unary Automata

We now make some preliminary remarks on finitely ambiguous and finitely sequential unary weighted automata. First, let us note that the ambiguity degree of a weighted automaton does not at all depend on its weights. This means that weights can be forgotten and the known criteria [30] for nondeterministic finite automata without weights can be applied in order to determine whether a given weighted automaton is, say, finitely or polynomially ambiguous.

Fig. 1.

The “forbidden configurations” for polynomially and finitely ambiguous trim finite automata, as identified by A. Weber and H. Seidl [30]. Distinct arrows represent distinct runs, as opposed to transitions.

Let us recall these criteria, as described by A. Weber and H. Seidl [30]. A trim finite automaton $\mathcal {A}$ with state set Q over an alphabet $\varSigma$ is polynomially ambiguous if and only if there does not exist a state q with at least two distinct runs from q to q upon some word $w \in \varSigma ^*$. Moreover, $\mathcal {A}$ is finitely ambiguous if and only if there is no pair of distinct states p, q such that for some $w \in \varSigma ^*$, there are runs upon w from p to p, from p to q, as well as from q to q. These “forbidden configurations” for polynomially and finitely ambiguous automata are schematically depicted in Fig. 1.

These criteria admit a particularly simple form for unary automata, which we now make explicit.

Theorem 1

Let S be a semiring and $\mathcal {A}$ a trim unary weighted automaton over S and $\varSigma = \{c\}$. The automaton $\mathcal {A}$ is:

• (i) Polynomially ambiguous if and only if its strongly connected components are all either single vertices, or directed cycles.

• (ii) Finitely ambiguous if and only if, in addition to (i), there is no run of $\mathcal {A}$ passing through two distinct directed cycles.

The characterisations of Theorem 1 can also be obtained, for a unary weighted automaton $\mathcal {A}$ with $\mathcal {P}_{\mathcal {A}} = (n,\mathbf {i},A,\mathbf {f})$, with a little help of the Perron-Frobenius theory [22] applied to the enumeration matrix $\nu (A)$. Indeed, the condition (i) is equivalent to all eigenvalues of $\nu (A)$ being of absolute value 0 or 1. If this is the case, (3) reduces to a polynomial function and $\mathcal {A}$ is polynomially ambiguous. Otherwise, the Perron-Frobenius theory gives us existence of an eigenvalue $\lambda > 1$ with at least one nonzero coefficient $a'_{\lambda ,j}$ in (3) – the automaton $\mathcal {A}$ is not polynomially ambiguous. Given (i), the equivalence of (ii) with finite ambiguity can be easily established by noting that a possibility of passing through two different cycles in a single run is equivalent to unboundedness of $\mathrm {amb}_{\mathcal {A}}$.

Given these characterisations of polynomially and finitely ambiguous trim unary weighted automata, the number of strongly connected components taking the form of cycles becomes a natural measure of their structural complexity.

Definition 2

Let S be a semiring, $\mathcal {A}$ a trim polynomially ambiguous unary weighted automaton over S and $\varSigma = \{c\}$, and $k \in \mathbb {N}$. We say that $\mathcal {A}$ is a k-cycle automaton if it contains at most k directed cycles.

It is easy to see that $\mathcal {A}$ as above is a k-cycle automaton if and only if the algebraic multiplicity of 1 as an eigenvalue of its enumeration matrix is at most k. We mostly apply this measure to finitely ambiguous automata in what follows; nevertheless, note that this measure is incomparable with the ambiguity degree in general.

We now note that every trim finitely ambiguous k-cycle automaton $\mathcal {A}$ over a unary alphabet decomposes, for $k \ge 1$, into k finitely ambiguous 1-cycle automata. The construction is intuitively obvious: for each of the cycles, we make use of the criterion (ii) of Theorem 1, and alter the original automaton $\mathcal {A}$ in order to obtain a 1-cycle automaton, whose successful runs are exactly the successful runs of $\mathcal {A}$ visiting at least one state on the cycle in question. Then we only need to take care of the runs of $\mathcal {A}$ that do not visit any cycle – but these can clearly be realised by a 0-cycle automaton, which may be “adjoined” to any of the k automata without spoiling their 1-cycle property.

Proposition 3

Let S be a semiring, $k \in \mathbb {N} \setminus \{0\}$, and $\mathcal {A}$ a trim finitely ambiguous k-cycle automaton over S and $\varSigma = \{c\}$. Then there are trim 1-cycle automata $\mathcal {A}_1,\ldots ,\mathcal {A}_k$ over S and $\varSigma$ such that , the values of successful runs of $\mathcal {A}_1,\ldots ,\mathcal {A}_k$ being the same as in the original automaton $\mathcal {A}$. This in particular implies that for all $t \in \mathbb {N}$,

$$\begin{aligned} \left( \Vert \mathcal {A}\Vert , c^t\right) = \sum _{j = 1}^k \left( \Vert \mathcal {A}_j\Vert , c^t\right) \end{aligned}$$

and

$$\begin{aligned} \mathrm {amb}_{\mathcal {A}}(c^t) = \sum _{j = 1}^k \mathrm {amb}_{\mathcal {A}_j}(c^t). \end{aligned}$$

Proof

Without loss of generality, assume that $\mathcal {A}$ contains precisely k cycles.³ Let $\mathcal {A} = (Q,\sigma ,\iota ,\tau )$ and let the k cycles of $\mathcal {A}$ correspond to state sets $C_1,\ldots ,C_k \subseteq Q$, respectively. Thus, denoting by $Q_0 \subseteq Q$ the set of states that do not belong to any cycle, we obtain . For $j = 1,\ldots ,k$, denote by $\mathcal {R}^{(j)}_s(\mathcal {A})$ the set of all successful runs of $\mathcal {A}$ visiting at least one state of $C_j$, i.e.,

$$\begin{aligned} \mathcal {R}^{(j)}_s(\mathcal {A}) = \{\gamma \in \mathcal {R}_s(\mathcal {A}) \mid Q(\gamma ) \cap C_j \ne \emptyset \}, \end{aligned}$$

where $Q(\gamma )$ is the set of states passed by $\gamma$, i.e., $Q(\gamma ) = \{q_0,\ldots ,q_t\}$ for each $\gamma = q_0 c q_1 c q_2 \ldots q_{t-1} c q_t \in \mathcal {R}(\mathcal {A})$ with $q_0,\ldots ,q_t \in Q$. For

$$\begin{aligned} \mathcal {R}^{(0)}_s(\mathcal {A}) = \{\gamma \in \mathcal {R}_s(\mathcal {A}) \mid Q(\gamma ) \cap C_j = \emptyset \text { for}\, j = 1,\ldots ,k\}, \end{aligned}$$

we clearly obtain .

For $j = 1,\ldots ,k$, we may also decompose Q as , where $Q_{\rightarrow }$ consists of all $q \in Q \setminus C_j$ from which there exists a run to a state in $C_j$, $Q_{\leftarrow }$ consists of all $q \in Q \setminus C_j$ to which there exists a run from some state in $C_j$, and $Q_{\times } = Q \setminus (Q_{\rightarrow } \cup C_j \cup Q_{\leftarrow })$. Denote by $Q'_0$ the set of all states $q \in Q_0$ such that $q \in Q(\gamma )$ for some run $\gamma \in \mathcal {R}^{(0)}_s(\mathcal {A})$. Let $Q_j = Q'_0 \cup Q_{\rightarrow } \cup C_j \cup Q_{\leftarrow }$ if $j = 1$ and $Q_j = Q_{\rightarrow } \cup C_j \cup Q_{\leftarrow }$ otherwise. Let $\mathcal {A}_j = (Q_j,\iota _j,\sigma _j,\tau _j)$ be a weighted automaton over S and $\varSigma = \{c\}$ such that for all $p,q \in Q_j$,

$$\begin{aligned} \iota _j(q)&= \left\{ \begin{array}{ll}\iota (q) &{} \text { if}\, q \in Q_{\rightarrow } \cup C_j \,\text {or}\, j = 1, \\ 0 &{} \text { otherwise,}\end{array}\right. \\ \sigma _j(p,c,q)&= \left\{ \begin{array}{ll}\sigma (p,c,q) &{} \text { if}\, p \not \in Q_{\rightarrow }, q \not \in Q_{\leftarrow }, \text {or} \, j = 1 \\ 0 &{} \text { otherwise,}\end{array}\right. \\ \tau _j(q)&= \left\{ \begin{array}{ll}\tau (q) &{} \text { if}\, q \in C_j \cup Q_{\leftarrow } \,\,\,\text {or}\, j = 1, \\ 0 &{} \text { otherwise.}\end{array}\right. \end{aligned}$$

Then $\mathcal {A}_j$ is clearly a trim 1-cycle automaton for $j = 1,\ldots ,k$. Moreover, obviously and $\mathcal {R}_s(\mathcal {A}_j) = \mathcal {R}^{(j)}_s(\mathcal {A})$ for $j = 2,\ldots ,k$, so that indeed , the values of these runs in $\mathcal {A}_1,\ldots ,\mathcal {A}_k$ being clearly the same as in $\mathcal {A}$.    $\square$

Let us now turn our attention to unary weighted automata over commutative semirings, for which we relate finite ambiguity with finite sequentiality.

Lemma 4

Let S be a commutative semiring, and $\mathcal {A}$ a trim finitely ambiguous 1-cycle automaton over S and unary alphabet $\varSigma = \{c\}$. Then there is a deterministic weighted automaton $\mathcal {B}$ over S and $\varSigma$ such that $\Vert \mathcal {B}\Vert = \Vert \mathcal {A}\Vert$.

Proof

The observation is trivial when $\mathcal {A}$ contains no cycle. We may thus assume that there is precisely one cycle in $\mathcal {A} = (Q,\sigma ,\iota ,\tau )$. Let $\ell \in \mathbb {N} \setminus \{0\}$ be its length, and $\gamma _{C} = q_1 c q_2 \ldots q_{\ell } c q_1$, for some $q_1,\ldots ,q_{\ell } \in Q$, a run of $\mathcal {A}$ on $c^{\ell }$ that goes around the cycle exactly once. Then there is $t_0 \in \mathbb {N}$ such that for all $t \ge t_0$, each run $\gamma$ of $\mathcal {A}$ upon $c^t$ visits $q_1$ and goes around the cycle from $q_1$ to $q_1$ at least $\lfloor (t-t_0)/\ell \rfloor$ times.⁴ Such $\gamma$ first follows some run $\gamma _1$ until it visits $q_1$ for the first time, then goes $\lfloor (t-t_0)/\ell \rfloor$ times around $\gamma _C$, and finally follows some run $\gamma _2$ from $q_1$ (the run $\gamma _2$ may revisit $q_1$). Setting $M = \sigma (\gamma _C)$, we get $\sigma (\gamma ) = \left( \sigma (\gamma _1)\sigma (\gamma _2)\right) M^{\lfloor (t-t_0)/\ell \rfloor }$.

Now, $|\gamma _1|+ |\gamma _2|= t - \ell \lfloor (t-t_0)/\ell \rfloor = t - ((t - t_0) - s) = t_0 + s$, where $s \in \{0,\ldots ,\ell -1\}$ is the remainder after dividing $t - t_0$ by $\ell$ – in other words, we have $t - t_0 \equiv s~(\mathrm {mod}~\ell )$. The set of all possible pairs $(\gamma _1,\gamma _2)$ is thus finite for all $s \in \{0,\ldots ,\ell -1\}$ and depends only on s. It thus follows that there are $b_0,\ldots ,b_{\ell - 1} \in S$ such that for $s = 0,\ldots ,\ell - 1$ and all $t \ge t_0$ with $t - t_0 \equiv s~(\mathrm {mod}~\ell )$,

$$\begin{aligned} \left( \Vert \mathcal {A}\Vert ,c^t\right) = b_s M^{\lfloor (t-t_0)/\ell \rfloor }. \end{aligned}$$

Moreover, for $t = 0,\ldots ,t_0 - 1$, denote by $a_t$ the value $(\Vert \mathcal {A}\Vert ,c^t)$.

Fig. 2.

The equivalent deterministic weighted automaton $\mathcal {B}$.

The automaton $\mathcal {A}$ is then obviously equivalent to the deterministic weighted automaton $\mathcal {B}$ over S and $\varSigma = \{c\}$ in Fig. 2.   $\square$

Theorem 5

Let S be a commutative semiring, $k \in \mathbb {N} \setminus \{0\}$, and $\mathcal {A}$ a trim finitely ambiguous k-cycle automaton over S and unary alphabet $\varSigma = \{c\}$. Then there is a k-sequential weighted automaton $\mathcal {B}$ over S and $\varSigma$ such that $\Vert \mathcal {B}\Vert = \Vert \mathcal {A}\Vert$.

Proof

Decompose $\mathcal {A}$ into trim finitely ambiguous 1-cycle automata $\mathcal {A}_1,\ldots ,\mathcal {A}_k$ as in Proposition 3, so that $\mathcal {A}_j$ has a deterministic equivalent $\mathcal {B}_j = (Q_j,\sigma _j,\iota _j,\tau _j)$ for $j = 1,\ldots ,k$ by Lemma 4. Then $\Vert \mathcal {A}\Vert = \Vert \mathcal {B}\Vert$ for $\mathcal {B}$ the union of $\mathcal {B}_1,\ldots ,\mathcal {B}_k$, i.e., a k-sequential automaton $\mathcal {B} = (Q,\sigma ,\iota ,\tau )$ with $Q = (Q_1 \times \{1\}) \cup \ldots \cup (Q_k \times \{k\})$, $\iota (q,j) = \iota _j(q)$, $\sigma ((p,j),c,(q,j)) = \sigma _j(p,c,q)$, and $\tau (q,j) = \tau _j(q)$ for all $p,q \in Q$, $j \in [k]$, and $c \in \varSigma$, while $\sigma (p,c,q) = 0$ for all other $(p,c,q) \in Q \times \varSigma \times Q$.    $\square$

Corollary 6

Every finitely ambiguous unary weighted automaton $\mathcal {A}$ over a commutative semiring S admits a finitely sequential equivalent (and vice versa).

4 Infinite Hierarchies

We now consider weighted automata over fields and first focus on the infinite hierarchies of formal power series realised, for $k = 0,1,2,\ldots$, by the k-ambiguous and k-sequential weighted automata. Our aim is to show that these hierarchies are strict if and only if the underlying field is not locally finite, while unary alphabets are sufficient to establish this observation. C. Barloy et al. [3] have noted that the finite ambiguity hierarchy over the rationals is strict, describing a counterexample witnessing this fact. We provide a similar counterexample that works over all other than locally finite fields and note that strictness of the finite sequentiality hierarchy is implied by this counterexample as well.

Lemma 7

Let $\mathbb {F}$ be a field that is not locally finite and $k \in \mathbb {N}$. Then there exists a series realised by a $(k+1)$-sequential weighted automaton over $\mathbb {F}$ and $\varSigma = \{c\}$, but by no k-ambiguous weighted automaton over $\mathbb {F}$.

Proof

As $\mathbb {F}$ is not locally finite, there necessarily exists some $\alpha \in \mathbb {F}$ of infinite multiplicative order, i.e., $\alpha \in \mathbb {F}$ such that $\alpha ^s = \alpha ^t$ for $s,t \in \mathbb {N}$ implies $s = t$. In fact, such $\alpha$ is known to exist in every other than locally finite commutative semiring [18, Lemma 7.2]; for fields, its existence also follows by containment of the rational numbers in fields of characteristic zero and by existence of elements transcendental over the Galois field $\mathbb {F}_p$ in other than locally finite fields of characteristic $p > 0$.

Consider a series given for all $t \in \mathbb {N}$ by

$$\begin{aligned} \left( r,c^t\right) = \alpha ^t + \alpha ^{2t} + \ldots + \alpha ^{(k+1)t}. \end{aligned}$$

(4)

Then r is clearly realised by a $(k+1)$-sequential weighted automaton.

Suppose for contradiction that r is realised by some k-ambiguous weighted automaton $\mathcal {A}$ over $\mathbb {F}$ and $\varSigma = \{c\}$. Without loss of generality, assume $\mathcal {A}$ is trim; moreover, let $\mathcal {P}_{\mathcal {A}} = (n,\mathbf {i},A,\mathbf {f})$. The spectrum of A then allows us to uniquely express $(r,c^t)$, as a function of $t \in \mathbb {N}$, in the form (2). It thus follows by (4), together with the linear independence of pairwise distinct functions ${t \atopwithdelims ()j}\lambda ^{t - j}$ with $\lambda \in \overline{\mathbb {F}}$ and $j \in \mathbb {N}$, that $\alpha ,\alpha ^2,\ldots ,\alpha ^{k+1}$ are eigenvalues of A.⁵

As $\mathcal {A}$ is finitely ambiguous, Theorem 1 tells us that its strongly connected components are all either directed cycles, or single vertices (without a loop). Nonzero eigenvalues of A are thus precisely the roots of characteristic polynomials of matrices corresponding to the directed cycles, each taking the form $x^{\ell } - b$ for some $\ell \in \mathbb {N} \setminus \{0\}$ and $b \in \mathbb {F} \setminus \{0\}$.

For each $a \in \overline{\mathbb {F}}$, let $\xi (a)$ be the set of all multiples of a by roots of unity in $\overline{\mathbb {F}}$, i.e., $\xi (a) = \left\{ \kappa a \mid \kappa \in \overline{\mathbb {F}};~\exists t \in \mathbb {N} \setminus \{0\}: \kappa ^t = 1\right\}$. The roots of each polynomial $x^{\ell } - b$ are then contained in $\xi (a)$ for any of its roots $a \in \overline{\mathbb {F}}$: indeed, if $a,a' \in \overline{\mathbb {F}}$ are roots of $x^{\ell } - b$, then they are both nonzero and

$$\begin{aligned} \left( \frac{a'}{a}\right) ^{\ell } = \frac{b}{b} = 1, \end{aligned}$$

so that

$$\begin{aligned} a' = \left( \frac{a'}{a}\right) a \in \xi (a). \end{aligned}$$

On the other hand, the sets $\xi (\alpha ),\xi (\alpha ^2),\ldots ,\xi (\alpha ^{k+1})$ are pairwise disjoint – if this was not a case, there would exist $x < y \in [k+1]$ such that $\kappa \alpha ^x = \nu \alpha ^y$ for some roots of unity $\kappa ,\nu \in \overline{\mathbb {F}}$; this would imply that $\alpha ^{y - x} = \kappa /\nu$ is a root of unity, contradicting the infinite multiplicative order of $\alpha$. In particular, none of the polynomials $x^{\ell } - b$ can have two distinct roots among $\alpha ,\alpha ^2,\ldots ,\alpha ^{k+1}$. It follows that $\mathcal {A}$ contains $K \ge k + 1$ cycles.

Decompose the K-cycle automaton $\mathcal {A}$ into 1-cycle automata $\mathcal {A}_1,\ldots ,\mathcal {A}_K$ as in Proposition 3. For $j = 1,\ldots ,K$, let $\mathcal {P}_{\mathcal {A}_j} = (n_j,\mathbf {i}_j,A_j,\mathbf {f}_j)$. Then, by what has been said, , where $J_d$ consists, for $d = 1,\ldots ,k+1$, of precisely all $j \in [K]$ such that the eigenvalues of $A_j$ are in $\xi (\alpha ^d) \cup \{0\}$, while they are not all zero; the nonzero eigenvalues of $A_j$ for $j \in J_0$ do not belong to any $\xi (\alpha ^d)$ with $d \in [k+1]$. It thus follows by uniqueness of the form (2) that there exists some $t_0 \in \mathbb {N}$ such that for all $t \ge t_0$,

$$\begin{aligned} \sum _{j \in J_d}\left( \Vert \mathcal {A}_j\Vert ,c^t\right) = \alpha ^{dt} \qquad \text {for}\, d = 1,\ldots ,k+1. \end{aligned}$$

As these values are always nonzero, we find out that the set $\bigcup _{j \in J_d}\mathcal {R}_s(\mathcal {A}_j,c^t)$ is nonempty for $d = 1,\ldots ,k+1$, the decomposition of Proposition 3 guaranteeing that . There are thus at least $k + 1$ successful runs of $\mathcal {A}$ on $c^t$, so $\mathcal {A}$ cannot be k-ambiguous: a contradiction.    $\square$

For $\mathbb {F}$ a field, $\varSigma$ an alphabet, and $k \in \mathbb {N}$, let $\mathrm {AMB}_k(\mathbb {F},\varSigma )$ and $\mathrm {SEQ}_k(\mathbb {F},\varSigma )$ denote, respectively, the sets of series realised by the k-ambiguous and k-sequential automata over $\mathbb {F}$ and $\varSigma$. The following theorem is obtained directly by Lemma 7.

Theorem 8

Let $\mathbb {F}$ be a field and $\varSigma$ an alphabet. If $\mathbb {F}$ is not locally finite, then $\mathrm {AMB}_k(\mathbb {F},\varSigma ) \subsetneq \mathrm {AMB}_{k+1}(\mathbb {F},\varSigma )$ and $\mathrm {SEQ}_k(\mathbb {F},\varSigma ) \subsetneq \mathrm {SEQ}_{k+1}(\mathbb {F},\varSigma )$ for all $k \in \mathbb {N}$.

As all weighted automata over locally finite semirings are determinisable [19], both hierarchies collapse over locally finite fields: $\mathrm {AMB}_k(\mathbb {F},\varSigma ) = \mathrm {AMB}_{k+1}(\mathbb {F},\varSigma )$ and $\mathrm {SEQ}_k(\mathbb {F},\varSigma ) = \mathrm {SEQ}_{k+1}(\mathbb {F},\varSigma )$ for $\mathbb {F}$ locally finite and $k \ge 1$.

5 Separation of Finite and Polynomial Ambiguity

We now examine the relations between finitely and polynomially ambiguous weighted automata over fields. C. Barloy et al. [3] have proved that polynomially ambiguous unary weighted automata over the rationals are more powerful than their finitely ambiguous counterparts. Let us first observe that their observation directly generalises to all fields of characteristic zero.

Theorem 9

Let $\mathbb {F}$ be a field of characteristic zero. Then there exists a series realised by a polynomially ambiguous weighted automaton over $\mathbb {F}$ and $\varSigma = \{c\}$, but by no finitely ambiguous weighted automaton over $\mathbb {F}$.

Proof

Let $(r,c^t) = t$ for all $t \in \mathbb {N}$. Then r is clearly realised by a polynomially ambiguous automaton. Suppose for contradiction that there is a finitely ambiguous automaton realising r. Then it can be decomposed into 1-cycle automata by Proposition 3. As $\mathbb {F}$ is of characteristic zero, all polynomials $x^{\ell } - b$ with $\ell \in \mathbb {N} \setminus \{0\}$ and $b \in \mathbb {F} \setminus \{0\}$ are separable. The nonzero eigenvalues of A are thus of algebraic multiplicity 1 for every 1-cycle automaton $\mathcal {A}$ with $\mathcal {P}_{\mathcal {A}} = (n,\mathbf {i},A,\mathbf {f})$. By uniqueness of the expression (2) for $(r,c^t)$, it follows that it cannot contain the term ${t \atopwithdelims ()1} 1^{t-1}$, so that $(r,c^t)$ cannot equal t for all $t \in \mathbb {N}$.    $\square$

The situation for fields of positive characteristic seems to be slightly different. We make just a single step towards its understanding, by showing that polynomially and finitely ambiguous automata over algebraically closed fields of positive characteristic are equally powerful when restricted to unary alphabets.

Theorem 10

Let $\mathbb {F}$ be an algebraically closed field of characteristic $p > 0$ and $\mathcal {A}$ a polynomially ambiguous unary weighted automaton over $\mathbb {F}$ and $\varSigma = \{c\}$. Then there is a finitely ambiguous weighted automaton $\mathcal {B}$ over $\mathbb {F}$ such that $\Vert \mathcal {B}\Vert = \Vert \mathcal {A}\Vert$.

Proof

Without loss of generality, let us assume that $\mathcal {A}$ with $\mathcal {P}_{\mathcal {A}} = (n,\mathbf {i},A,\mathbf {f})$ is trim. By Theorem 1, the strongly connected components of $\mathcal {A}$ are all directed cycles or single vertices, so that

$$\begin{aligned} \mathrm {ch}_A(x) = x^{\ell _0} \prod _{k = 1}^s \left( x^{\ell _k} - b_k\right) \end{aligned}$$

for some $\ell _0,s \in \mathbb {N}$, $\ell _1,\ldots ,\ell _s \in \mathbb {N} \setminus \{0\}$, and $b_1,\ldots ,b_s \in \mathbb {F} \setminus \{0\}$. For $k = 1,\ldots ,s$, let $\sigma _k \subseteq \mathbb {F}$ consist of all roots of $x^{\ell _k} - b_k$ that are not in .⁶ Let $\sigma _0 = \{0\}$ if 0 is a root of $\mathrm {ch}_A(x)$, and $\sigma _0 = \emptyset$ otherwise. Moreover, given a root $\lambda \in \mathbb {F}$ of $\mathrm {ch}_A(x)$, let $\alpha (\lambda )$ denote its multiplicity. Then (2) can be rewritten as

$$\begin{aligned} \left( \Vert \mathcal {A}\Vert , c^t\right) = \sum _{k = 0}^s \left( r_k, c^t\right) , \end{aligned}$$

(5)

where is given, for $k = 0,\ldots ,s$ and all $t \in \mathbb {N}$, by

$$\begin{aligned} \left( r_k, c^t\right) = \sum _{\lambda \in \sigma _k} \sum _{j = 0}^{\alpha (\lambda ) - 1} a_{\lambda ,j} {t \atopwithdelims ()j} \lambda ^{t - j} \end{aligned}$$

(6)

for some constants $a_{\lambda ,j} \in \mathbb {F}$ for $\lambda \in \sigma _k$ and $j = 0,\ldots ,\alpha (\lambda )-1$.

Now, the series $r_0$ can clearly be realised by a finitely ambiguous automaton. For $k = 1,\ldots ,s$, let $m \in \mathbb {N} \setminus \{0\}$ satisfy $p^m \ge \alpha (\lambda )$ for all $\lambda \in \sigma _k$. Let $M = \ell _k p^m$ and $B = b_k^{p^m}$, and let us consider a deterministic 1-cycle weighted automaton $\mathcal {A}_k = (M,\sigma ,\iota ,\tau )$ with $\sigma (t,c,t+1) = 1$ for $t = 1,\ldots ,M-1$, $\sigma (M,c,1) = B$, $\sigma (t,c,t') = 0$ for all remaining $(t,t') \in [M]^2$, $\iota (1) = 1$, $\iota (t) = 0$ for $t = 2,\ldots ,M$, and $\tau (t) = (r_k, c^{t-1})$ for $t = 1,\ldots ,M$. If $\mathcal {P}_{\mathcal {A}_k} = (M,\mathbf {i}_k,A_k,\mathbf {f}_k)$, then

$$\begin{aligned} \mathrm {ch}_{A_k}(x) = x^M - B = \left( x^{\ell _k}\right) ^{p^m} - b_k^{p^m} = \left( x^{\ell _k} - b_k\right) ^{p^m}, \end{aligned}$$

as $\mathbb {F}$ is of characteristic p. The eigenvalues of $A_k$ thus form a superset of $\sigma _k$ and the algebraic multiplicity of every eigenvalue $\lambda \in \sigma _k$ of $A_k$ is at least $\alpha (\lambda )$. The constants in the expression (2) for the series $(\Vert \mathcal {A}_k\Vert ,c^t)$ are uniquely determined by $(\Vert \mathcal {A}_k\Vert ,c^t) = (r_k, c^t)$ for $t = 0,\ldots ,M-1$. It follows that the expression (2) for $(\Vert \mathcal {A}_k\Vert ,c^t)$ is the same as in (6). In other words, $\Vert \mathcal {A}_k\Vert = r_k$.

Each of the series $r_k$ for $k = 0,\ldots ,s$ is thus realised by a finitely ambiguous automaton. Existence of $\mathcal {B}$ thus follows by (5).    $\square$

Note that the property that we have just established holds trivially – and regardless of the alphabet considered – for weighted automata over finite fields and their algebraic extensions, which are always locally finite. It would thus be interesting to know whether there exists a field of positive characteristic, over which the series realised by polynomially ambiguous and finitely ambiguous weighted automata can be separated, and how the answer to this question depends on the size of the alphabet.