On the Capacity of Capacitated Automata
=======================================

Capacitated automata (CAs) have been recently introduced in [KT14] as
a variant of finite-state automata in which each transition is
associated with a (possibly infinite) capacity. The capacity bounds
the number of times the transition may be traversed in a single run.

The study in [KT14] includes preliminary results about the expressive
power of CAs, their succinctness, and the complexity of basic decision
problems for them.  We continue the investigation of the theoretical
properties of CAs and solve problems that have been left open in
[KT14]. In particular, we show that union and intersection of CAs
involve an exponential blow-up and that their determinization involves
a doubly-exponential blow up. This blow-up is carried over to
complementation and to the complexity of the universality and
containment problems, which we show to be EXPSPACE-complete. On the
positive side, capacities do not increase the complexity when used in
the deterministic setting. Also, the containment problem for
nondeterministic CAs is PSPACE-complete when capacities are used only
in the left-hand side automaton. Our results suggest that while the
succinctness of CAs leads to a corresponding increase in the
complexity of some of their decision problems, there are also settings
in which succinctness comes at no price.