On the power of bounded concurrency I: Finite Automata

Abstract. We investigate the descriptive succinctness of three fundamental notions for modeling concurrency: nondeterminism and pure parallelism, the two facets of alternation, and bounded cooperatu)e 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 X * and X@, establishing that: (1) Each of thethree features represents anexponential saving insuccinctness of the representa-tion, in a manner that is independent of the other two and additive with respect to them. (2) Ofthethree, bounded concurrency isthestrongest, representing asimilar 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