×

On the degree of team cooperation in CD grammar systems. (English) Zbl 1341.68068

Holzer, Markus (ed.) et al., Descriptional complexity of formal systems. 13th international workshop, DCFS 2011, Gießen/Limburg, Germany, July 25–27, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22599-4/pbk). Lecture Notes in Computer Science 6808, 68-79 (2011).
Summary: In this paper, we introduce a dynamical complexity measure, namely the degree of team cooperation, in the aim of investigating “how much” the components of a grammar system cooperate when forming a team in the process of generating terminal words. We present several results which strongly suggest that this measure is trivial in the sense that the degree of team cooperation of any language is bounded by a constant. Finally, we prove that the degree of team cooperation of a given cooperating/distributed grammar system cannot be algorithmically computed and discuss a decision problem.
For the entire collection see [Zbl 1218.68017].

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Atanasiu, A., Mitrana, V.: The modular grammars. International Journal of Computer Math. 30, 17–35 (1989) · Zbl 0683.68060 · doi:10.1080/00207168908803767
[2] ter Beek, M.H.: Teams in grammar systems: hybridity, and weak rewriting. Acta Cybernetica 12, 427–444 (1996) · Zbl 0880.68078
[3] Csuhaj-Varjú, E., Dassow, J.: On cooperating distributed grammar systems. J. Inform. Process. Cybern. EIK 26, 49–63 (1990) · Zbl 0693.68041
[4] Csuhaj-Varjú, E., Dassow, J., Kelemen, J., Păun, G.: Grammar Systems. Gordon and Breach (1994) · Zbl 0816.68080
[5] Csuhaj-Varjú, E., Păun, G.: Limiting the size of teams in cooperating grammar systems. Bulletin EATCS 51, 198–202 (1993) · Zbl 0782.68071
[6] Dassow, J., Păun, G., Rozenberg, G.: Grammar Systems. In: [14] · doi:10.1007/978-3-662-07675-0_4
[7] Kari, L., Mateescu, A., Păun, G., Salomaa, A.: Teams in cooperating grammar systems. Journal of Experimental & Theoretical Artificial Intelligence 7, 347–359 (1995) · Zbl 0840.68071 · doi:10.1080/09528139508953816
[8] Meersman, R., Rozenberg, G.: Cooperating grammar systems. In: Winkowski, J. (ed.) MFCS 1978. LNCS, vol. 64, pp. 364–374. Springer, Heidelberg (1978) · Zbl 0387.68057 · doi:10.1007/3-540-08921-7_84
[9] Mateescu, A., Mitrana, V., Salomaa, A.: Dynamical teams in cooperating distributed grammar systems. Ann. Univ. of Bucharest, 3–14 (1993-1994) · Zbl 0823.68052
[10] Nii, P.H.: Blackboard systems. In: Barr, A., Cohen, P.R., Feigenbaum, E.A. (eds.) The Handbook of AI, vol. 4. Addison-Wesley, London (1989)
[11] Păun, G., Rozenberg, G.: Prescribed teams of grammars. Acta Informatica 31, 525–537 (1994) · Zbl 0818.68104 · doi:10.1007/BF01213205
[12] Penttonen, M.: ET0L-grammars and N-grammars. Inform. Proc. Letters 4, 11–13 (1975) · Zbl 0312.68045 · doi:10.1016/0020-0190(75)90052-6
[13] Rozenberg, G., Vermeir, D.: On the relationships between context-free programmed grammars and ET0L systems. Fundamenta Informaticae 1, 325–345 (1978) · Zbl 0386.68069
[14] Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. I-III. Springer, Berlin (1997) · Zbl 0866.68057
[15] von Solms, S.H.: On T0L languages over terminals. Inform. Proc. Letters 3, 69–70 (1975) · Zbl 0294.68026 · doi:10.1016/0020-0190(75)90017-4
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.