Weighted automaton

A commutative semiring (or rig) is a set R equipped with two distinguished elements ${\displaystyle 0\neq 1}$ and addition and multiplication operations ${\displaystyle \oplus }$ and ${\displaystyle \otimes }$ such that ${\displaystyle \oplus }$ is commutative and associative with identity ${\displaystyle 0}$, ${\displaystyle \otimes }$ is commutative and associative with identity ${\displaystyle 1}$, ${\displaystyle \otimes }$ distributes over ${\displaystyle \oplus }$, and 0 is an absorbing element for ${\displaystyle \otimes }$.

A weighted automaton over ${\displaystyle R}$ is a tuple ${\displaystyle {\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)}$ where:

• ${\displaystyle Q}$ is a finite set of states.
• ${\displaystyle \Sigma }$ is a finite alphabet.
• ${\displaystyle \Delta \subseteq Q\times \Sigma \times R\times Q}$ is a finite set of transitions ${\displaystyle (q,\sigma ,w,q')}$, where ${\displaystyle \sigma }$ is called a character and ${\displaystyle w}$ is called a weight.
• ${\displaystyle I:Q\to R}$ is an initial weight function.
• ${\displaystyle F:Q\to R}$ is a final weight function.

A path on input ${\displaystyle w\in \Sigma ^{*}}$ is a finite path in the graph, where the concatenation of the character labels equals ${\displaystyle w}$. The weight of the path ${\displaystyle q_{0},q_{1},\ldots ,q_{n}}$ is the product (${\displaystyle \otimes }$) of the weights along the path, additionally multiplied by the initial and final weights ${\displaystyle I(q_{0})\otimes I(q_{n})}$. The weight of the word ${\displaystyle w}$ is the sum (${\displaystyle \oplus }$) of the weights of all paths on input ${\displaystyle w}$ (or 0 if there are no accepting paths). In this way the machine defines a function ${\displaystyle [\![{\mathcal {A}}]\!]:\Sigma ^{*}\to R}$.

The underlying NFA of ${\displaystyle {\mathcal {A}}}$ is an NFA formed by removing all transitions with weight ${\displaystyle 0}$ and then erasing all of the weights on the transitions ${\displaystyle \Delta }$, so that the new transition set lies in ${\displaystyle Q\times \Sigma \times Q}$. The initial states and final states are the set of states ${\displaystyle q}$ such that ${\displaystyle I(q)\neq 0}$ and ${\displaystyle F(q)\neq 0}$, respectively.

• A weighted automaton is deterministic if the underlying NFA is deterministic and unambiguous if the underlying NFA is unambiguous. In these cases, there is always exactly one accepting path, so the ${\displaystyle \oplus }$ operation is never applied and can be omitted from the definition.

• It is possible to extend the definition to allow epsilon transitions ${\displaystyle (q,\epsilon ,w,q')}$, where ${\displaystyle \epsilon }$ is the empty string. In this case, one must then require that there are no cycles of epsilon transitions. This does not increase the expressiveness of weighted automata.[2][10] If epsilon transitions are allowed, the initial weights and final weights can be replaced by initial and final sets of states without loss of expressiveness.

• The transition function can be given as a matrix ${\displaystyle \Delta _{\sigma }\in R^{Q\times Q}}$ with entries in ${\displaystyle R}$ for each ${\displaystyle \sigma }$, rather than a set of transitions. The entry of the matrix at ${\displaystyle (q,q')}$ is the sum of all transitions labeled ${\displaystyle (q,\sigma ,q')}$.[2][11]

• Some authors omit the initial and final weight functions ${\displaystyle I}$ and ${\displaystyle F}$.[1] Instead, ${\displaystyle I}$ and ${\displaystyle F}$ are replaced by a set of initial and final states. If epsilon transitions are not present, this technically decreases expressiveness as it forces ${\displaystyle [\![{\mathcal {A}}]\!](\varepsilon )}$ to depend only on the number of states that are both initial and final.

• Some authors restrict to specific semirings, such as ${\displaystyle \mathbb {N} }$ or ${\displaystyle \mathbb {Z} }$, particularly when studying decidability results.[1][9][4]

• The requirement that there is a zero element for ${\displaystyle \oplus }$ is sometimes omitted; in this case the machine defines a partial function from ${\displaystyle \Sigma ^{*}}$ to ${\displaystyle R}$ rather than a total function.