  While weighted automata provide a natural framework to express quantitative
properties, many basic properties like average response time cannot be
expressed with weighted automata. Nested weighted automata extend weighted
automata and consist of a master automaton and a set of slave automata that are
invoked by the master automaton. Nested weighted automata are strictly more
expressive than weighted automata (e.g., average response time can be expressed
with nested weighted automata), but the basic decision questions have higher
complexity (e.g., for deterministic automata, the emptiness question for nested
weighted automata is PSPACE-hard, whereas the corresponding complexity for
weighted automata is PTIME). We consider a natural subclass of nested weighted
automata where at any point at most a bounded number k of slave automata can be
active. We focus on automata whose master value function is the limit average.
We show that these nested weighted automata with bounded width are strictly
more expressive than weighted automata (e.g., average response time with no
overlapping requests can be expressed with bound k=1, but not with non-nested
weighted automata). We show that the complexity of the basic decision problems
(i.e., emptiness and universality) for the subclass with k constant matches the
complexity for weighted automata. Moreover, when k is part of the input given
in unary we establish PSPACE-completeness.
