A|C Seminar, 2007-01-18
Sunday, 14 January 2007 00:00
There are no translations available.

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_UPDATED2