TWiki
>
FST Web
>
FstQuickTour
>
FstWeightRequirements
(2012-03-01,
MichaelRiley
)
(raw view)
E
dit
A
ttach
---+ FST Weight Requirements A _semiring_ is specified by 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>. A left semiring distributes on the left; a right semiring is similarly defined. A =Weight= class must have binary functions =Plus= and =Times= and static member functions =Zero()= and =One()= and these must form (at least) a left or right semiring. In addition, the following must be defined for a =Weight=: * =Member=: predicate on set membership. * =NoWeight=: static member function that returns an element that is not a set member; used to signal an error. * =>>=: reads textual representation of a weight. * =<<=: prints textual representation of a weight. * =Read(istream &)=: reads binary representation of a weight. * =Write(ostream &)=: writes binary representation of a weight. * =Hash=: maps weight to size_t. * =<nop>ApproxEqual=: approximate equality (for inexact weights) * =Quantize=: quantizes wrt delta (for inexact weights) * =Divide=: ∀ =a,b,c= s.t. =Times(a, b) = c= %BR% ⇒ =b' = Divide(c, a, DIVIDE_LEFT)= if a left semiring, =b'.Member()= and =Times(a, b') = c= %BR% ⇒ =a' = Divide(c, b, DIVIDE_RIGHT)= if a right semiring and =a'.Member()= and =Times(a', b) = c= %BR% ⇒ =b' = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT)= if a commutative semiring, =b'.Member()= and =Times(a, b') = Times(b', a) = c= * =ReverseWeight=: the type of the corresponding reverse weight. Typically the same type as =Weight= for a (both left and right) semiring. For the left string semiring, it is the right string semiring. * =Reverse=: a mapping from =Weight= to =ReverseWeight= s.t. %BR% ⇒ =Reverse(Reverse(a)) = a= %BR% ⇒ =Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))= %BR% ⇒ =Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))= %BR% Typically the identity mapping in a (both left and right) semiring. In the left string semiring, it maps to the reverse string in the right string semiring. * =Properties=: specifies properties that hold: * =<nop>LeftSemiring=: indicates weights form a left semiring * =<nop>RightSemiring=: indicates weights form a right semiring * =<nop>Commutative=: ∀ =a,b=: =Times(a, b) = Times(b, a)= * =Idempotent=: ∀ =a=: =a ⊕ a = a=. * =Path=: ∀ =a, b=: =a ⊕ b = a= or =a ⊕ b = b.=
E
dit
|
A
ttach
|
Watch
|
P
rint version
|
H
istory
: r15
<
r14
<
r13
<
r12
<
r11
|
B
acklinks
|
V
iew topic
|
WYSIWYG
|
M
ore topic actions
Topic revision: r15 - 2012-03-01
-
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