Weighted automaton

The weighted automaton is a mathematical concept from theoretical computer science , especially from automaton theory . It is a generalization of the automaton . While the transitions of a (deterministic or nondeterministic) automaton are labeled with letters of the underlying alphabet, the transitions of a weighted automaton are also assigned a certain weight. For example, it can be interpreted as the effort that has to be made to get from one state to the other while a certain action is being carried out.

Mathematical definition

Be a half-ring , a non-empty set, and an alphabet . A Fünftupel is weighted with machine costs (weights) in the event that: , and . is then the transition function, are the entry weights and the exit weights. ${\displaystyle \mathbb {K} =(K,+,\cdot ,0,1)}$ ${\displaystyle Q}$ ${\displaystyle \Sigma }$ ${\displaystyle {\mathcal {A}}=(Q,\Sigma ,\delta ,\lambda ,\theta )}$ ${\displaystyle \mathbb {K} }$ ${\displaystyle \delta \colon Q\times \Sigma \times Q\rightarrow \mathbb {K} }$ ${\displaystyle \lambda \colon Q\rightarrow \mathbb {K} }$ ${\displaystyle \theta \colon Q\rightarrow \mathbb {K} }$ ${\displaystyle \delta }$ ${\displaystyle \lambda }$ ${\displaystyle \theta }$

A path in a weighted automaton is a sequence , where are states and letters. The labeling of this path is . The weight of such a path is . So the entry weight is multiplied by the weights of the transitions and the exit weight. To calculate the weight for a word , the automaton adds the weights of all paths with the label . The function calculated by an automaton is also called a formal power series. ${\displaystyle (q_{0},a_{1},q_{1},a_{2},...,a_{n},q_{n})\ }$ ${\displaystyle q_{0},...,q_{n}\in Q}$ ${\displaystyle a_{1},...,a_{n}\in \Sigma }$ ${\displaystyle a_{1}a_{2}...a_{n}\ }$ ${\displaystyle \lambda (q_{0})\cdot \left(\prod _{i=1,...,n}\delta (q_{i-1},a_{i},q_{i})\right)\cdot \theta (q_{n})}$ ${\displaystyle w=a_{1}a_{2}...a_{n}\in \Sigma ^{*}}$ ${\displaystyle w}$ ${\displaystyle |{\mathcal {A}}|\colon \Sigma ^{*}\rightarrow \mathbb {K} }$

Examples

A half-ring that is often considered in weighted automata is the tropical half-ring, where the neutral element with regard to the formation of the minimum and 0 is the neutral element with regard to the addition. For automata above this half-ring, the weight of a word is the minimum of the weights of all paths with the label . A very concrete example of a weighted machine over is ${\displaystyle \mathbb {T} =(R\cup \infty ,min,+,\infty ,0)}$ ${\displaystyle \infty }$ ${\displaystyle w}$ ${\displaystyle w}$ ${\displaystyle \mathbb {T} }$

for example the entry costs for 1. The transition costs from to are 2. for a and for b 2. Since in the tropical half-ring the first operation ("addition") is the formation of the minimum and the second operation is the addition, for a given word the weight just the minimum of all sums along paths labeled with this word. For the word aba, for example, the path is the only path with finite weight and thus the minimum path. So the cost of aba is exactly 10. ${\displaystyle q_{1}}$ ${\displaystyle q_{1}}$ ${\displaystyle q_{2}}$ ${\displaystyle \infty }$ ${\displaystyle q_{1},a,q_{1},b,q_{2},a,q_{2}\ }$

Another half ring is the Boolean half ring, with the two logical operations "and" and "or" and the neutral elements "0" (= false) with respect to "or" and "1" (= true) with respect to "and". Every finite automaton (not weighted) has exactly one corresponding Boolean automaton . The transitions from can be translated into transitions into which have the weight "1". All other transitions in then have the weight "0". In then exactly the paths that exist in have the weight "1" . Therefore, weighted automata are a more general concept than finite automata. ${\displaystyle \mathbb {B} =(\{0,1\},\vee ,\wedge ,0,1)}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$