On Cooperating Distributed Grammar Systems with Competence Based Start and Stop Conditions

• Autorzy: Dassow J.
• Języki publikacji: EN

Abstrakty

EN

We define cooperating distributed grammar systems with start and stop conditions which are based on the competence of a component on the current sentential form. We distinguish six different types of competence conditions which result in 18 types of grammar systems. We summarize the results on the generative power known from the literature (where they are sometimes not related to competence) and determine the power of some further grammar systems.

Słowa kluczowe

EN

cooperating distributed grammar systems; grammars with controlled derivations; ETOL systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 76, nr 3
• Strony: 293--304
• Opis fizyczny: bibliogr. 18 poz.

Twórcy

autor

Dassow J.

• Fakultät für Informatik, Otto-von-Guericke-Universitätt Magdeburg, Postfach 4120, D-39016 Magdeburg, Germany,

Bibliografia

• [1] M. ter Beek, E. Csuhaj-Varjú, M. Holzer, Gy. Vaszil: On competence in cooperating distributed grammar systems, Technical Report, 2002/1, Research Group on Modelling Multi-Agent Systems, Computer and Automation Research Institute, Hungarian Academy of Sciences, 2002.
• [2] M. ter Beek, E. Csuhaj-Varjú, M. Holzer, Gy. Vaszil: On competence in cooperating distributed grammar systems, part II., Technical Report 2002/2, Research Group on Modelling Multi-Agent Systems, Computer and Automation Research Institute, Hungarian Academy of Sciences, 2002.
• [3] M. ter Beek, E. Csuhaj-Varjú, M. Holzer, Gy. Vaszil: On competence in cooperating distributed grammar systems, part III., Technical Report, 2002/3, Research Group on Modelling Multi-Agent Systems, Computer and Automation Research Institute, Hungarian Academy of Sciences, 2002.
• [4] M. ter Beek, E. Csuhaj-Varjú,M. Holzer, Gy. Vaszil: On competence in cooperating distributed grammar systems, Developments in Language Theory: 8th International Conference, DLT 2004. Auckland, New Zealand, December 13-17. Proceedings (C. S. Calude, E. Calude, and M. J. Dinneen, Eds.), Volume 3340 of Lecture Notes in Computer Science, Springer-Verlag, Berlin-Heidelberg, 2004, 76-88.
• [5] H. Bordihn: On the number of components in CD grammar systems, Descriptional Complexity of Formal Systems, 5th International Workshop, Budapest, Hungary, July 12-14, 2003, Proceedings. (E. Csuhaj-Varjú, C. Kintala, D. Wotschke, and Gy. Vaszil, Eds.), Budapest. MTA-SZTAKI, 2003.
• [6] H. Bordihn, E. Csuhaj-Varjú: On competence and completeness in CD grammar systems. Acta Cybernetica, 12, 1996, 347-361.
• [7] E. Csuhaj-Varjú, J. Dassow: On cooperating/distributed grammar systems. Journal of Information Processing and Cybernetics (EIK), 26, 1990, 49-63.
• [8] E. Csuhaj-Varjú, J. Dassow, M. Holzer: On a competence-based cooperation strategy in CD grammar systems, submitted, 2004.
• [9] E. Csuhaj-Varjú, J. Dassow, M. Holzer: CD grammar systems with competence based entry conditions in their cooperation protocols, submitted, 2004.
• [10] E. Csuhaj-Varjú, J. Dassow, J. Kelemen, Gh. P˘aun: Grammar Systems - A Grammatical Approach to Distribution and Cooperation, Topics in Computer Mathematics 5, Gordon and Breach Science Publishers, Yverdon, 1994.
• [11] J. Dassow, Gh. Pǎun: Regulated Rewriting in Formal Language Theory, EATCS Monograph on Theoretical Computer Scince 18, Springer-Verlag, Berlin-Heidelberg-New York, 1989.
• [12] J. Dassow, Gh. Pǎun, G. Rozenberg: Grammar systems, in [18], Vol. II, Chapter 4, 155-213.
• [13] J. Dassow, Gh. Pǎun, A. Salomaa: Grammar with controlled derivations, in: [18], Vol. II, Chapter 3, 101-154.
• [14] H. Fernau, M. Holzer, R. Freund: Hybrid modes in cooperating distributed grammar systems: internal versus external hybridization, Theoretical Computer Science, 259, 2001, 404-426.
• [15] R. Meersman, G. Rozenberg: Cooperating grammar systems, Proceedings Mathematical Foundations of Computer Science 1978 (J.Winkowski, Ed.), Lecture Notes in Computer Science 64, Springer-Verlag, Berlin, 1978, 364-374.
• [16] V. Mitrana: Hybrid coooperating/distributed grammar systems, Computers and Artificial Intelligence, 12, 1993, 83-88.
• [17] G. Rozenberg, A. Salomaa: The Mathematical Theory of L Systems, Academic Press, New York, 1980.
• [18] G. Rozenberg, A. Salomaa, Eds.: Handbook of Formal Languages. Vol. I - III, Springer Verlag, Berlin-Heidelberg-New York, 1997.