Algorithm computing Simon decomposition in polynomial time

Prelegent(ci)

Paweł Parys

Afiliacja

Uniwersytet Warszawski

Termin

18 listopada 2009 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---