You are not logged in |
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.
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.
