Tight Bounds for Complementing Parity Automata
arXiv:1406.1090 · doi:10.1007/978-3-662-44522-8_42
Abstract
We follow a connection between tight determinisation and complementation and establish a complementation procedure from parity automata to nondeterministic Büchi automata and prove it to be tight up to an factor, where is the size of the nondeterministic parity automaton. This factor does not depend on the number of priorities.
Full version of paper accepted for publication at MFCS 2014