# Difference: EquivalentDoc (1 vs. 7)

#### Revision 72018-04-27 - MichaelRiley

Line: 1 to 1

 META TOPICPARENT name="FstQuickTour"

# Equivalent

Line: 13 to 13
bool Equivalent(const Fst &fst1, const Fst &fst2, double delta = kDelta);
Changed:
<
<
| %DOX{namespacefst.html#Equivalent[ ]}% |
>
>
|
|
`fstequivalent a.fst b.fst`
Changed:
<
<
||
>
>
|

## Examples

#### Revision 62014-04-23 - MichaelRiley

Line: 1 to 1

 META TOPICPARENT name="FstQuickTour"

# Equivalent

Line: 47 to 47
Weighted equivalence is sensitive to machine precision when using floating-point-based weights especially with non-integral values. Consider using RandEquivalent instead.
>
>

## References

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. "The Design and Analysis of Computer Programs". Addison-Wesley, 1974.

#### Revision 52014-04-23 - MichaelRiley

Line: 1 to 1

 META TOPICPARENT name="FstQuickTour"

# Equivalent

## Description

Changed:
<
<
This operations determines if two epsilon-free deterministic weighted acceptors are equivalent, that is if they accept the same strings with the same weights.
>
>
This operation determines if two epsilon-free deterministic weighted acceptors are equivalent, that is if they accept the same strings with the same weights.

## Usage

#### Revision 42014-04-23 - MichaelRiley

Line: 1 to 1

 META TOPICPARENT name="FstQuickTour"

# Equivalent

Line: 18 to 18
fstequivalent a.fst b.fst ||
Changed:
<
<

>
>

## Examples

 `A` `B` `C`   #### Revision 32014-03-24 - MichaelRiley

Line: 1 to 1

 META TOPICPARENT name="FstQuickTour"

# Equivalent

Line: 43 to 43
where n = V1 + V2 with Vi = # of states, d is the maximal out-degree and G(n) is a very slowly growing function that can be approximated by 4 by all practical purposes.
>
>

## Caveats

Weighted equivalence is sensitive to machine precision when using floating-point-based weights especially with non-integral values. Consider using RandEquivalent instead.

## References

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. "The Design and Analysis of Computer Programs". Addison-Wesley, 1974.

#### Revision 22010-08-17 - CyrilAllauzen

Line: 1 to 1

 META TOPICPARENT name="FstQuickTour"

# Equivalent

## Description

Changed:
<
< This operations determines if two epsilon-free deterministic weighted acceptors are equivalent.
>
>
This operations determines if two epsilon-free deterministic weighted acceptors are equivalent, that is if they accept the same strings with the same weights.

Line: 20 to 20

## Example

Changed:
<
< TBA
>
>
 `A` `B` `C`   ```Equivalent(A, B);  // returns true
Equivalent(A, C); // returns false

\$ if fstequivalent a.fst b.fst; then echo true; else echo false; fi
true
\$ if fstequivalent a.fst c.fst; then echo true; else echo false; fi
false
```

## Complexity

Deleted:
<
< `Equivalent`
• Time:
Changed:
<
<
• Unweighted: quasi-linear, i.e. O(n G(n))
• Weighted: complexity of unweighted + complexity of shortest-distance
• Space: quasi-linear, i.e. O(n G(n))
where n = V1 + V2 with Vi = # of states and G(n) is a very slowly growing function that can be approximated by 4 by all practical purposes.
>
>
• Unweighted: quasi-linear, i.e. O(d n G(n))
• Weighted: complexity of unweighted + complexity of weight-pushing
• Space: linear, i.e. O(n + d)
where n = V1 + V2 with Vi = # of states, d is the maximal out-degree and G(n) is a very slowly growing function that can be approximated by 4 by all practical purposes.

## References

Line: 38 to 48

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. "The Design and Analysis of Computer Programs". Addison-Wesley, 1974.

-- CyrilAllauzen - 03 Mar 2009

>
>
 META FILEATTACHMENT attachment="equiv1.png" attr="" comment="Equivalent example: automaton A" date="1282081141" name="equiv1.png" path="equiv1.png" size="15468" stream="equiv1.png" tmpFilename="/var/tmp/CGItemp26577" user="CyrilAllauzen" version="1" attachment="equiv2.png" attr="" comment="Equivalent example: automaton B" date="1282081174" name="equiv2.png" path="equiv2.png" size="11111" stream="equiv2.png" tmpFilename="/var/tmp/CGItemp26834" user="CyrilAllauzen" version="1" attachment="equiv3.png" attr="" comment="Equivalent example: automaton C" date="1282081346" name="equiv3.png" path="equiv3.png" size="11702" stream="equiv3.png" tmpFilename="/var/tmp/CGItemp26642" user="CyrilAllauzen" version="1"

#### Revision 12009-03-03 - CyrilAllauzen

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

# Equivalent

## Description This operations determines if two epsilon-free deterministic weighted acceptors are equivalent.

## Usage

 ```template bool Equivalent(const Fst &fst1, const Fst &fst2, double delta = kDelta); ``` %DOX{namespacefst.html#Equivalent[ ]}% ```fstequivalent a.fst b.fst ```

## Example TBA

## Complexity `Equivalent`

• Time:
• Unweighted: quasi-linear, i.e. O(n G(n))
• Weighted: complexity of unweighted + complexity of shortest-distance
• Space: quasi-linear, i.e. O(n G(n))
where n = V1 + V2 with Vi = # of states and G(n) is a very slowly growing function that can be approximated by 4 by all practical purposes.

## References

• Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. "The Design and Analysis of Computer Programs". Addison-Wesley, 1974.

-- CyrilAllauzen - 03 Mar 2009

Copyright © 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