Thomas Colcombet's deterministic version of Simon's decomposition theorem

Prelegent(ci)

Aymeric Vincent

Afiliacja

Uniwersytet Warszawski

Termin

4 czerwca 2008 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

In this presentation, we will introduce Simon's decomposition theorem and give an outline of the proof given by Thomas Colcombet. We will then concentrate on a weaker version of the theorem which has the advantage of being "deterministic" in the sense that the decomposition of any prefix of a word does not depend on its suffix. The work of Thomas was published in 2007 at FCT and ICALP, but we follow his research report containing the proofs "On Factorization Forests", also from 2007.

---