A|C Seminar, 2007-01-18
Sunday, 14 January 2007 00:00

In 1957 Rabin proved monadic second order logic of two (or more) successors, S2S, decidable by reducing the problem to the (non-)emptiness problem of non-deterministic binary tree Rabin automata. One of the improvements that have since been applied to the proof involves alternating binary tree parity automata and their non-determinization. In my talk I will introduce an effective procedure to non-determinise alternating binary tree automata which can easily be extended to arbitrary alternating coalgebra automata for weak pullback preserving functors.


blog comments powered by Disqus
Last Updated on Friday, 26 September 2008 12:12