Algorithm computing Simon decomposition in polynomial time

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

Nov. 18, 2009, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---