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

Speaker(s)

Aymeric Vincent

Affiliation

Uniwersytet Warszawski

Date

June 4, 2008, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---