Data monoids

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

April 28, 2010, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---