Minimisation of automata over data words

Prelegent(ci)

Sławomir Lasota

Afiliacja

Uniwersytet Warszawski

Termin

1 grudnia 2010 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

(a joint work with Mikołaj Bojańczyk and Bartek Klin)

 

I will state and prove an analog of the Myhill-Nerode
theorem for register automata. The difficulty comes from
the fact that the input alphabet contains data values and
is thus infinite. We have found and elegant way to overcome
the difficulty, using so called nominal sets, i.e., finite sets
"up to permutation of data". The nominal approach seems to
be very robustly usable in many other contexts; I will sketch
some potential further lines of work.

---