| 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. |
| LAST_UPDATED2 |