Nie jesteś zalogowany |
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.
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.
