# Weighted automaton

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Weighted_automaton
> Markdown URL: https://mediated.wiki/source/Weighted_automaton.md
> Source: https://en.wikipedia.org/wiki/Weighted_automaton
> Source revision: 1292383419
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Finite-state machine where edges carry weights}}

[[File:Quantitative automata.svg|thumb|300px|right|[Hasse diagram](/source/Hasse_diagram) of some classes of quantitative automata, ordered by expressiveness.<ref name=QuantitativeAutomata>{{Cite book|last1=Chatterjee|first1=Krishnendu|last2=Henzinger|first2=Thomas A.|last3=Otop|first3=Jan|title=Static Analysis |chapter=Quantitative Monitor Automata |date=2016|editor-last=Rival|editor-first=Xavier|chapter-url=https://link.springer.com/chapter/10.1007%2F978-3-662-53413-7_2|series=Lecture Notes in Computer Science|volume=9837 |language=en|location=Berlin, Heidelberg|publisher=Springer|pages=23–38|doi=10.1007/978-3-662-53413-7_2|isbn=978-3-662-53413-7}}</ref>{{rp|at=Fig.1}}]]

In [theoretical computer science](/source/theoretical_computer_science) and [formal language theory](/source/formal_language), a '''weighted automaton''' or '''weighted finite-state machine''' is a generalization of a [finite-state machine](/source/finite-state_machine) in which the edges have [weights](/source/Glossary_of_graph_theory), for example [real number](/source/real_number)s or [integer](/source/integer)s. Finite-state machines are only capable of answering [decision problem](/source/decision_problem)s; they take as input a [string](/source/string_(computer_science)) and produce a [Boolean](/source/Boolean_data_type) output, i.e. either "accept" or "reject". In contrast, weighted automata produce a [quantitative](/source/Quantification_(science)) output, for example a count of ''how many'' answers are possible on a given input string, or a [probability](/source/probability) of ''how likely'' the input string is according to a [probability distribution](/source/probability_distribution).<ref name=Handbook>{{Cite book|date=2009|editor-last=Droste|editor-first=Manfred|editor2-last=Kuich|editor2-first=Werner|editor3-last=Vogler|editor3-first=Heiko|title=Handbook of Weighted Automata|url=https://link.springer.com/book/10.1007/978-3-642-01492-5|series=Monographs in Theoretical Computer Science. An EATCS Series |language=en-gb|doi=10.1007/978-3-642-01492-5|bibcode=2009hwa..book.....D |isbn=978-3-642-01491-8 |issn=1431-2654}} chs.1-4, pp. 3–26, 69–71, 122–126.</ref> They are one of the simplest studied models of '''quantitative automata.'''<ref name=QuantitativeAutomata/>{{rp|at=Fig.1}}

The definition of a weighted automaton is generally given over an arbitrary [semiring](/source/semiring) <math>R</math>, an [abstract](/source/abstract_algebra) set with an addition operation <math>+</math> and a multiplication operation <math>\times</math>. The automaton consists of a finite set of states, a finite input alphabet of [characters](/source/Character_(computing)) <math>\Sigma</math> and edges which are labeled with both a character in <math>\Sigma</math> and a weight in <math>R</math>. The weight of any [path](/source/path_(graph_theory)) 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](/source/function_(mathematics)) from <math>\Sigma^*</math> to <math>R</math>.<ref name=Handbook/>

Weighted automata [generalize](/source/Generalization) [deterministic finite automata](/source/Deterministic_finite_automaton) (DFAs) and [nondeterministic finite automata](/source/Nondeterministic_finite_automaton) (NFAs), which correspond to weighted automata over the [Boolean semiring](/source/Semiring), where addition is [logical disjunction](/source/logical_disjunction) and multiplication is [logical conjunction](/source/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](/source/Statistical_model) and are also known as [probabilistic automata](/source/probabilistic_automaton). These machines define a probability distribution over all strings, and are related to other probabilistic models such as [Markov decision processes](/source/Markov_decision_process) and [Markov chain](/source/Markov_chain)s.

Weighted automata have applications in [natural language processing](/source/natural_language_processing) where they are used to assign weights to words and sentences,<ref>{{Cite web|last=Chiang|first=David|title=Weighted Automata|url=https://www3.nd.edu/~dchiang/teaching/nlp/2019/notes/chapter4v3.pdf|access-date=2021-11-09|website=Natural Language Processing (CSE 40657/60657), course notes, Fall 2019}}</ref><ref name=Handbook/>{{rp|pages=571-596}} as well as in [image compression](/source/image_compression).<ref name=Handbook/>{{rp|pages=453-480}} They were first introduced by [Marcel-Paul Schützenberger](/source/Marcel-Paul_Sch%C3%BCtzenberger) in his 1961 paper ''On the definition of a family of automata.''<ref name=Introduced>{{Cite journal|last=Schützenberger|first=M. P.|date=1961-09-01|title=On the definition of a family of automata|journal=Information and Control|language=en|volume=4|issue=2|pages=245–270|doi=10.1016/S0019-9958(61)80020-X|issn=0019-9958|doi-access=}}</ref> Since their introduction, many extensions have been proposed, for example nested weighted automata,<ref name=NWA>{{Cite journal|last1=Chatterjee|first1=Krishnendu|last2=Henzinger|first2=Thomas A.|last3=Otop|first3=Jan|date=2017-12-14|title=Nested Weighted Automata|url=https://doi.org/10.1145/3152769|journal=ACM Transactions on Computational Logic|volume=18|issue=4|pages=31:1–31:44|doi=10.1145/3152769|arxiv=1504.06117 |s2cid=15070803 |issn=1529-3785}}</ref> cost register automata,<ref name=CRA>{{Cite book |last1=Alur |first1=Rajeev |last2=D'Antoni |first2=Loris |last3=Deshmukh |first3=Jyotirmoy |last4=Raghothaman |first4=Mukund |last5=Yuan |first5=Yifei |title=2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science |chapter=Regular Functions and Cost Register Automata |date=2013 |chapter-url=https://ieeexplore.ieee.org/document/6571532 |pages=13–22 |doi=10.1109/LICS.2013.65|isbn=978-1-4799-0413-6 |s2cid=1286659 |url=https://repository.upenn.edu/cis_papers/568 }}</ref> and [weighted finite-state transducers](/source/Finite-state_transducer).<ref name=WFST>{{Cite journal|last1=Mohri|first1=Mehryar|last2=Pereira|first2=Fernando|last3=Riley|first3=Michael|date=2002-01-01|title=Weighted finite-state transducers in speech recognition|url=https://repository.upenn.edu/bitstreams/0473dbb0-8787-4c32-97f6-0d3f6edaffed/download|journal=Computer Speech & Language|language=en|volume=16|issue=1|pages=69–88|doi=10.1006/csla.2001.0184|issn=0885-2308}}</ref> Researchers have studied weighted automata from the perspective of [learning](/source/machine_learning) a machine from its input-output behavior<ref>{{Cite book|last1=Balle|first1=Borja|last2=Mohri|first2=Mehryar|title=Algebraic Informatics |chapter=Learning Weighted Automata |date=2015|editor-last=Maletti|editor-first=Andreas|chapter-url=https://link.springer.com/chapter/10.1007/978-3-319-23021-4_1|series=Lecture Notes in Computer Science|volume=9270 |language=en|location=Cham|publisher=Springer International Publishing|pages=1–21|doi=10.1007/978-3-319-23021-4_1|isbn=978-3-319-23021-4}}</ref> (see [computational learning theory](/source/computational_learning_theory)) and studying [decidability](/source/Decision_problem) questions.<ref name=Decidability>{{Cite book|last1=Almagor|first1=Shaull|last2=Boker|first2=Udi|last3=Kupferman|first3=Orna|title=Automated Technology for Verification and Analysis |chapter=What's Decidable about Weighted Automata? |date=2011|editor-last=Bultan|editor-first=Tevfik|editor2-last=Hsiung|editor2-first=Pao-Ann|chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-24372-1_37|series=Lecture Notes in Computer Science|volume=6996 |language=en|location=Berlin, Heidelberg|publisher=Springer|pages=482–491|doi=10.1007/978-3-642-24372-1_37|isbn=978-3-642-24372-1|s2cid=10159261 }}</ref>

{{clear|right}}

== Definition ==

A [commutative semiring](/source/Semiring) (or '''rig''') is a set ''R'' equipped with two distinguished elements <math>0 \ne 1</math> and addition and multiplication operations <math>\oplus</math> and <math>\otimes</math> such that <math>\oplus</math> is [commutative](/source/Commutative_property) and [associative](/source/Associative_property) with [identity](/source/Identity_element) <math>0</math>, <math>\otimes</math> is commutative and associative with identity <math>1</math>, <math>\otimes</math> [distributes](/source/Distributive_property) over <math>\oplus</math>, and 0 is an [absorbing element](/source/absorbing_element) for <math>\otimes</math>.

A '''weighted automaton over <math>R</math>''' is a tuple <math>\mathcal{A} = (Q, \Sigma, \Delta, I, F)</math> where:
* <math>Q</math> is a finite set of states.
* <math>\Sigma</math> is a finite alphabet.
* <math>\Delta \subseteq Q \times \Sigma \times R \times Q</math> is a finite set of transitions <math>(q, \sigma, w, q')</math>, where <math>\sigma</math> is called a '''character''' and <math>w</math> is called a '''weight'''.
* <math>I: Q \to R</math> is an initial weight function.
* <math>F: Q \to R</math> is a final weight function.

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

== Ambiguity and determinism ==

Since <math>\Delta</math> is a ''set'' of transitions, weighted automata allow multiple transitions (or paths) on a single input string.
Therefore a weighted automaton can be considered analogous to a [nondeterministic finite automaton](/source/nondeterministic_finite_automaton) (NFA).
As is the case with NFAs, restrictions of weighted automata are considered that correspond to the concepts of [deterministic finite automaton](/source/deterministic_finite_automaton) and [unambiguous finite automaton](/source/unambiguous_finite_automaton) (deterministic weighted automata and unambiguous weighted automata, respectively).

First, a preliminary definition: the '''underlying NFA''' of <math>\mathcal{A}</math> is an NFA formed by removing all transitions with weight <math>0</math> and then erasing all of the weights on the transitions <math>\Delta</math>, so that the new transition set lies in <math>Q \times \Sigma \times Q</math>. The initial states and final states are the set of states <math>q</math> such that <math>I(q) \ne 0</math> and <math>F(q) \ne 0</math>, respectively.

A weighted automaton is '''deterministic''' if the underlying NFA is deterministic and '''unambiguous''' if the underlying NFA is unambiguous.
Every deterministic weighted automaton is unambiguous.

In both the deterministic and unambiguous cases, there is always at most one accepting path, so the <math>\oplus</math> operation is never applied and can be omitted from the definition.

== Variations ==

* The requirement that there is a zero element for <math>\oplus</math> is sometimes omitted; in this case the machine defines a [partial function](/source/partial_function) from <math>\Sigma^*</math> to <math>R</math> rather than a total function.

* It is possible to extend the definition to allow [epsilon transitions](/source/epsilon_transition_(disambiguation)) <math>(q, \epsilon, w, q')</math>, where <math>\epsilon</math> is the empty string. In this case, one must then require that there are no [cycles](/source/Cycle_(graph_theory)) of epsilon transitions. This does not increase the expressiveness of weighted automata.<ref name=Handbook/><ref>{{Citation|last=Mohri|first=Mehryar|title=Weighted Automata Algorithms|date=2009|url=https://doi.org/10.1007/978-3-642-01492-5_6|work=Handbook of Weighted Automata|pages=213–254|editor-last=Droste|editor-first=Manfred|series=Monographs in Theoretical Computer Science. An EATCS Series|place=Berlin, Heidelberg|publisher=Springer|language=en|doi=10.1007/978-3-642-01492-5_6|bibcode=2009hwa..book..213M |isbn=978-3-642-01492-5|access-date=2021-11-11|editor2-last=Kuich|editor2-first=Werner|editor3-last=Vogler|editor3-first=Heiko|url-access=subscription}}</ref> 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.

* Some authors omit the initial and final weight functions <math>I</math> and <math>F</math>.<ref name=QuantitativeAutomata/> Instead, <math>I</math> and <math>F</math> are replaced by a set of initial and final states. If epsilon transitions are not present, this technically decreases expressiveness as it forces <math>[\![ \mathcal{A} ]\!](\varepsilon)</math> to depend only on the number of states that are both initial and final.

* The transition function can be given as a [matrix](/source/matrix_ring) <math>\Delta_\sigma \in R^{Q \times Q}</math> with entries in <math>R</math> for each <math>\sigma</math>, rather than a set of transitions. The entry of the matrix at <math>(q, q')</math> is the sum of all transitions labeled <math>(q, \sigma, q')</math>.<ref name=Handbook/><ref>{{Cite journal|last1=Droste|first1=Manfred|last2=Gastin|first2=Paul|date=2007-06-21|title=Weighted automata and weighted logics|journal=Theoretical Computer Science|series=Automata, Languages and Programming|language=en|volume=380|issue=1|pages=69–86|doi=10.1016/j.tcs.2007.02.055|issn=0304-3975|doi-access=free}}</ref>

* Some authors restrict to specific semirings, such as <math>\mathbb{N}</math> or <math>\mathbb{Z}</math>, particularly when studying decidability results.<ref name=QuantitativeAutomata/><ref name=Decidability/><ref name=Introduced/>

== See also ==

{{columns-list|colwidth=20em|
* [Probabilistic automaton](/source/Probabilistic_automaton)
* [Nondeterministic finite automaton](/source/Nondeterministic_finite_automaton)
* [Finite-state transducer](/source/Finite-state_transducer)
* [Rational series](/source/Rational_series)
* [Semiring](/source/Semiring)
* [Matrix ring](/source/Matrix_ring)
* [Timed automaton](/source/Timed_automaton)
* [Fuzzy logic](/source/Fuzzy_logic)
* [Markov chain](/source/Markov_chain)
}}

== References ==

{{reflist}}

Category:Finite-state machines

---
Adapted from the Wikipedia article [Weighted automaton](https://en.wikipedia.org/wiki/Weighted_automaton) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Weighted_automaton?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.