You are not logged in | Log in

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.