Weighted automaton (original) (raw)
In theoretical computer science and formal language theory, a weighted automaton or weighted finite-state machine is a generalization of a finite-state machine in which the edges have weights, for example real numbers or integers. Finite-state machines are only capable of answering decision problems; they take as input a string and produce a Boolean output, i.e. either "accept" or "reject". In contrast, weighted automata produce a quantitative output, for example a count of how many answers are possible on a given input string, or a probability of how likely the input string is according to a probability distribution. They are one of the simplest studied models of quantitative automata.
| Property | Value |
|---|---|
| dbo:abstract | In theoretical computer science and formal language theory, a weighted automaton or weighted finite-state machine is a generalization of a finite-state machine in which the edges have weights, for example real numbers or integers. Finite-state machines are only capable of answering decision problems; they take as input a string and produce a Boolean output, i.e. either "accept" or "reject". In contrast, weighted automata produce a quantitative output, for example a count of how many answers are possible on a given input string, or a probability of how likely the input string is according to a probability distribution. They are one of the simplest studied models of quantitative automata. The definition of a weighted automaton is generally given over an arbitrary semiring , an abstract set with an addition operation and a multiplication operation . The automaton consists of a finite set of states, a finite input alphabet of characters and edges which are labeled with both a character in and a weight in . 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 to . 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. (en) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Quantitative_automata.svg?width=300 |
| dbo:wikiPageID | 43590026 (xsd:integer) |
| dbo:wikiPageLength | 13019 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096488516 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Probability_distribution dbr:Natural_language_processing dbr:Nondeterministic_finite_automaton dbr:Probabilistic_automaton dbr:Boolean_data_type dbr:Deterministic_finite_automaton dbr:Character_(computing) dbr:Cycle_(graph_theory) dbr:Decision_problem dbr:Commutative_property dbr:Generalization dbr:Function_(mathematics) dbr:Glossary_of_graph_theory dbr:Logical_conjunction dbr:Machine_learning dbr:Statistical_model dbr:Computational_learning_theory dbr:Identity_element dbr:Partial_function dbr:Path_(graph_theory) dbr:String_(computer_science) dbr:Theoretical_computer_science dbr:Matrix_ring dbr:Distributive_property dbr:Fuzzy_logic dbc:Finite_automata dbr:Finite-state_transducer dbr:Formal_language dbr:Epsilon_transition dbr:Logical_disjunction dbr:Probability dbr:Quantification_(science) dbr:Associative_property dbr:Absorbing_element dbr:Abstract_algebra dbr:Marcel-Paul_Schützenberger dbr:Integer dbr:Real_number dbr:Semiring dbr:Markov_chain dbr:Markov_decision_process dbr:Unambiguous_finite_automaton dbr:Image_compression dbr:Finite-state_machine dbr:Rational_series dbr:Timed_automaton dbr:File:Quantitative_automata.svg |
| dbp:wikiPageUsesTemplate | dbt:Clear dbt:Columns-list dbt:Reflist dbt:Rp dbt:Short_description |
| dct:subject | dbc:Finite_automata |
| rdfs:comment | In theoretical computer science and formal language theory, a weighted automaton or weighted finite-state machine is a generalization of a finite-state machine in which the edges have weights, for example real numbers or integers. Finite-state machines are only capable of answering decision problems; they take as input a string and produce a Boolean output, i.e. either "accept" or "reject". In contrast, weighted automata produce a quantitative output, for example a count of how many answers are possible on a given input string, or a probability of how likely the input string is according to a probability distribution. They are one of the simplest studied models of quantitative automata. (en) |
| rdfs:label | Weighted automaton (en) |
| owl:sameAs | wikidata:Weighted automaton https://global.dbpedia.org/id/G8dC3 |
| prov:wasDerivedFrom | wikipedia-en:Weighted_automaton?oldid=1096488516&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Quantitative_automata.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Weighted_automaton |
| is dbo:knownFor of | dbr:Marcel-Paul_Schützenberger |
| is dbo:wikiPageRedirects of | dbr:Weighted_automata dbr:Weighted_finite-state_machine |
| is dbo:wikiPageWikiLink of | dbr:Deterministic_finite_automaton dbr:Constant-recursive_sequence dbr:Automata_theory dbr:Marcel-Paul_Schützenberger dbr:Rational_series dbr:Weighted_automata dbr:Weighted_finite-state_machine |
| is foaf:primaryTopic of | wikipedia-en:Weighted_automaton |
