Tight Bounds for Complementing Parity Automata
  We follow a connection between tight determinisation and complementation and establish a complementation procedure from parity automata to nondeterministic B\"uchi automata and prove it to be tight up to an $O(n)$ factor, where $n$ is the size of the nondeterministic parity automaton. This factor does not depend on the number of priorities. 
Sven Schewe, Thomas Varghese
cs.FL