Nondeterminism in the Presence of a Diverse or Unknown Future 
=============================================================

Choices made by nondeterministic word automata depend on both the past
(the prefix of the word read so far) and the future (the suffix yet to
be read). In several applications, most notably synthesis, the future
is diverse or unknown, leading to algorithms that are based on
deterministic automata. Hoping to retain some of the advantages of
nondeterministic automata, researchers have studied restricted classes
of nondeterministic automata. Three such classes are nondeterministic
automata that are {\em good for trees} (GFT; i.e., ones that can be
expanded to tree automata accepting the derived tree languages, thus
whose choices should satisfy diverse futures), {\em good for games}
(GFG; i.e., ones whose choices depend only on the past), and {\em
determinizable by pruning} (DBP; i.e., ones that embody equivalent
deterministic automata). The theoretical properties and relative
merits of the different classes are still open, having vagueness on
whether they really differ from deterministic automata. In particular,
while DBP $\subseteq$ GFG \subseteq GFT, it is not known whether every
GFT automaton is GFG and whether every GFG automaton is DBP. Also open
is the possible succinctness of GFG and GFT automata compared to
deterministic automata. We study these problems for \omega-regular
automata with all common acceptance conditions. We show that GFT = GFG
\supset DBP, and describe a determinization construction for GFG
automata.