TWiki
>
FST Web
>
FstGlossary
(2014-04-23,
MichaelRiley
)
(raw view)
E
dit
A
ttach
---+ !OpenFst Glossary #AcceptorDef $ *acceptor*: An acceptor is a finite automaton where each transition has a label and possibly a weight. In this library, an acceptor is represented as a transducer with the input and output label of each transition being equal. #AccessibleDef $ *accessible*: A state *q* is accessible iff there is a path from the initial state to *q*. #CoAccessibleDef $ *co-accessible*: A state *q* is co-accessible iff there is a path from *q* to a final state. #DelayedDef $ *delayed*: An FST is delayed (or _lazy_, _on-the-fly_, or _dynamic_) if the computation of its states and transitions occur only when requested. The complexity of a delayed FSTs constructor is constant-time, while the complexity of its traversal is a function of only those states and transitions that are visited. #DeterministicDef $ *deterministic*: An acceptor is deterministic iff for each state *q* there is at most one transition labeled with a given label. A transducer can be input deterministic (or _subsequential_) or output deterministic. #EpsilonDef $ *epsilon, ε*: An input label that consumes no input or an output label emits no output. #EquivalentDef $ *equivalent*: Two transducers are equivalent if for each input string, they produce the same output strings with the same weight. The output strings, however, may differ in the number of paths, in the location of epsilon transitions, or in the distribution of the weights along the paths. #FunctionalDef $ *functional*: A transducer is functional if each input string is transduced to a unique output string. There may be multiple paths, however, that contain this input and output string pair. #MultiplicityDef $ *multiplicity*: The maximum number of times a label is repeated at a state - a measure of [[#DetermnisticDef][non-determinism]]. #OutDegreeDef $ *out-degree*: The number of transitions exiting a state. #SemiringDef $ *semiring*: A semiring is a set of elements (_weights_) together with two binary operations ⊕ and ⊗ and two designated elements <span style="text-decoration:overline">0</span> and <span style="text-decoration:overline">1</span> with the following properties: * ⊕: associative, commutative, and has <span style="text-decoration:overline">0</span> as its identity. * ⊗: associative and has identity <span style="text-decoration:overline">1</span>, distributes w.r.t. ⊕, and has <span style="text-decoration:overline">0</span> as an annihilator: <span style="text-decoration:overline">0</span> ⊗ a = a ⊗ <span style="text-decoration:overline">0</span> = <span style="text-decoration:overline">0</span>. #SuccessfulPathDef $ *successful path*: A path from the initial state to some final state. #TransducerDef $ *transducer*: A transducer is a finite automaton where each transition has an input label, an output label, and possibly a weight. #TrimDef $ *trim*: An automaton is trim (or _connected_) iff it contains no [[#AccessibleDef][inaccessible]] or [[#CoAccessibleDef][no-coaccessible]] states. #UnambiguousDef $ *unambiguous*: A transducer is unambiguous iff it has at most one successful path for any input labeling. #ZeroSumFreeDef $ *zero-sum-free*: A semiring is zero-sum-free if ∀ =a,b: a ⊕ b = <span style="text-decoration:overline">0</span> ⇒ a = b = <span style="text-decoration:overline">0</span>=.
E
dit
|
A
ttach
|
Watch
|
P
rint version
|
H
istory
: r13
<
r12
<
r11
<
r10
<
r9
|
B
acklinks
|
V
iew topic
|
WYSIWYG
|
M
ore topic actions
Topic revision: r13 - 2014-04-23
-
MichaelRiley
FST
Log In
or
Register
FST Web
Create New Topic
Index
Search
Changes
Notifications
Statistics
Preferences
Webs
Contrib
FST
Forum
GRM
Kernel
Main
Sandbox
TWiki
Main
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback