Data monoids

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

28 kwietnia 2010 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

A data monoid is like a monoid, but it is used to recognize languages
of data words, and not languages of words over finite alphabets. I
will say what kind of languages of data words can be recognized by
data monoids (not many), and how much of finite monoid theory extends
to data monoids (a lot). I will talk about the following theorem: for
a language of data words recognized by an orbit finite data monoid,
aperiodicity is equivalent to definability in first-order logic.

---