Automata with group actions

Speaker(s)

Sławomir Lasota

Affiliation

Uniwersytet Warszawski

Date

March 9, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Our motivating question is a Myhill-Nerode theorem for infinite
alphabets. We consider several kinds of those: alphabets whose letters
can be compared only for equality, but also ones with more structure,
such as a total order or a partial order. We develop a framework for
studying such alphabets, where the key role is played by the
automorphism group of  the alphabet. This framework builds on the idea
of nominal sets of Gabbay and Pitts; nominal sets are  the special
case of our framework where letters can be only compared for
equality. We use the framework to uniformly generalize to infinite
alphabets parts of automata theory, including decidability results. In
the case of letters compared for equality, we obtain automata
equivalent in expressive power to finite memory automata, as defined
by Francez and Kaminski.

---