Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving, Revisited

• Autorzy: Bordihn H. , Holzer M.
• Języki publikacji: EN

Abstrakty

EN

Based on a derivation mode f for cooperating distributed (CD) grammar systems, we introduce a new form of cooperation protocol, the so called "cut-f-mode" of derivation. Intuitively, in the cut-f-mode of derivation the sentential form is partitioned (cut) into several subwords, where some of these subwords are distributed to the components, which derive them according to the underlying f-mode of derivation, and finally the new sentential form is obtained by concatenating all the subwords-derived or not-in their original order. According to the original motivation from distributed artificial intelligence, the new functioning mode appears to be more realistic than the original model. We investigate the cut-mode versions of the basic derivation modes and some of their combined versions. It turns out that in most cases, the cut-f-mode is at most as powerful as the corresponding non-cut-mode, that is, the f-mode itself. In some cases the power is even reduced to that of context-free grammars.

Słowa kluczowe

EN

cooperating distributed grammar systems; derivation modes; regulated rewriting; programmed grammars; finite index restriction; Lindenmayer systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 3
• Strony: 255--270
• Opis fizyczny: bibliogr. 15 poz.

Twórcy

autor

Bordihn H.

autor

Holzer M.

• Universität Potsdam, Institut für Informatik, August-Bebel-Strasse 89, 14482 Potsdam, Germany,

Bibliografia

• [1] Bordihn, H., Csuhaj-Varjú, E., Dassow, J.: CD grammar systems versus L systems, in: Grammatical Models of Multi Agent Systems (Gh. P˘aun, A. Salomaa, Eds.), Gordon and Breach, 1999, 18-32.
• [2] Bordihn, H., Holzer, M.: Grammar systems with negated conditions in their cooperation protocols, Journal of Universal Computer Science, 6, 2000, 1165-1184.
• [3] Csuhaj-Varjú, E., Dassow, J.: On cooperating/distributed grammar systems, J. Inf. Process. Cybern. EIK (formerly Elektron. Inf.verarb. Kybern.), 26(1/2), 1990, 49-63.
• [4] Csuhaj-Varjú, E., Dassow, J., Kelemen, J., Pǎun, Gh.: Grammar Systems: A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, 1994.
• [5] Dassow, J., Pǎun, Gh.: Regulated Rewriting in Formal Language Theory, Springer, 1989.
• [6] Dassow, J., Pǎun, Gh., Rozenberg, G.: Grammar systems, in: Handbook of Formal Languages, volume 2, (G. Rozenberg, A. Salomaa, Eds.), Springer, 1997, 155-213.
• [7] Fernau, H., Freund, R., Holzer, M.: Hybrid modes in cooperating distributed grammar systems: internal versus external hybridization, Theoretical Computer Science, 259(1-2), 405-426.
• [8] Fernau, H., Holzer, M.: Regulated finite index language families collapse, Technical Report WSI-96-16, Universität Tübingen (Germany), Wilhelm-Schickard-Institut für Informatik, 1996.
• [9] Fernau, H., Holzer, M., Freund, R.: Bounding resources in cooperating distributed grammar systems, in:Proc. of the 3rd Int. Conf. Developments in Language Theory, (S. Bozapalidis, Ed.), Aristotle University of Thessaloniki, 1997, 261-272.
• [10] Meersman, R., Rozenberg, G.: Cooperating grammar systems, in: Proceedings of Mathematical Foundations of Computer Science MFCS'78, LNCS 64, Springer, 1978, 364-374.
• [11] Nii, P. H.: Blackboard systems, in: The Handbook of Artificial Intelligence IV, Addison-Wesley, 1989, 1-82.
• [12] Mitrana, V.: Hybrid cooperating/distributed grammar systems, Computers and Artificial Intelligence, 12(1), 1993, 83-88.
• [13] Rosenkrantz, D. J.: Programmed grammars and classes of formal languages, Journal of the ACM, 16(1), 1969, 107-131.
• [14] Rozoy, B.: The Dyck language D0_1 is not generated by any matrix grammar of finite index, Information and Computation (formerly Information and Control), 74, 1987, 64-89.
• [15] von Solms, S. H.: Some notes on ET0L-languages. International Journal of Computer Mathematics, 5(A), 1976, 285-296.