Other meanings of Weighted automaton
Computer Science
A weighted automaton is a formal automaton that assigns weights to transitions and accepting computations, generalizing classical finite automata by mapping each run to a value in a semiring rather than a Boolean acceptance. These weights can represent probabilities, costs, or other quantitative measures, enabling the modeling of systems where transitions have associated magnitudes. Weighted automata are used in natural language processing, speech recognition, and formal verification, and they underpin algorithms for shortest paths and algebraic power series.
A weighted automaton over a semiring K is a tuple (Q, Σ, I, F, δ) where Q is a finite set of states, Σ is an input alphabet, I and F are functions assigning initial and final weights, and δ: Q × Σ × Q → K assigns a weight to each transition. The weight of a path is the product of its transition weights, and the weight of a word is the sum over all accepting paths, using the semiring's multiplication and addition. This definition subsumes classical automata when K is the Boolean semiring, where weights are 0 or 1. Weighted automata can be deterministic or nondeterministic, and determinization is not always possible without increasing the state space. The behavior of a weighted automaton is a formal power series over Σ*, mapping each word to its weight.
Weighted automata are closed under union, concatenation, and Kleene star, mirroring regular language operations, provided the underlying semiring is complete. The equivalence problem for weighted automata is undecidable in general, but decidable for certain semirings such as the tropical semiring. Algorithms for composition, shortest path, and minimization have been developed, with the Floyd–Warshall algorithm adapted to compute the transitive closure of a weighted automaton. In the tropical semiring, where weights represent costs, the Viterbi algorithm finds the minimum-weight path, which is crucial in speech recognition. The determinization of weighted automata, when possible, may lead to an exponential blow-up, and the minimal deterministic weighted automaton is not always unique.
In natural language processing, weighted automata and transducers model pronunciation, morphology, and language models, where weights represent probabilities or log-likelihoods. Speech recognition systems use weighted finite-state transducers to integrate acoustic and language models efficiently. In formal verification, weighted automata model resource consumption, such as energy or time, and are used in model checking of quantitative properties. They also appear in image processing for morphological operators and in bioinformatics for sequence alignment, where edit distances are computed via weighted automata. The theory of weighted automata connects to formal power series and rational series, with applications in algebraic coding theory.
Weighted automata were independently introduced by Schützenberger in 1961 and by Chomsky and Schützenberger in 1963, building on earlier work on probabilistic automata by Rabin. A lesser-known variant is the weighted visibly pushdown automaton, which handles nested structures with weights, used in program analysis. The concept of weighted automata over the max-plus semiring is central to timed automata and scheduling problems. In quantum computing, weighted automata over the field of complex numbers model quantum finite automata, where amplitudes replace probabilities. The minimization problem for weighted automata is closely related to the theory of Hankel matrices, and the rank of the Hankel matrix determines the minimal number of states. Weighted automata also generalize to weighted tree automata, which operate on trees rather than strings, with applications in natural language parsing and XML processing.
Weighted automata form a rich theoretical framework with deep connections to algebra, logic, and optimization.
Help improve the encyclopedia. Reports go straight to the site manager.