Nie jesteś zalogowany | Zaloguj się

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.