PC GRAMMAR SYSTEMS WITH CLUSTERS OF COMPONENTS

作     者：Csuhaj-Varju, Erzsebet Oswald, Marion Vaszil, Gyoergy 

作者机构：Hungarian Acad Sci Comp & Automat Res Inst H-1111 Budapest Hungary Eotvos Lorand Univ Dept Algorithms & Their Applicat Fac Informat H-1117 Budapest Hungary Vienna Univ Technol Fac Informat A-1040 Vienna Austria 

出 版 物：《INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE》 (国际计算机科学基础杂志)

年 卷 期：2011年第22卷第1期

页      面：203-212页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Parallel communicating grammar systems descriptional complexity distributed problem solving clusters of agents 

摘      要：We introduce PC grammar systems where the components form clusters and the query symbols refer to clusters not individual grammars, i.e., the addressee of the query is not precisely identified. We prove that if the same component replies to all queries issued to a cluster in a rewriting step, then non-returning PC grammar systems with 3 clusters and 7 context-free components are able to generate any recursively enumerable language. We also provide open problems and directions for future research.