It is wasteful to compute ti as suggested earlier , by minimizing ( cxxi ) of o ( yixE ) , since then the real work is done by an c-closure step ( Mohri , 2002 ) that implements the all-pairs version of algebraic path , whereas all we need is the single-source version .
generic epsilonremoval and input epsilonnormalization algorithms for weighted transducers
M Mohri
Then ti is the total semiring weight w0n of paths in Ti from initial state 0 to final state n ( assumed WLOG to be unique and unweighted ) . It is wasteful to compute ti as suggested earlier , by minimizing ( cxxi ) of o ( yixE ) , since then the real work is done by an c-closure step ( Mohri , 2002 ) that implements the all-pairs version of algebraic path , whereas all we need is the single-source version . If n and m are the number of states and edges ,19 then both problems are O ( n3 ) in the worst case , but the single-source version can be solved in essentially O ( m ) time for acyclic graphs and other reducible flow graphs ( Tar an , 1981b ) .
It is wasteful to compute ti as suggested earlier , by minimizing ( cxxi ) of o ( yixE ) , since then the real work is done by an c-closure step ( @@CITATION ) that implements the all-pairs version of algebraic path , whereas all we need is the single-source version .