ON THE POWER OF BOUNDED CONCURRENCY .1. FINITE AUTOMATA

We investigate the descriptive succinctness of three fundamental notions for modeling concurrency: nondeterminism and pure parallelism, the two facets of alternation, and bounded cooperative concurrency, whereby a system configuration consists of a bounded number of cooperating states. Our results are couched in the general framework of finite-state automata, but hold for appropriate versions of most concurrent models of computation, such as Petri nets, statecharts or finite-state versions of concurrent programming languages. We exhibit exhaustive sets of upper and lower bounds on the relative succinctness of these features over SIGMA* and SIGMA(omega), establishing that: (1) Each of the three features represents an exponential saving in succinctness of the representation, in a manner that is independent of the other two and additive with respect to them. (2) Of the three, bounded concurrency is the strongest, representing a similar exponential saving even when substituted for each of the others. For example, we prove exponential upper and lower bounds on the simulation of deterministic concurrent automata by AFAs, and triple-exponential bounds on the simulation of alternating concurrent automata by DFAs.