Trade-Offs Between Time, Space, Cooperation, and Communication Complexity for CD Grammar Systems

• Autorzy: Cojocaru L.
• Języki publikacji: EN

Abstrakty

EN

In this paper we investigate the communication and cooperation phenomenon in Cooperating Distributed Grammar Systems (henceforth CDGSs). In this respect, we define several complexity structures and two complexity measures, the cooperation and communication complexity measures. These measures are studied with respect to the derivation modes and fairness conditions under which CDGSs may work. We deal with trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with regular, linear, and context-free components. Cooperation and communication processes in CDGSs with regular and linear components are of equal complexity. The two (equal) cooperation and communication complexity measures are either constant or linear, as functions of lengths of words in the generated language. The same result holds for the cooperation and communication complexity of q-fair languages generated by CDGSs with regular and linear components. For the case of non-constant communication (cooperation) the time and space used by a nondeterministicmultitape Turingmachine to recognizeweakly q-fair languages are linear, as is the communication (cooperation) complexity. For CDGSs with context-free components the cooperation and communication complexity may be different. These measures are either linear or logarithmic functions, in terms of lengths of words in the generated language. In order to find trade-offs between time, space, cooperation, and communication complexity of languages generated by CDGSs with context-free components we study asymptotic behavior of growth functions characteristic to these measures. We prove that languages generated by CDGSs with context-free components are accepted by nondeterministicmultitape Turing machines either in quadratic time, linear space, and with cooperation complexity that varies from logarithmic to linear, or in polynomial or exponential time and space, and linear cooperation complexity.

Słowa kluczowe

EN

CDGSs; q-fair languages; szilard languages; turing machines; cooperation and communication complexity; time and space complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 107, nr 4
• Strony: 345--378
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Cojocaru L.

• Department of Computer Sciences, University of Tampere Kanslerinrinne 1, FIN-33014, Tampere, Finland,

Bibliografia

• [1] Chandra, A. K., Furst, M. L., Lipton, R. J.: Multiparty Protocols, Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC), 1983, 94-99.
• [2] Cojocaru, L.: On the Time, Space, and Communication Complexity of CDGSs, Proceedings of Grammar Systems Week 2004 (E. Csuhaj-Varj´u, Gy. Vaszil, Eds.), Budapest, Hungary, 2004, 101-113.
• [3] Cojocaru, L.: On the Time, Space, and Communication Complexity of q-fair Languages, Proceedings of the 6th Descriptional Complexity of Formal Systems Workshop, London, Ontario, Canada, 2004, 154-163.
• [4] Csuhaj-Varju, E., Dassow, J.: On Cooperating Distributed Grammar Systems, Journal of Information Processing and Cybernetics (EIK), 26(1-2), 1990, 49-63.
• [5] Csuhaj-Varju, E., Kelemen, J.: Cooperating Grammar Systems: A Syntactical Framework for the Blackboard Model of Problem Solving, Proceedings Artificial Intelligence and Information-Control Systems of Robots '89 (I. Plander, Ed.), North-Holland, Amsterdam, 1989, 121-127.
• [6] Csuhaj-Varju, E., Dassow, J., Kelemen, J., Pǎun, Gh.: Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, Yverdon, 1994.
• [7] Dassow, J., Mitrana, V.: Fairness in Grammar Systems, Acta Cybernetica, 12(4), 1996, 331-346.
• [8] Dassow, J., Mitrana, V., Pǎun, Gh.: Szilard Languages Associated to Cooperating Distributed Grammar Systems, Studii s¸i Cercetari Matematice, 45, 1993, 403-413.
• [9] Dassow J., Pǎun, Gh.: Regulated Rewriting in Formal Language Theory, Springer-Verlag Berlin, 1989.
• [10] Hromkoviǎ, J.: Relation Between Chomsky Hierarchy and Communication Complexity Hierarchy, Acta Mathematica, Universitatis Comenianae, 48-49, 1986, 311-317.
• [11] Hromkovič, J., Kari, J., Kari, L., Pardubská, D.: Two Lower Bounds on Distributive Generation of Languages, Fundamenta Informaticae, 25(3), 1996, 271-284.
• [12] Hromkovič, J., Kari, J., Kari, L.: Some Hierarchies for the Communication Complexity Measures of Cooperating Grammar Systems, Theoretical Computer Science, 127(1), 1994, 123-147.
• [13] Hromkovič, J.: Communication Complexity and Parallel Computing, Springer-Verlag Berlin, 1997.
• [14] Jirásková, G.: Chomsky Hierarchy and Communication Complexity, Journal of Information Processing and Cybernetics (EIK) 25(4), 1989, 157-164.
• [15] Jirásková, G.: Note onMinimal Automata and Uniform Communication Protocols, Grammars and Automata for String Processing (C. Martin-Vide, V. Mitrana, Eds.), Taylor&Francis Inc., London, 2003, 163-170.
• [16] Kushilevitz, E., Nisan, N.: Communication Complexity, Cambridge University Press, 1997.
• [17] Meersman, R., Rozenberg, G.: Cooperating Grammar Systems, Proceedings of the 7th Mathematical Foundations of Computer Science Symposium, LNCS 64, Springer-Verlag Berlin, 1978, 364-374.
• [18] Meersman, R., Rozenberg, G., Vermeir, D.: Cooperating Grammar Systems, Technical Report 78-12, University of Antwerp, Department of Mathematics, 1978.
• [19] Mihalache, V.: Cooperation, Communication, Control: Investigations on Grammar Systems, TUCS Dissertations, No. 9, June 1998, Turku Centre for Computer Science, 1998.
• [20] Mihalache, V.: Decidability Problems in Grammar Systems, Theoretical Computer Science, 215(1-2), 1999, 169-189.
• [21] Nisan, N., Wigderson, A.: Rounds in Communication Complexity Revisited, SIAM Journal on Computing, 22(1), 1993, 211-219.
• [22] Pardubská, D.: On the Power of Communication Structure for Distributed Generation of languages, Developments in Language Theory, At the Crossroads of Mathematics, Computer Science and Biology (G. Rozenberg, A. Salomaa, Eds.),World Scientific, Singapore, 1994, 419-429.
• [23] Pardubská, D.: The CommunicationComplexity Hierarchy of Parallel Communicating Systems, Proceedings of IMYC'92, 1992.
• [24] Pǎun, Gh.: Parallel Communicating Grammar Systems: Recent Results, Open Problems, Acta Cybernetica, 12(4), 1996, 381-396.
• [25] Purdom, P. W., Brown, A. C.: The Analysis of Algorithms, Oxford University Press, 1995.
• [26] Rozenberg G., Salomaa, A.: The Mathematical Theory of L Systems, Academic Press, Inc., London, 1980.
• [27] Sudkamp, I.: Languages andMachines, An Introduction to the Theory of Computer Science, Addison-Wesley, 1997.
• [28] Yao, A. C.: Some Complexity Questions Related to Distributed Computing, Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC), 1979, 209-213.