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

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

5 stycznia 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---