Recognisability and Algebras of Infinite Trees

Speaker(s)

Achim Blumensath

Affiliation

Technische Universität Darmstadt

Date

Jan. 22, 2014, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---