Systems and methods for determining the determinizability of finite-state automata and transducers

• US 7,240,004 B1
• Filed: 06/20/2002
• Issued: 07/03/2007
• Est. Priority Date: 03/04/2002
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Mohri, Mehryar, Allauzen, Cyril
• Primary Examiner(s): Hudspeth; David R.
• Assistant Examiner(s): Sked; Matthew J.
• Application Number:
  US10/176,465
• Time in Patent Office: 1,839 Days
• Field of Search: None
• US Class Current: 704/255
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

Finite-state transducers and weighted finite-state automata may not be determinizable. The twins property can be used to characterize the determinizability of such devices. For a weighted finite-state automaton or transducer, that weighted finite-state automaton or transducer and its inverse are intersected or composed, respectively. The resulting device is checked to determine if it has the cycle-identity property. If not, the original weighted finite-state automaton or transducer is not determinizable. For a weighted or unweighted finite-state transducer, that device is checked to determine if it is functional. If not, that device is not determinizable. That device is then composed with its inverse. The composed device is checked to determine if every edge in the composed device having a cycle-accessible end state meets at least one of a number of conditions. If so, the original device has the twins property. If the original device has the twins property, then it is determinizable.

Claims

1. A method for determining if a first weighted finite-state transducer is determinizable, comprising:

receiving the first weighted finite-state transducer having at least one weight assigned to a transition between two states;

determining an inverse weighted finite-state transducer from the first weighted finite-state transducer;

composing the first weighted finite-state transducer and the inverse weighted finite-state transducer to form a composed weighted finite-state transducer; and

determining if the composed weighted finite-state transducer meets a cycle-identity condition;

wherein, if the composed weighted finite-state transducer does not meet the cycle-identity condition, the first weighted finite-state transducer is not determinizable; and

if the composed weighted finite-state transducer meets the cycle identity condition, the first weighted finite-state transducer is determinizable, and creating an output indicating that the first weighted finite-state transducer meets the cycle-identity condition.

2. The method of claim 1, wherein determining if the composed weighted finite-state transducer meets the cycle-identity condition comprises:

(a) identifying all strongly connected components in the composed weighted finite-state transducer;

(b) selecting one of the identified strongly connected component as a current strongly connected component;

(c) identifying all transitions in the current strongly connected component;

(d) selecting a first transition of the current strongly connected component;

(e) determining a weight of an end state of a last transition of the current strongly connected component; and

(f) determining at least one of;

if the weight of the end state of the last transition of the current strongly connected component is equal to an identity value of a multiplicative operator of the weighted finite-state transducer; and

wherein, if the weight of the end state of the last transition of the current strongly connected component is not equal to the identity value of the multiplicative operator of the weighted finite-state transducer or if the weight of the end state of the last transition of the current strongly connected component is not equal to the weight of the beginning state of the first transition, the weighted finite-state transducer is not determinizable.

3. The method of claim 2, wherein determining the weight of the end state of the last transition of the current strongly connected component comprises:

selecting a first transition as a current transition;

determining a multiplicative product of a weight of a beginning state of the current transition of the current strongly connected component and a weight of the current transition;

setting the weight of an end state of the current transition to the multiplicative product, wherein the end state of the current transition is the beginning state of a next transition of the current strongly connected component; and

repeating the multiplicative product determining and weight setting steps using the next transition as the current transition until the end state of the current transition is the beginning state of the first transition.

4. The method of claim 2, further comprising, if the weight of the end state of the last transition of the current strongly connected component is equal to the identity value of the multiplicative operator of the weighted finite-state transducer and the weight of the end state of the last transition of the current strongly connected component is equal to the weight of the beginning state of the first transition of the current strongly connected component, repeating steps (b)-(f) until all strongly connected components have been selected as the current strongly connected component, wherein, for each identified strongly connected component, if the weight of the end state of the last transition of that strongly connected component is equal to the identity value of the multiplicative operator of the weighted finite-state transducer and is equal to the weight of the beginning state of the first transition that strongly connected component, the intersection weighted finite-state transducer meets the cycle-identity condition.

5. The method of claim 1, wherein determining if the composed weighted finite-state transducer meets the cycle-identity condition comprises:

(a) identifying all strongly connected components in the composed weighted finite-state transducer;

(b) selecting one of the identified strongly connected components that has not been selected as a current strongly connected component;

(c) selecting a start state of the selected strongly connected component as a current state;

(d) setting the weight of the selected start state to the identity value of a multiplicative operator of the first weighted finite-state transducer;

(e) selecting a transition from the current state that has not yet been selected as the current transition;

(f) determining if a weight of the end state is defined;

(g) if the weight of the end state is not defined, defining the weight of the end state as the multiplicative product of the weight of the current state and a weight of the current transition;

(h) determining if the weight of the end state is equal to the multiplicative product of the weight of the current state and the weight of the current transition, wherein, if the weight of the end state is not equal to the multiplicative product of the weight of the current state and the weight of the current transition, the first weighted finite-state transducer is not determinizable;

(i) if the weight of the end state is equal to the multiplicative product of the weight of the current state and the weight of the current transition, determining if an end state of the current transition is the start state;

(i1) if the end state is not the start state, (j) selecting the end state of the current transition as the current state and returning to step (e);

(i2) if the end state is the start state, (k) determining if there is a transition from the current state to another state of the current strongly connected component that has not yet been selected;

(k1) if there is a transition from the current state to another state of the current strongly connected component that has not yet been selected, returning to step (e);

(k2) if there is not a transition from the current state to another state of the current strongly connected component that has not yet been selected, (l) determining if the beginning state of the current transition is the start state;

(l1) if the current state is not the start state, (m) selecting the last selected transition whose end state is the current state and returning to step (j);

(l2) if the current state is the start state, (n) determining if all transitions from the start state have been selected;

(n1) if all transitions from the start state have not been selected, (O) returning to step (e);

(n2) if all transitions from the start state have been selected, (p) determining if all strongly connected components have been selected, wherein, if all strongly connected components have been selected, the first weighted finite-state transducer has the cycle-identity condition; and

(q) if all strongly connected components have not been selected, returning to step (b).

6. The method of claim 1, further comprising:

determining if the first weighted finite-state transducer is trim; and

if not, converting the first weighted finite-state transducer into an equivalent trim weighted finite-state transducer, wherein the trim weighted finite-state transducer is used in place of the first weighted finite-state transducer in the inverse weighted finite-state transducer determining step and the intersecting step.

7. The method of claim 1, further comprising, when the intersection weighted finite-state transducer meets the cycle-identity condition, determining if the first weighted finite-state transducer is functional, wherein, if the first weighted finite-state transducer is not functional, the first weighted finite-state transducer is not determinizable.

8. The method of claim 7, wherein determining if the first weighted finite-state transducer is functional comprises:

composing the first weighted finite-state transducer with the inverse finite-state transducer to generate a composed finite-state transducer; and

determining if the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer.

9. The method of claim 8, wherein determining if the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer comprises:

determining all successful paths in the composed finite-state transducer; and

determining, for each successful path, if the input string of that successful path is equal to the output string of that successful path;

wherein, if the input string of that successful path is equal to the output string of that successful path for all successful paths, the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer.

10. The method of claim 8, wherein determining if the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer comprises:

determining all successful paths in the composed finite-state transducer; and

determining, for each successful path, if the residue for that successful path is equal to zero;

wherein, if the residue for that successful path is equal to zero for all successful paths, the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer.

11. The method of claim 8, wherein determining if the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer comprises:

(a) selecting an initial state of the composed finite-state transducer as a current state;

(b) selecting a transition from the current state that has not been selected as a current transition;

(c) determining if an end state of the current transition is coaccessible;

(d) if the end state of the current transition is coaccessible, determining whether a residue for the end state of the current transition has been defined;

(e) if the residue for the end state of the current transition e has not been defined, defining the residue for the current end state as i[e]<sup>−

1</sup>R[p[e]] o[e], where i[e] is the input symbol of the current transition e, R[p[e]] is the residue of the beginning state of the current transition e and o[e] is the output symbol of the current transition e;

(f) determining if the residue for the end state of the current transition is equal to i[e]<sup>−

1</sup>R[p[e]] o[e], wherein, if the residue for the end state of the current transition is not equal to i[e]<sup>−

1</sup>R[p[e]] o[e], the first weighted finite-state transducer is not determinizable;

(g) if the residue for the end state of the current transition is equal to i[e]<sup>−

1</sup>R[p[e]] o[e], determining if the end state of the current transition is a final state;

(h) if the end state of the current transition is a final state, determining if the residue of the end state of the current transition is equal to the empty string, wherein, if the residue of the end state of the current transition is not equal to the empty string, the first weighted finite-state transducer is not determinizable;

(i) if the end state of the current transition is not a final state or if the residue of the end state of the current transition is equal to the empty string, determining if there are any unselected transitions from the end state of the current transition;

(j) if there are any unselected transitions from the end state of the current transition, selecting the end state of the current transition as the current state and returning to step (b);

(k) if there are no unselected transitions from the end state of the current transition or the end state of the current transition is not coaccessible, (l) determining if there are any unselected transitions from the current state;

(l1) if there are any unselected transitions from the current state, (m) returning to step (b);

(l2) if there are no unselected transitions from the current state, (n) determining if the current state is the initial state, wherein, if the current state is the initial state, the first weighted finite-state transducer is functional; and

(o) if the current state is not the initial state, selecting the last selected transition whose end state is the current state and returning to step (l).

12. The method of claim 7, further comprising, when the first weighted finite-state transducer is functional, determining if, for the composed weighted finite-state transducer, a residue purity condition holds for any transition in the composed weighted finite-state transducer that has an end state that is cycle-accessible.

13. The method of claim 12, wherein, if the residue purity condition does not hold for any transition in the composed weighted finite-state transducer that has an end state that is cycle-accessible, the first weighted finite-state transducer is not determinizable.

14. The method of claim 7, further comprising, when the first weighted finite-state transducer is functional, determining if, for the composed weighted finite-state transducer and for any path π

from an initial state of the composed finite-state transducer to a strongly connected component c of the composed finite-state transducer, the residue <

π

>

of the path π

is equal to the residue <

π

c>

of the concatenated path π

c.

15. The method of claim 14, wherein, if the residue <

π

>

of the path π

is not equal to the residue <

π

c>

of the concatenated path π

c for any path π

in the composed weighted finite-state transducer that is cycle-accessible, the first weighted finite-state transducer is not determinizable.

16. The method of claim 7, further comprising, when the first weighted finite-state transducer is functional, determining if, for the composed weighted finite-state transducer, at least one of a first residue condition and a second residue condition holds for every transition in the composed weighted finite-state transducer that has an end state that is cycle-accessible.

17. The method of claim 16, wherein the first residue condition is, for a non-empty strongly connected component of the composed weighted finite-state transducer that has three paths π

₁, π

₂ and π

, each having distinct residues, that, leading from an initial state to that strongly connected component, the residue of the residue of path π

₁ and the residue of the path π

commutes with the residue of the residue of the path π

₁ and the residue of the path π

₂.

18. The method of claim 16, wherein the second residue condition is that, for three paths π

₁, π

₂, and π

₃ in that composed finite-state transducer that lead from the initial state to the same cycle-accessible state, the residue of the residue of the path π

₁ and the residue of the path π

₂ commute with the residue of the residue of the path π

₁ and the residue of the path π

₃.

19. The method of claim 16, wherein determining if the first residue condition holds for a transition in the composed weighted finite-state transducer comprises:

determining if a strongly connected component that contains an end state of that transition is equal to a strongly connected component that contains a beginning state of that transition; and

determining if a residue for the end state is equal to a residue for the beginning state concatenated with that transition.

20. The method of claim 16, wherein determining if the second residue condition holds for a transition in the composed weighted finite-state transducer comprises:

determining if a residue of a first residue for the end state of that transition and a second residue for the end state of that transition commutes with a residue of the first residue for the end state of that transition and a third residue for the end state of that transition.

21. The method of claim 16, wherein determining, for the composed weighted finite-state transducer, if at least one of a first residue condition and a second residue condition holds for any transition in the composed weighted finite-state transducer that has an end state that is cycle-accessible, comprises:

(a) selecting the initial state of the composed weighted finite-state transducer as the current state;

(b) selecting a transition extending from the current state that has an end state that is cycle-accessible and that has not previously been selected as a current transition;

(c) determining a current residue for an end state of the current transition; and

(d) determining if the current residue is pure, wherein, if the current residue is not pure, the weighted finite-state transducer is not determinizable.

22. The method of claim 21, further comprising:

(e) determining if a first strongly connected component containing a beginning state of the current transition and a second strongly connected component containing the end state of the current transition are equivalent;

(e1) if the first and second strongly connected components are not equivalent, (f) determining if a first residue for the end state of the current transition has been defined;

(f1) if the first residue for the end state of the current transition has been defined, (g) determining if a second residue for the end state of the current transition has been defined;

(g1) if the second residue for the end state of the current transition has been defined, (h) determining a third residue of the first residue for the end state of the current transition and the current residue and a fourth residue of the first residue for the end state of the current transition and the second residue for the end state of the current transition; and

(i) determining if the third and fourth residues commute, wherein, if the third and fourth residues do not commute, the weighted finite-state transducer is not determinizable.

23. The method of claim 22, further comprising:

(g2) if the second residue for the end state of the current transition has not been defined, (j) determining if the first residue for the end state of the current transition is equal to the current residue;

(j1) if the first residue for the end state of the current transition is not equal to the current residue, (k) determining if only the first residue for the end state of the current transition has been defined;

(k1) if only the first residue for the end state of the current transition has been defined, (l) defining the second residue for the end state of the current transition as the current residue; and

(m) repeating the method beginning with step (b) using the end state of the current transition as the current state.

24. The method of claim 23, further comprising:

(k2) if more than the first residue for the end state of the current transition has been defined, (n) determining if a kth residue for the end state of the current transition has been defined;

(n1) if the kth residue for the end state of the current transition has not been defined, (o) defining the kth residue for the end state of the current transition as the current residue; and

(p) repeating the method beginning with step (b) using the end state of the current transition as the current state.

25. The method of claim 24, further comprising:

(n2) if the kth residue for the end state of the current transition has been defined, (q) determining if there are any unselected transitions extending from the current state;

(q1) if there are any unselected transitions extending from the current state, (r) repeating the method beginning with step (b);

(q2) if there are no unselected transitions extending from the current state, (s) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions;

(t) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state; and

(u) returning to step (q).

26. The method of claim 23, further comprising:

(j2) if the first residue for the end state of the current transition is equal to the current residue, (n) determining if a kth residue for the end state of the current transition has been defined;

(n1) if the kth residue for the end state of the current transition has not been defined, (o) defining the kth residue for the end state of the current transition as the current residue; and

(p) repeating the method beginning with step (b) using the end state of the current transition as the current state.

27. The method of claim 26, further comprising:

(n2) if the kth residue for the end state of the current transition has been defined, (q) determining if there are any unselected transitions extending from the current state;

(q1) if there are any unselected transitions extending from the current state, (r) repeating the method beginning with step (b);

(q2) if there are no unselected transitions extending from the current state, (s) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions;

(t) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state; and

(u) returning to step (q).

28. The method of claim 22, further comprising:

(i1) if the third and fourth residues commute, (j) determining if a kth residue for the end state of the current transition has been defined;

(j1) if the kth residue for the end state of the current transition has not been defined, (k) defining the kth residue for the end state of the current transition as the current residue; and

(m) repeating the method beginning with step (b) using the end state of the current transition as the current state.

29. The method of claim 28, further comprising:

(j2) if the kth residue for the end state of the current transition has been defined, (n) determining if there are any unselected transitions extending from the current state;

(n1) if there are any unselected transitions extending from the current state, repeating the method beginning with step (b);

(n2) if there are no unselected transitions extending from the current state, (o) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions;

(p) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state;

(q) returning to step (n).

30. The method of claim 22, further comprising:

(f2) if the first residue for the end state of the current transition has not been defined, (j) determining if a kth residue for the end state of the current transition has been defined;

(j1) if the kth residue for the end state of the current transition has not been defined, (k) defining the kth residue for the end state of the current transition as the current residue; and

(l) repeating the method beginning with step (b) using the end state of the current transition as the current state.

31. The method of claim 30, further comprising:

(j2) if the kth residue for the end state of the current transition has been defined, (m) determining if there are any unselected transitions extending from the current state;

(m1) if there are any unselected transitions extending from the current state, (n) repeating the method beginning with step (b);

(m2) if there are no unselected transitions extending from the current state, (o) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions;

(p) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state; and

(q) returning to step (m).

32. The method of claim 22, further comprising:

(e2) if the first and second strongly connected components are equivalent, (j) determining if a kth residue for the end state of the current transition has been defined;

(j1) if the kth residue for the end state of the current transition has not been defined, (k) defining the kth residue for the end state of the current transition as the current residue; and

(l) repeating the method beginning with step (b) using the end state of the current transition as the current state.

33. The method of claim 32, further comprising, (j2) if the kth residue for the end state of the current transition has been defined, (m) determining if the kth residue for the end state of the current transition is equal to the current residue, wherein, if the kth residue for the end state of the current transition is not equal to the current residue, the weighted finite-state transducer is not determinizable.

34. The method of claim 32, further comprising:

(j2) if the kth residue for the end state of the current transition has been defined, (m) determining if the kth residue for the end state of the current transition is equal to the current residue;

(m1) if the kth residue for the end state of the current transition is equal to the current residue, (n) determining if there are any unselected transitions extending from the current state;

(n1) if there are any unselected transitions extending from the current state, (o) repeating the method beginning with step (b); and

(n2) if there are no unselected transitions extending from the current state, (p) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions.

35. The method of claim 34, further comprising:

(q) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state;

(r) returning to step (n).

36. A method for determining if a first weighted finite-state automaton is determinizable, comprising:

receiving the first weighted finite-state automaton having at least one weight assigned to a transition between two states;

determining an inverse weighted finite-state automaton from the first weighted finite-state automaton;

intersecting the first weighted finite-state automaton and the inverse weighted finite-state automaton to form an intersection weighted finite-state automaton; and

determining if the intersection weighted finite-state automaton meets a cycle-identity condition;

wherein, if the intersection weighted finite-state automaton does not meet the cycle-identity condition, the first weighted finite-state automaton is not determinizable; and

if the intersection weighted finite-state transducer meets the cycle identity condition, the first weighted finite-state automation is determinizable, and creating an output indicating that the first weighted finite-state automation meets the cycle-identity condition.

37. The method of claim 36, wherein determining if the intersection weighted finite-state automaton meets the cycle-identity condition comprises

(a) identifying all strongly connected components in the intersection weighted finite-state automaton;

(b) selecting one of the identified strongly connected component as a current strongly connected component;

(c) identifying all transitions in the current strongly connected component;

(d) selecting a first transition of the current strongly connected component;

(e) determining a weight of an end state of a last transition of the current strongly connected component; and

(f) determining at least one of;

if the weight of the end state of the last transition of the current strongly connected component is equal to an identity value of a multiplicative operator of the weighted finite-state automaton; and

if the weight of the end state of the last transition of the current strongly connected component is equal to the weight of a beginning state of the first transition;

wherein, if the weight of the end state of the last transition of the current strongly connected component is not equal to the identity value of the multiplicative operator of the weighted finite-state automaton or if the weight of the end state of the last transition of the current strongly connected component is not equal to the weight of the beginning state of the first transition, the weighted finite-state automaton is not determinizable.

38. The method of claim 37, wherein determining the weight of the end state of the last transition of the current strongly connected component comprises:

selecting a first transition as a current transition;

determining a multiplicative product of a weight of a beginning state of the current transition of the current strongly connected component and a weight of the current transition;

setting the weight of an end state of the current transition to the multiplicative product, wherein the end state of the current transition is the beginning state of a next transition of the current strongly connected component; and

repeating the multiplicative product determining and weight setting steps using the next transition as the current transition until the end state of the current transition is the beginning state of the first transition.

39. The method of claim 37, further comprising, if the weight of the end state of the last transition of the current strongly connected component is equal to the identity value of the multiplicative operator of the weighted finite-state automaton and the weight of the end state of the last transition of the current strongly connected component is equal to the weight of the beginning state of the first transition of the current strongly connected component, repeating steps (b)-(f) until all strongly connected components have been selected as the current strongly connected component, wherein, for each identified strongly connected component, if the weight of the end state of the last transition of that strongly connected component is equal to the identity value of the multiplicative operator of the weighted finite-state automaton and is equal to the weight of the beginning state of the first transition of that strongly connected component, the weighted finite-state automaton is determinizable.

40. The method of claim 36, wherein determining if the intersection weighted finite-state automaton meets the cycle-identity condition comprises

(a) identifying all strongly connected components in the intersection weighted finite-state automaton;

(b) selecting one of the identified strongly connected component that has not been selected as a current strongly connected component;

(c) selecting a start state of the selected strongly connected component as a current state;

(d) setting the weight of the selected start state to the identity value of a multiplicative operator of the first weighted finite-state automaton;

(e) selecting a transition from the current state that has not yet been selected as the current transition;

(f) determining if a weight of the end state is defined;

(g) if the weight of the end state is not defined, defining the weight of the end state as the multiplicative product of the weight of the current state and a weight of the current transition;

(h) determining if the weight of the end state is equal to the multiplicative product of the weight of the current state and the weight of the current transition, wherein, if the weight of the end state is not equal to the multiplicative product of the weight of the current state and the weight of the current transition, the first weighted finite-state automaton is not determinizable;

(i) if the weight of the end state is equal to the multiplicative product of the weight of the current state and the weight of the current transition, determining if an end state of the current transition is the start state;

(i1) if the end state is not the start state, (j) selecting the end state of the current transition as the current state and returning to step (e);

(i2) if the end state is the start state, (k) determining if there is a transition from the current state to another state of the current strongly connected component that has not yet been selected;

(k1) if there is a transition from the current state to another state of the current strongly connected component that has not yet been selected, (l) returning to step (e);

(k2) if there is not a transition from the current state to another state of the current strongly connected component that has not yet been selected, (m) determining if the beginning state of the current transition is the start state;

(m1) if the current state is not the start state, (n) selecting the last selected transition whose end state is the current state and returning to step (k);

(m2) if the current state is the start state, (o) determining if all transitions from the start state have been selected;

(o1) if all transitions from the start state have not been selected, (p) returning to step (e);

(o2) if all transitions from the start state have been selected, (q) determining if all strongly connected components have been selected, wherein, if all strongly connected components have been selected, the first weighted finite-state automaton is determinizable; and

(r) if all strongly connected components have not been selected, returning to step (b).

41. The method of claim 36, further comprising:

determining if the first weighted finite-state automaton is trim; and

if not, converting the first weighted finite-state automaton into an equivalent trim weighted finite-state automaton, wherein the trim weighted finite-state automaton is used in place of the first weighted finite-state automaton in the inverse weighted finite-state automaton determining step and the intersecting step.

42. A method for determining if a first finite-state transducer is determinizable, comprising:

receiving the first finite-state transducer having at least one input string assigned to a path between two states;

composing the first finite-state transducer with an inverse finite-state transducer to generate a composed finite-state transducer; and

determining if the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer,

wherein, if the composed first finite-state transducer is not equal to the identity function, the first finite-state transducer is not determinizable, and

if the composed first finite-state transducer is equal to the identity function, the first finite-state transducer is determinizable and creating an output indicating that the first finite-state transducer is equal to the identity function.

43. The method of claim 42, wherein determining if the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer comprises:

determining all successful paths in the composed finite-state transducer; and

determining, for each successful path, if the input string of that successful path is equal to the output string of that successful path;

wherein, if the input string of that successful path is equal to the output string of that successful path for all successful paths, the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer.

44. The method of claim 42, wherein determining if the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer comprises:

determining all successful paths in the composed finite-state transducer; and

determining, for each successful path, if the residue for that successful path is equal to the empty string;

wherein, if the residue for that successful path is equal to the empty string for all successful paths, the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer.

45. The method of claim 42, wherein determining if the composed finite-state transducer is equal to the identity function over the domain of that composed finite-state transducer comprises:

(a) selecting an initial state of the composed finite-state transducer as a current state;

(b) selecting a transition from the current state that has not been selected as a current transition;

(c) determining if an end state of the current transition is coaccessible;

(d) if the end state of the current transition is coaccessible, determining whether a residue for the end state of the current transition has been defined;

(e) if the residue for the end state of the current transition e has not been defined, defining the residue for the current end state as i[e]<sup>−

1</sup>R[p[e]] o[e], where i[e] is the input symbol of the current transition e, R[p[e]] is the residue of the beginning state of the current transition e and o[e] is the output symbol of the current transition e;

(f) determining if the residue for the end state of the current transition is equal to i[e]<sup>−

1</sup>R[p[e]] o[e], wherein, if the residue for the end state of the current transition is not equal to i[e]<sup>−

1</sup>R[p[e]] o[e], the first finite-state transducer is not determinizable;

(g) if the residue for the end state of the current transition is equal to i[e]<sup>−

1</sup>R[p[e]] o[e], determining if the end state of the current transition is a final state;

(h) if the end state of the current transition is a final state, determining if the residue of the end state of the current transition is equal to the empty string, wherein, if the residue of the end state of the current transition is not equal to the empty string, the first finite-state transducer is not determinizable;

(i) if the end state of the current transition is not a final state or if the residue of the end state of the current transition is equal to the empty string, determining if there are any unselected transitions from the end state of the current transition;

(j) if there are any unselected transitions from the end state of the current transition, selecting the end state of the current transition as the current state and returning to step (b);

(k) if there are no unselected transitions from the end state of the current transition or the end state of the current transition is not coaccessible, (l) determining if there are any unselected transitions from the current state;

(l1) if there are any unselected transitions from the current state, (m) returning to step (b);

(l2) if there are no unselected transitions from the current state, (n) determining if the current state is the initial state, wherein, if the current state is the initial state, the first finite-state transducer is functional; and

(o) if the current state is not the initial state, selecting the last selected transition whose end state is the current state and returning to step (1).

46. The method of claim 42, further comprising, when the first finite-state transducer is functional, determining if, for the composed finite-state transducer, a residue purity condition holds for any transition in the composed finite-state transducer that has an end state that is cycle-accessible.

47. The method of claim 46, wherein, if the residue purity condition does not hold for any transition in the composed finite-state transducer that has an end state that is cycle-accessible, the first finite-state transducer is not determinizable.

48. The method of claim 42, further comprising, when the first finite-state transducer is functional, determining if, for the composed finite-state transducer and for any path π

from an initial state of the composed finite-state transducer to a strongly connected component c of the composed finite-state transducer, a residue <

π

>

of the path π

is equal to a residue <

π

c>

of the concatenated path π

c.

49. The method of claim 48, wherein, if the residue <

π

>

of the path π

is not equal to the residue <

π

c>

of the concatenated path π

c for any path π

in the composed finite-state transducer that is cycle-accessible, the first finite-state transducer is not determinizable.

50. The method of claim 42, further comprising, when the first finite-state transducer is functional, determining if, for the composed finite-state transducer, at least one of a first residue condition and a second residue condition holds for every transition in the composed finite-state transducer that has an end state that is cycle-accessible.

51. The method of claim 50, wherein the first residue condition is, for a non-empty strongly connected component of the composed finite-state transducer that has three paths π

₁, π

₂ and π

having residues that are distinct from each other, where each path π

₁, π

₂ and π

leads from a same initial state to that strongly connected component, that the residue of the residue of path π

₁ and the residue of the path π

commutes with the residue of the residue of the path π

₁ and the residue of the path π

₂.

52. The method of claim 50, wherein the second residue condition is, for three paths π

₁, π

₂, and π

₃ in that composed finite-state transducer, where each path π

₁, π

₂ and π

leads from the same initial state to the same cycle-accessible state, that the residue of the residue of the path π

₁ and the residue of the path π

₂ commutes with the residue of the residue of the path π

₁ and the residue of the path π

₃.

53. The method of claim 50, wherein determining if the first residue condition holds for a transition in the composed finite-state transducer comprises:

determining if a strongly connected component that contains an end state of that transition is equal to a strongly connected component that contains a beginning state of that transition; and

determining if a residue for the end state is equal to a residue for the beginning state concatenated with that transition.

54. The method of claim 50, wherein determining if the second residue condition holds for a transition in the composed finite-state transducer comprises:

determining if a residue of a first residue for the end state of that transition and a second residue for the end state of that transition commutes with a residue of the first residue for the end state of that transition and a third residue for the end state of that transition.

55. The method of claim 50, wherein determining, for the composed finite-state transducer, if at least one of a first residue condition and a second residue condition holds for any transition in the composed finite-state transducer that has an end state that is cycle-accessible comprises:

(a) selecting the initial state of the composed finite-state transducer as the current state;

(b) selecting a transition extending from the current state that has an end state that is cycle-accessible and that has not previously been selected as a current transition;

(c) determining a current residue for an end state of the current transition; and

(d) determining if the current residue is pure, wherein, if the current residue is not pure, the finite-state transducer is not determinizable.

56. The method of claim 55, further comprising:

(e) determining if a first strongly connected component containing a beginning state of the current transition and a second strongly connected component containing the end state of the current transition are equivalent;

(e1) if the first and second strongly connected components are not equivalent, (f) determining if a first residue for the end state of the current transition has been defined;

(f1) if the first residue for the end state of the current transition has been defined, (g) determining if a second residue for the end state of the current transition has been defined;

(g1) if the second residue for the end state of the current transition has been defined, (h) determining a third residue of the first residue for the end state of the current transition and the current residue and a fourth residue of the first residue for the end state of the current transition and the second residue for the end state of the current transition; and

(i) determining if the third and fourth residues commute, wherein, if the third and fourth residues do not commute, the finite-state transducer is not determinizable.

57. The method of claim 56, further comprising:

(g2) if the second residue for the end state of the current transition has not been defined, (j) determining if the first residue for the end state of the current transition is equal to the current residue;

(j1) if the first residue for the end state of the current transition is not equal to the current residue, (k) determining if only the first residue for the end state of the current transition has been defined;

(k1) if only the first residue for the end state of the current transition has been defined, (l) defining the second residue for the end state of the current transition as the current residue; and

(m) repeating the method beginning with step (b) using the end state of the current transition as the current state.

58. The method of claim 57, further comprising:

(k2) if more than the first residue for the end state of the current transition has been defined, (n) determining if a kth residue for the end state of the current transition has been defined;

(n1) if the kth residue for the end state of the current transition has not been defined, (o) defining the kth residue for the end state of the current transition as the current residue; and

(p) repeating the method beginning with step (b) using the end state of the current transition as the current state.

59. The method of claim 58, further comprising:

(n2) if the kth residue for the end state of the current transition has been defined, (q) determining if there are any unselected transitions extending from the current state;

(q1) if there are any unselected transitions extending from the current state, (r) repeating the method beginning with step (b);

(q2) if there are no unselected transitions extending from the current state, (s) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions;

(t) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state; and

(u) returning to step (q).

60. The method of claim 57, further comprising:

(j2) if the first residue for the end state of the current transition is equal to the current residue, (n) determining if a kth residue for the end state of the current transition has been defined;

(n1) if the kth residue for the end state of the current transition has not been defined, (o) defining the kth residue for the end state of the current transition as the current residue; and

(p) repeating the method beginning with step (b) using the end state of the current transition as the current state.

61. The method of claim 60, further comprising:

(n2) if the kth residue for the end state of the current transition has been defined, (q) determining if there are any unselected transitions extending from the current state;

(q1) if there are any unselected transitions extending from the current state, (r) repeating the method beginning with step (b);

(q2) if there are no unselected transitions extending from the current state, (s) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions;

(t) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state; and

(u) returning to step (q).

62. The method of claim 56, further comprising:

(i1) if the third and fourth residues commute, (j) determining if a kth residue for the end state of the current transition has been defined;

(j1) if the kth residue for the end state of the current transition has not been defined, (k) defining the kth residue for the end state of the current transition as the current residue; and

(m) repeating the method beginning with step (b) using the end state of the current transition as the current state.

63. The method of claim 62, further comprising:

(j2) if the kth residue for the end state of the current transition has been defined, (n) determining if there are any unselected transitions extending from the current state;

(n1) if there are any unselected transitions extending from the current state, repeating the method beginning with step (b);

(n2) if there are no unselected transitions extending from the current state, (o) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions;

(p) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state;

(q) returning to step (n).

64. The method of claim 56, further comprising:

(f2) if the first residue for the end state of the current transition has not been defined, (j) determining if a kth residue for the end state of the current transition has been defined;

(j1) if the kth residue for the end state of the current transition has not been defined, (k) defining the kth residue for the end state of the current transition as the current residue; and

(l) repeating the method beginning with step (b) using the end state of the current transition as the current state.

65. The method of claim 64, further comprising:

(j2) if the kth residue for the end state of the current transition has been defined, (m) determining if there are any unselected transitions extending from the current state;

(m1) if there are any unselected transitions extending from the current state, repeating the method beginning with step (b);

(m2) if there are no unselected transitions extending from the current state, (n) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions;

(o) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state;

(p) returning to step (m).

66. The method of claim 56, further comprising:

(e2) if the first and second strongly connected components are equivalent, (j) determining if a kth residue for the end state of the current transition has been defined;

(j1) if the kth residue for the end state of the current transition has not been defined, (k) defining the kth residue for the end state of the current transition as the current residue; and

(l) repeating the method beginning with step (b) using the end state of the current transition as the current state.

67. The method of claim 66, further comprising, (j2) if the kth residue for the end state of the current transition has been defined, (m) determining if the kth residue for the end state of the current transition is equal to the current residue, wherein, if the kth residue for the end state of the current transition is not equal to the current residue, the finite-state transducer is not determinizable.

68. The method of claim 66, further comprising:

(j2) if the kth residue for the end state of the current transition has been defined, (m) determining if the kth residue for the end state of the current transition is equal to the current residue;

(m1) if the kth residue for the end state of the current transition is equal to the current residue, (n) determining if there are any unselected transitions extending from the current state;

(n1) if there are any unselected transitions extending from the current state, (o) repeating the method beginning with step (b); and

(n2) if there are no unselected transitions extending from the current state, (p) determining if the current state is the initial state, wherein, if the current state is the start state, every transition in the composed finite-state transducer whose end state is cycle-accessible meets one of the first and second residue conditions.

69. The method of claim 68, further comprising:

(q) if the current state is not the initial state, selecting a most-recently-selected edge whose end state is the current state as the current transition and a beginning state of the current transition as the current state; and

(r) returning to step (n).