computational learning theory) and studying decidability questions. Definition A commutative semiring (or rig) is a set R equipped with two distinguished elements and addition and multiplication operations and such that is commutative and associative with identity , is commutative and associative with identity , distributes over , and 0 is an absorbing element for . A weighted automaton over is a tuple where: is a finite set of states. is a finite alphabet. is a finite set of transitions , where is called a character and is called a weight. is an initial weight function. is a final weight function. A path on input is a finite path in the graph, where the concatenation of the character labels equals . The weight of the path is the product () of the weights along the path, additionally multiplied by the initial and final weights . The weight of the word is the sum () of the weights of all paths on input (or 0 if there are no accepting paths). In this way the machine defines a function . The underlying NFA of is an NFA formed by removing all transitions with weight and then erasing all of the weights on the transitions , so that the new transition set lies in . The initial states and final states are the set of states such that and , respectively. Variations 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 operation is never applied and can be omitted from the definition. It is possible to extend the definition to allow epsilon transitions , where 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. 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 with entries in for each , rather than a set of transitions. The entry of the matrix at is the sum of all transitions labeled . Some authors omit the initial and final weight functions and . Instead, and are replaced by a set of initial and final states. If epsilon transitions are not