Computation Width and Deviation Number

The computation width (a.k.a. tree width, a.k.a. leaf size) of a nondeterministic finite automaton (NFA) A counts the number of branches in the computation tree of A on a given input. The deviation number of A on a given input counts the number of nondeterministic paths that branch out from the best accepting computation. Deviation number is a best-case nondeterminism measure closely related to the guessing measure of Goldstine, Kintala and Wotschke (Infrom. Comput. 86, 1990, 179–194). We consider the descriptional complexity of NFAs with similar given deviation number and with computation width.