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.

Add a comment
Last Updated on Friday, 26 September 2008 12:12
 
<< Start < Prev 1 2 3 Next > End >>

Page 3 of 3