*For the most recent entries see the
Petri Nets Newsletter.*

## On the power of bounded concurrency. 1. Finite automata.

Drusinsky, D.;
Harel, D.
In:
*Journal of the ACM, Vol. 41, No. 3*, pages 517-539.
1994.

Abstract:
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.

Keywords:
Petri nets, bounded concurrency, concurrent automata, statecharts.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*