Access Restriction

Author Drusinsky, Doron ♦ Harel, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1994
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Alternation ♦ Bounded cooperative concurrency ♦ Finite automata ♦ Nondeterminism ♦ Omega-automata ♦ Statecharts ♦ Succinctness
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 &Sgr;* and &Sgr;ω, 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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1994-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 41
Issue Number 3
Page Count 23
Starting Page 517
Ending Page 539

Open content in new tab

   Open content in new tab
Source: ACM Digital Library