### On the power of bounded concurrency II: pushdown automataOn the power of bounded concurrency II: pushdown automata

Access Restriction
Subscribed

 Author Hirst, Tirza ♦ 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 Cooperative concurrency ♦ Pushdown automata ♦ Succinctness Abstract This is the second in a series of papers on the inherent power of bounded cooperative concurrency, whereby an automaton can be in some bounded number of states that cooperate in accepting the input. In this paper, we consider pushdown automata. We are interested in differences in power of expression and in exponential (or higher) discrepancies in succinctness between variants of pda's that incorporate nondeterminism (E), pure parallelism (A), and bounded cooperative concurrency (C). Technically, the results are proved for cooperating push-down automata with cooperating states, but they hold for appropriate versions of most concurrent models of computation. We exhibit exhaustive sets of upper and lower bounds on the relative succinctness of these features for three classes of languages: deterministic context-free, regular, and finite. For example, we show that C represents exponential savings in succinctness in all cases except when both E and A are present (i.e., except for alternating automata), and that E and A represent $\textit{unlimited}$ savings in succinctness in all cases. 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 15 Starting Page 540 Ending Page 554

#### Open content in new tab

Source: ACM Digital Library