The normalization for semirings of this type is O(|Q| 3 ) according to Mohri (2009).
given the restricted graphs that we define, this complete semiring behaves as a k-closed semiring (see our Equations (12) and (13)) because the characteristic matrix M is an upper triangular matrix, and, therefore, the time complexity is O(|δ|).