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

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

Oct. 5, 2016, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---