Recognisability and Algebras of Infinite Trees

Prelegent(ci)

Achim Blumensath

Afiliacja

Technische Universität Darmstadt

Termin

22 stycznia 2014 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

In this talk I give an overview of an algebraic language theory for languages of infinite trees based on algebras called omega-hyperclones. Recognisability with respect to these algebras has the same expressive power as tree automata. I also present an analogue of so-called Wilke algebras, which serve as finite presentations of omega-hyperclones. As an application of this machinery, I present a purely algebraic proof of Rabin's Tree Theorem on the decidability of monadic second-order logic over the binary tree.

---