ON THE POWER OF BOUNDED CONCURRENCY .1. FINITE AUTOMATA

We investigate the descriptive succinctness of three fundamental notio ns for modeling concurrency: nondeterminism and pure parallelism, the two facets of alternation, and bounded cooperative concurrency, whereb y a system configuration consists of a bounded number of cooperating s tates. Our results are couched in the general framework of finite-stat e automata, but hold for appropriate versions of most concurrent model s of computation, such as Petri nets, statecharts or finite-state vers ions of concurrent programming languages. We exhibit exhaustive sets o f upper and lower bounds on the relative succinctness of these feature s over SIGMA and SIGMA(omega), establishing that: (1) Each of the thr ee features represents an exponential saving in succinctness of the re presentation, in a manner that is independent of the other two and add itive with respect to them. (2) Of the three, bounded concurrency is t he strongest, representing a similar exponential saving even when subs tituted for each of the others. For example, we prove exponential uppe r and lower bounds on the simulation of deterministic concurrent autom ata by AFAs, and triple-exponential bounds on the simulation of altern ating concurrent automata by DFAs.