Automata with group actions

Prelegent(ci)

Sławomir Lasota

Afiliacja

Uniwersytet Warszawski

Termin

9 marca 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---