Publication:

Conditions for the existence of maximal factorizations

Extending classical algorithms for ordinary weighted or string-to-string automata to automata with underlying more general algebraic structures is of significant practical and theoretical interest. However, the generalization of classical algorithms sets certain assumptions on the underlying structure. In this respect the maximal factorization turns out to be a sufficient condition for many practical problems, e.g. minimization and canonization. Recently, an axiomatic approach on monoid structures suggested that monoids with most general equalizer (mge-monoids) provide an alternative framework to achieve similar results. In this paper, we study the fundamental relation between monoids admitting a maximal factorization and mge-monoids. We describe necessary conditions for the existence of a maximal factorization and provide sufficient conditions for an mge-monoid to admit a maximal factorization.