On the power of bounded concurrency II: pushdown automata

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 unlimited savings in succinctness in all cases.

REFERENCES

• 1: Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
• 2: Doron Drusinsky , David Harel, On the power of bounded concurrency I: finite automata, Journal of the ACM (JACM), v.41 n.3, p.517-539, May 1994 [doi>10.1145/176584.176587]
• 3: ~GLOBERMAN, N., AND HAREL, D. 1994. On the succinctness and logic of multi-pebble automata. ~In Proceedings of the 21st International Colloqmum on Automata, Languages, and Programming. ~Lecture Notes in Computer Science, Springer-Verlag, New York, to appear.
• 4: David Harel, Statecharts: A visual formalism for complex systems, Science of Computer Programming, v.8 n.3, p.231-274, June 1, 1987 [doi>10.1016/0167-6423(87)90035-9 ]
• 5: ~HAREL, D., ROSNER, R., AND VARDI, M. 1990. On the power of bounded concurrency III: ~Reasoning about programs. In Proceedings of the 5th Symposium on Logic m Computer Sczence. ~IEEE Press, New York, pp. 479-488.
• 6: M.A. A. Harrison , M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 7: ~HIRST, T. 1989. Succinctness results for statecharts. M.Sc. dissertation. Bar-Ilan Univ., Ramat ~Gan, Israel (in Hebrew).
• 8: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 9: ~LADNER, R E., LIPTON, R. J., AND STOCKME~'ER, L. J. 1984. Alternating pushdown and stack ~automata. SIAM J Comput. 13, 135-155.
• 10: ~MEYER, A. R., AND FISCHER, M. J. 1971. Economy of description by automata, grammars, and ~formal systems. In Procee&ngs of the 12th IEEE &'mposutm on Switchttzg and Automata Theory ~IEEE Press, New York, pp. 188-191.
• 11: R. Milner, A Calculus of Communicating Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1982
• 12: Rohit J. Parikh, On Context-Free Languages, Journal of the ACM (JACM), v.13 n.4, p.570-581, Oct. 1966 [doi>10.1145/321356.321364]
• 13: Wolfgang Reisig, Petri nets: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism

General Terms:
Theory

Keywords:
cooperative concurrency, pushdown automata, succinctness