Abstract | ||
---|---|---|
We consider P colonies as introduced in Kelemen et al. (2005) and investigate their computational power when working in the maximally parallel and in the sequential mode. It turns out that there is a trade-off between maximal parallelism and checking programs: Using checking programs (i.e., priorities on the communication rules in the programs of the agents), P colonies working in the sequential mode with height at most 5 are computationally complete, whereas when working in the maximally parallel mode, P colonies (again with height 5) already obtain the same computational power without using checking programs. Moreover, when allowing an arbitrary number of programs for each agent, we can prove that P colonies with only one agent (thus these P colonies are working in the sequential mode) are already computationally complete. Finally, P colonies with an arbitrary number of agents working in the sequential mode as well as even P colonies with only one agent using an arbitrary number of non-checking programs characterize the family of languages generated by matrix grammars without appearance checking. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1109/SYNASC.2005.55 | SYNASC |
Keywords | Field | DocType |
maximally parallel mode,sequential mode,p colonies working,arbitrary number,p colony,checking program,communicaton rule,matrix grammar,computational power,maximally parallel,appearance checking,computational complexity,grammars | Rule-based machine translation,Discrete mathematics,Matrix algebra,Matrix (mathematics),Computer science,Theoretical computer science,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
0-7695-2453-2 | 16 | 1.47 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Rudolf Freund | 1 | 1000 | 109.64 |
Marion Oswald | 2 | 320 | 30.27 |