Difference: FstWeightRequirements (1 vs. 15)

Revision 152012-03-01 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weight Requirements

Line: 17 to 17
  In addition, the following must be defined for a Weight:
  • Member: predicate on set membership.
Added:
>
>
  • 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.

Revision 142011-02-01 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weight Requirements

Line: 17 to 17
  In addition, the following must be defined for a Weight:
  • Member: predicate on set membership.
Changed:
<
<
  • >>: reads textual representation of a weight.
  • <<: prints textual representation of a weight.
>
>
  • >>: 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.

Revision 132010-08-11 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weight Requirements

Line: 41 to 41
 
    • Idempotent: ∀ a: a ⊕ a = a.
    • Path: ∀ a, b: a ⊕ b = a or a ⊕ b = b.
Deleted:
<
<
-- MichaelRiley - 23 Feb 2009
 
META TOPICMOVED by="MichaelRiley" date="1236117130" from="FST.FstWeights" to="FST.FstWeightRequirements"

Revision 122009-03-06 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weight Requirements

Line: 29 to 29
 a' = Divide(c, b, DIVIDE_RIGHT) if a right semiring and a'.Member() and Times(a', b) = c
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.
Changed:
<
<
  • Reverse: a mapping from Weight to ReverseWeight s.t.
>
>
  • Reverse: a mapping from Weight to ReverseWeight s.t.
 Reverse(Reverse(a)) = a
Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))

Revision 112009-03-03 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"
Changed:
<
<

FST Weights

>
>

FST Weight Requirements

  A semiring is specified by two binary operations ⊕ and ⊗ and two designated elements 0 and 1 with the following properties:
Line: 42 to 42
 
    • Path: ∀ a, b: a ⊕ b = a or a ⊕ b = b.

-- MichaelRiley - 23 Feb 2009 \ No newline at end of file

Added:
>
>
META TOPICMOVED by="MichaelRiley" date="1236117130" from="FST.FstWeights" to="FST.FstWeightRequirements"

Revision 102009-02-26 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weights

Line: 21 to 21
 
  • <<: prints textual representation of a weight.
  • Read(istream &): reads binary representation of a weight.
  • Write(ostream &): writes binary representation of a weight.
Changed:
<
<
  • Hash: maps weight to ssize_t.
>
>
  • Hash: maps weight to size_t.
 
  • ApproxEqual: approximate equality (for inexact weights)
  • Quantize: quantizes wrt delta (for inexact weights)
  • Divide: ∀ a,b,c s.t. Times(a, b) = c
Line: 41 to 41
 
    • Idempotent: ∀ a: a ⊕ a = a.
    • Path: ∀ a, b: a ⊕ b = a or a ⊕ b = b.
Changed:
<
<
-- MichaelRiley - 25 May 2007
>
>
-- MichaelRiley - 23 Feb 2009
 \ No newline at end of file

Revision 92008-11-21 - CyrilAllauzen

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weights

Line: 25 to 25
 
  • ApproxEqual: approximate equality (for inexact weights)
  • Quantize: quantizes wrt delta (for inexact weights)
  • Divide: ∀ a,b,c s.t. Times(a, b) = c
Changed:
<
<
b = Divide(c, a, DIVIDE_LEFT) if a left semiring and b.Member()
a = Divide(c, b, DIVIDE_RIGHT) if a right semiring and a.Member()
b = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a commutative semiring and b.Member()
>
>
b' = Divide(c, a, DIVIDE_LEFT) if a left semiring, b'.Member() and Times(a, b') = c
a' = Divide(c, b, DIVIDE_RIGHT) if a right semiring and a'.Member() and Times(a', b) = c
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.
    Reverse(Reverse(a)) = a

Revision 82007-07-11 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weights

Changed:
<
<
A semiring is specified by two binary operations Plus(x, y) and Times(x, y) and two designated elements Zero and One with the following properties:
  • Plus: associative, commutative, and has Zero as its identity.
  • Times: associative and has identity One, distributes w.r.t. Plus, and has Zero as an annihilator: Times(Zero(), a) = Times(a, Zero()) = Zero().
>
>
A semiring is specified by two binary operations ⊕ and ⊗ and two designated elements 0 and 1 with the following properties:
  • ⊕: associative, commutative, and has 0 as its identity.
  • ⊗: associative and has identity 1, distributes w.r.t. ⊕, and has 0 as an annihilator: 0 ⊗ a = a ⊗ 0 = 0.
  A left semiring distributes on the left; a right semiring is similarly defined.
Changed:
<
<
A Weight class is required to be (at least) a left or right semiring.
>
>
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.
 
Changed:
<
<
In addition, the following should be defined for a Weight:
>
>
In addition, the following must be defined for a Weight:
 
  • Member: predicate on set membership.
  • >>: reads textual representation of a weight.
  • <<: prints textual representation of a weight.
Line: 35 to 38
 
    • LeftSemiring: indicates weights form a left semiring
    • RightSemiring: indicates weights form a right semiring
    • Commutative: ∀ a,b: Times(a, b) = Times(b, a)
Changed:
<
<
    • Idempotent: ∀ a: Plus(a, a) = a.
    • Path: ∀ a, b: Plus(a, b) = a or Plus(a, b) = b.
>
>
    • Idempotent: ∀ a: a ⊕ a = a.
    • Path: ∀ a, b: a ⊕ b = a or a ⊕ b = b.
  -- MichaelRiley - 25 May 2007 \ No newline at end of file

Revision 72007-07-10 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weights

Line: 14 to 14
  In addition, the following should be defined for a Weight:
  • Member: predicate on set membership.
Changed:
<
<
  • >>: reads weight.
  • <<: prints weight.
  • Read(InputBuffer *buf): reads from an input buffer.
  • Write(OutputBuffer *buf): writes to an output buffer.
>
>
  • >>: 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 ssize_t.
  • ApproxEqual: approximate equality (for inexact weights)
  • Quantize: quantizes wrt delta (for inexact weights)

Revision 62007-07-07 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weights

Line: 16 to 16
 
  • Member: predicate on set membership.
  • >>: reads weight.
  • <<: prints weight.
Changed:
<
<
  • Weight(const string &): reads from byte array.
  • Data(string *): writes to byte array.
>
>
  • Read(InputBuffer *buf): reads from an input buffer.
  • Write(OutputBuffer *buf): writes to an output buffer.
 
  • Hash: maps weight to ssize_t.
  • ApproxEqual: approximate equality (for inexact weights)
  • Quantize: quantizes wrt delta (for inexact weights)

Revision 52007-06-30 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weights

A semiring is specified by two binary operations Plus(x, y) and Times(x, y) and

Changed:
<
<
two designated elements Zero() and One() with the following properties:
>
>
two designated elements Zero and One with the following properties:
 
  • Plus: associative, commutative, and has Zero as its identity.
  • Times: associative and has identity One, distributes w.r.t. Plus, and has Zero as an annihilator: Times(Zero(), a) = Times(a, Zero()) = Zero().
Line: 21 to 21
 
  • Hash: maps weight to ssize_t.
  • ApproxEqual: approximate equality (for inexact weights)
  • Quantize: quantizes wrt delta (for inexact weights)
Changed:
<
<
  • Divide: for all a,b,c s.t. Times(a, b) = c
    --> b = Divide(c, a, DIVIDE_LEFT) if a left semiring and b.Member()
    --> a = Divide(c, b, DIVIDE_RIGHT) if a right semiring and a.Member()
    --> b = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a commutative semiring and b.Member()
>
>
  • Divide: ∀ a,b,c s.t. Times(a, b) = c
    b = Divide(c, a, DIVIDE_LEFT) if a left semiring and b.Member()
    a = Divide(c, b, DIVIDE_RIGHT) if a right semiring and a.Member()
    b = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a commutative semiring and b.Member()
 
  • 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.
Changed:
<
<
--> Reverse(Reverse(a)) = a
--> Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
--> Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
>
>
Reverse(Reverse(a)) = a
Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
  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:
    • LeftSemiring: indicates weights form a left semiring
    • RightSemiring: indicates weights form a right semiring
Changed:
<
<
    • Commutative: for all a,b: Times(a, b) = Times(b, a)
    • Idempotent: for all a: Plus(a, a) = a.
    • Path: for all a, b: Plus(a, b) = a or Plus(a, b) = b.
>
>
    • Commutative: ∀ a,b: Times(a, b) = Times(b, a)
    • Idempotent: ∀ a: Plus(a, a) = a.
    • Path: ∀ a, b: Plus(a, b) = a or Plus(a, b) = b.
  -- MichaelRiley - 25 May 2007 \ No newline at end of file

Revision 42007-06-21 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weights

Line: 24 to 24
 
  • Divide: for all a,b,c s.t. Times(a, b) = c
    --> b = Divide(c, a, DIVIDE_LEFT) if a left semiring and b.Member()
    --> a = Divide(c, b, DIVIDE_RIGHT) if a right semiring and a.Member()
Changed:
<
<
--> b = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a commatative semiring and b.Member()
>
>
--> b = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a commutative semiring and b.Member()
 
  • 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.
    --> Reverse(Reverse(a)) = a

Revision 32007-06-16 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weights

A semiring is specified by two binary operations Plus(x, y) and Times(x, y) and two designated elements Zero() and One() with the following properties:

  • Plus: associative, commutative, and has Zero as its identity.
Changed:
<
<
  • Times: associative and has identiy One, distributes w.r.t. Plus, and
>
>
  • Times: associative and has identity One, distributes w.r.t. Plus, and
  has Zero as an annihilator: Times(Zero(), a) = Times(a, Zero()) = Zero().

A left semiring distributes on the left; a right semiring is similarly defined.

Revision 22007-05-26 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

FST Weights

Line: 31 to 31
  --> Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
--> Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
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.
Changed:
<
<
  • Properties: specifies additional properties that hold:
>
>
  • Properties: specifies properties that hold:
 
    • LeftSemiring: indicates weights form a left semiring
    • RightSemiring: indicates weights form a right semiring
    • Commutative: for all a,b: Times(a, b) = Times(b, a)

Revision 12007-05-25 - MichaelRiley

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="FstQuickTour"

FST Weights

A semiring is specified by two binary operations Plus(x, y) and Times(x, y) and two designated elements Zero() and One() with the following properties:

  • Plus: associative, commutative, and has Zero as its identity.
  • Times: associative and has identiy One, distributes w.r.t. Plus, and has Zero as an annihilator: Times(Zero(), a) = Times(a, Zero()) = Zero().

A left semiring distributes on the left; a right semiring is similarly defined.

A Weight class is required to be (at least) a left or right semiring.

In addition, the following should be defined for a Weight:

  • Member: predicate on set membership.
  • >>: reads weight.
  • <<: prints weight.
  • Weight(const string &): reads from byte array.
  • Data(string *): writes to byte array.
  • Hash: maps weight to ssize_t.
  • ApproxEqual: approximate equality (for inexact weights)
  • Quantize: quantizes wrt delta (for inexact weights)
  • Divide: for all a,b,c s.t. Times(a, b) = c
    --> b = Divide(c, a, DIVIDE_LEFT) if a left semiring and b.Member()
    --> a = Divide(c, b, DIVIDE_RIGHT) if a right semiring and a.Member()
    --> b = Divide(c, a) = Divide(c, a, DIVIDE_ANY) = Divide(c, a, DIVIDE_LEFT) = Divide(c, a, DIVIDE_RIGHT) if a commatative semiring and b.Member()
  • 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.
    --> Reverse(Reverse(a)) = a
    --> Reverse(Plus(a, b)) = Plus(Reverse(a), Reverse(b))
    --> Reverse(Times(a, b)) = Times(Reverse(b), Reverse(a))
    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 additional properties that hold:
    • LeftSemiring: indicates weights form a left semiring
    • RightSemiring: indicates weights form a right semiring
    • Commutative: for all a,b: Times(a, b) = Times(b, a)
    • Idempotent: for all a: Plus(a, a) = a.
    • Path: for all a, b: Plus(a, b) = a or Plus(a, b) = b.

-- MichaelRiley - 25 May 2007

 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback