An algebraic proof of Rabin%26apos;s Tree Theorem

作者：Blumensath Achim^*

来源：Theoretical Computer Science, 2013, 478: 1-21.

DOI：10.1016/j.tcs.2013.01.026

• Monadic second-order logic
• Infinite trees
• Recognisability

We continue the development of a theory of recognisability for infinite trees by introducing the equivalent of a Wilke algebra. As an application we give a new proof of the decidability of the monadic second-order theory of the infinite binary tree, a proof that does not use automata or games.

• 出版日期2013-3-25