A non-regular language of infinite trees that is recognised by a finitary algebra

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

5 października 2016 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

I will present an example, resulting from joint work with Bartek Klin. One natural approach to algebras for infinite trees is to use an algebra which has infinitely many sorts {0,1,2,..}, where sort n represents trees with n ports (a port can be used multiple times, possibly infinitely often). Some people call this an \omega-clone. The example will show that there is a language that is not regular, but is recognised by an \omega-clone which has finitely many elements on every sort.

---