Minimisation of automata over data words

Speaker(s)

Sławomir Lasota

Affiliation

Uniwersytet Warszawski

Date

Dec. 1, 2010, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

(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.

---