Ramsey Theorems for Compact Colors. Joint work with Eryk Kopczyński and Szymon Toruńczyk

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

Jan. 5, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

When applied to omega-words, the Ramsey Theorem says the following. Suppose that finite factors (=infixes) of an omega-word are colored by a finite number of colors. Then one factorize a suffix of the omega-word so that every finite union of consecutive factors has the same color. I will present a variant of the theorem where there are infinitely many colors, but they form a compact metric space. Then I will present a tree variant of the theorem. These results are useful when working with automata with counters.

---