Stack cooperation in multistack pushdown automata. (English) Zbl 0939.68070

Summary: The authors consider multistack pushdown automata with several strategies on the use of stacks, similar to the strategies of cooperation in grammar systems. As was to be expected, the accepting capacity of all nondeterministic variants equals the power of Turing machines. Also, all strategies in the deterministic case are equivalent. Moreover, one shows that they accept a large class of nonrecursive languages.


68Q45 Formal languages and automata
Full Text: DOI


[1] Csuhaj-Varju, E.; Dassow, J., On cooperating/distributed grammar systems, J. inf. process cybern. EIK, 26, 49-63, (1990) · Zbl 0693.68041
[2] Csuhaj-Varju, E.; Dassow, J.; Kelemen, J.; Paun, Gh., Grammar systems. A grammatical approach to distribution and cooperation, (1994), Gordon 6 Breach New York · Zbl 0925.68286
[3] Durfee, E.H., Cooperative distributed problem solving, ()
[4] Harrison, M., Introduction to formal language theory, (1978), Addison-Wesley · Zbl 0411.68058
[5] Kari, L.; Mateescu, A.; Paun, Gh.; Salomaa, A., Teams in cooperating grammar systems, J. exper. th. AI, 7, 347-359, (1995) · Zbl 0840.68071
[6] Mateescu, A.; Mitrana, V.; Salomaa, A., Dynamical teams in cooperating distributed grammar systems, Ann. univ. bucharest, mat-inform. ser., 3-14, (1993-1994)
[7] Meersman, R.; Rozenberg, G., Cooperating grammar systems, Proc MFCS ’78 symp., LNCS 64, (1978), Springer-Verlag New York/Berlin, p. 364-374 · Zbl 0387.68057
[8] Mitrana, V., Hybrid cooperating distributed grammar systems, Comput. AI, 12, 83-88, (1993)
[9] Morita, K.; Yamamoto, Y.; Nishihara, N.; Zhang, Z., A hierarchy of uniquely parsable grammar classes and deterministic acceptors, Acta inform., 34, 389-410, (1997) · Zbl 0865.68076
[10] Nii, P.H., Blackboard systems: the blackboard model of problem solving and the evolution of blackboard architectures. part I, AI mag., 38-53, (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.