  A nondeterministic automaton is semantically deterministic (SD) if different
nondeterministic choices in the automaton lead to equivalent states. Semantic
determinism is interesting as it is a natural relaxation of determinism, and as
some applications of deterministic automata in formal methods can actually use
automata with some level of nondeterminism, tightly related to semantic
determinism.
  In the context of finite words, semantic determinism coincides with
determinism, in the sense that every pruning of an SD automaton to a
deterministic one results in an equivalent automaton. We study SD automata on
infinite words, focusing on B\"uchi, co-B\"uchi, and weak automata. We show
that there, while semantic determinism does not increase the expressive power,
the combinatorial and computational properties of SD automata are very
different from these of deterministic automata. In particular, SD B\"uchi and
co-B\"uchi automata are exponentially more succinct than deterministic ones (in
fact, also exponentially more succinct than history-deterministic automata),
their complementation involves an exponential blow up, and decision procedures
for them like universality and minimization are PSPACE-complete. For weak
automata, we show that while an SD weak automaton need not be pruned to an
equivalent deterministic one, it can be determinized to an equivalent
deterministic weak automaton with the same state space, implying also efficient
complementation and decision procedures for SD weak automata.
