loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC'05)
P Colonies Working in the Maximally Parallel and in the Sequential Mode
Timisoara, Romania
September 25-September 29
ISBN: 0-7695-2453-2
Rudolf Freund, Vienna University of Technology
Marion Oswald, Vienna University of Technology
We consider P colonies as introduced in [4] 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 communicaton 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.
Citation:
Rudolf Freund, Marion Oswald, "P Colonies Working in the Maximally Parallel and in the Sequential Mode," synasc, pp.419-426, Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.