Algorithm computing Simon decomposition in polynomial time

Simon decomposition is a very important tool in the finite monoid theory. I will present a new, efficient construction of the Simon decomposition. All previous constructions were starting from a finite monoid. When we have a finite automaton on input, it was first needed to transform it into a monoid, which was causing exponential blowup. Our construction works in time polynomial in the size of an automaton, since monoids are used only implicitly. The construction has some implications in efficient XPath processing.