摘要：Different types of automata over words and trees offer different trade-offs between expressivity, conciseness, and the complexity of decision procedures. Alternating weak automata enjoy simple algorithms for emptiness and membership checks, which makes transformations into automata of this type particularly interesting. For instance, an algorithm for solving two-player infinite games can be viewed as a special case of such a transformation. However, our understanding of the worst-case size blow-up that these transformations can incur is rather poor. This paper establishes two new results, one on word automata and one on tree automata. We show that: - Alternating parity word automata can be turned into alternating weak automata of quasi-polynomial (rather than exponential) size. - Universal co-Büchi tree automata, a special case of alternating parity tree automata, can be exponentially more concise than alternating weak automata. Along the way, we present a family of game languages, strict for the levels of the weak hierarchy of tree automata, which corresponds to a weak version of the canonical game languages known to be strict for the Mostowski - Rabin index hierarchy.
