On the synchronization in parallel communicating grammar systems
Tóm tắt
We investigate the power of various types of synchronization in parallel communicating grammar systems. Systems without a universal clock (a pumping lemma is given for this case) proves in general to be weaker than the synchronized systems. Further synchronizing restrictions are introduced (added to the basic synchronization by a universal clock and their effect on the generative capacity of grammar systems is examined.
Tài liệu tham khảo
Csuhaj-Varju, E., Dassow, J.: On cooperating/distributed grammar systems. J. Inf. Process. Cybern. EIK26, 49–63 (1990)
Dassow, J., Kelemen, J.: Cooperating/distributed grammar systems: a link between formal languages and artificial intelligence. Bull. EATCS45, 131–145 (1991)
Dassow, J., Păun, Gh.: Regulated Rewriting in Formal Language Theory. Berlin Heidelberg New York: Springer 1989
Ibarra, O.: Simple matrix languages. Inf. Control17, 359–394 (1970)
Kari, J., Santean, L.: The impact of the number of cooperating grammars on the generative power. Theor. Comput. Sci.98, 621–633 (1992)
Meersman, R., Rozenberg, G.: Cooperating grammar systems. Proceedings MFCS '78 Symposium. (Lect. Notes Comput. Sci., vol. 64, pp. 364–374) Berlin Heidelberg New York: Springer 1978
Nii, P.H.: Blackboard systems. In: Barr, A., Cohen, P.R., Feigenbaum, E.A. (eds.) The handbook of artificial intelligence, vol. 4. Reading, Mass.: Addison-Wesley 1989
Păun, Gh.: On the power of synchronization in parallel communicating grammar systems. Stud. Cercet. Matem.41, 191–197 (1989)
Păun, Gh.: On the syntactic complexity of parallel communicating grammar systems. Kybernetika28, 155–166 (1992)
Păun, Gh. Santean, L.: Parallel communicating grammar systems: the regular case. Ann. Univ. Buc., Ser. Matem.-Inform.38, 55–63 (1989)
Păun, Gh., Salomaa, A., Vicolov, S.: On the generative capacity of parallel communicating grammar systems. Intern. J. Comput. Math.45, 49–59 (1992)
Salomaa, A.: Formal Languages. Academic Press, New York London 1973
Santean, L.: Parallel communicating systems. Bulletin, EATCS42, 160–171 (1990)