Existential and universal width of alternating finite automata

The existential width of an alternating finite automaton (AFA) A on a string w is, roughly speaking, the number of nondeterministic choices that A uses in an accepting computation on w that uses least nondeterminism. The universal width of A on string w is the least number of parallel branches an accepting computation of A on w needs to have. The existential or universal width of A is said to be finite if it is bounded for all accepted strings. We show that finiteness of existential and universal width of an AFA is decidable and at least PSPACE-hard. We consider the problem of deciding whether the existential or universal width is bounded by a given integer. We show that the problem is PSPACE-complete for AFAs where the number of transitions defined for a given universal state and input symbol is bounded by a constant.