An algebraic proof of Rabin's tree theorem (Q1951555)

The algebraic theory of languages emerged from the result of [\textit{M. O. Rabin} and \textit{D. Scott}, in: Sequential Machines, select. Papers 63--91 (1964), Nachdruck von IBM J. Res. Develop. 3, 114--125 (1962; Zbl 0158.25404)] (credited to Myhill) that a set of finite words is recognizable by a finite automaton exactly when its so-called \textit{syntactic monoid} is finite. This characterization allows to replace a machine model, the finite automaton, by an algebraic structure, the syntactic monoid. This approach not only allows the use of algebraic methods in automata theory, but also can yield decision procedures for inclusion in some language classes. For instance, [\textit{M. P. Schützenberger}, Inf. Control 8, 190--194 (1965; Zbl 0131.02001)] characterizes star-free languages as those having a finite and aperiodic syntactic monoid. Inclusion in the class of star-free languages can hence be effectively determined by constructing the syntactic monoid and then checking that it is indeed aperiodic. The paper under review further develops the author's algebraic approach to recognizability for languages of infinite trees [Theor. Comput. Sci. 412, No. 29, 3463--3486 (2011; Zbl 1233.68159)]. The main result is to show that the algebras introduced in [Zbl 1233.68159], the \textit{path-continuous \(\omega\)-hyperclones} are finitely presentable. To show finite presentation, the author uses the result of [Zbl 0158.25404], which offers a tree analogue to Ramsey's Theorem. As an application, a new proof of Rabin's Tree Theorem, which shows that the monadic second-order theory of the infinite complete binary tree is decidable, is given.