Weighted automaton

The definition of a weighted automaton is generally given over an arbitrary semiring ${\displaystyle R}$, an abstract set with an addition operation ${\displaystyle \oplus }$ and a multiplication operation ${\displaystyle \otimes }$. The automaton consists of a finite set of states, a finite input alphabet of characters ${\displaystyle \mathrm{\Sigma }}$ and edges which are labeled with both a character in ${\displaystyle \mathrm{\Sigma }}$ and a weight in ${\displaystyle R}$. The weight of any path in the automaton is defined to be the product of weights along the path, and the weight of a string is the sum of the weights of all paths which are labeled with that string. The weighted automaton thus defines a function from ${\displaystyle {\mathrm{\Sigma }}^{\ast }}$ to ${\displaystyle R}$.

Weighted automata generalize deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs), which correspond to weighted automata over the Boolean semiring, where addition is logical disjunction and multiplication is logical conjunction. In the DFA case, there is only one accepting path for any input string, so disjunction is not applied. When the weights are real numbers and the outgoing weights for each state add to one, weighted automata can be considered a probabilistic model and are also known as probabilistic automata. These machines define a probability distribution over all strings, and are related to other probabilistic models such as Markov decision processes and Markov chains.

Weighted automata have applications in natural language processing where they are used to assign weights to words and sentences, as well as in image compression. They were first introduced by Marcel-Paul Schützenberger in his 1961 paper On the definition of a family of automata. Since their introduction, many extensions have been proposed, for example nested weighted automata, cost register automata, and weighted finite-state transducers. Researchers have studied weighted automata from the perspective of learning a machine from its input-output behavior (see computational learning theory) and studying decidability questions.

Definition

A commutative semiring (also known as a rig) is a set R equipped with two distinguished elements ${\displaystyle 0}$ and ${\displaystyle 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,\mathrm{\Sigma },\mathrm{\Delta },I,F)}$ where:

• ${\displaystyle Q}$ is a finite set of states.
• ${\displaystyle \mathrm{\Sigma }}$ is a finite alphabet.
• ${\displaystyle \mathrm{\Delta }\subseteq Q\times \mathrm{\Sigma }\times R\times Q}$ is a finite set of transitions ${\displaystyle (q,\sigma ,w,q^{\prime })}$, 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 {\mathrm{\Sigma }}^{\ast }}$ 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,\dots ,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 F(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}]]:{\mathrm{\Sigma }}^{\ast }\to R}$.