Solving Problems in a DistributedWay in Membrane Computing: dP Systems
Keywords:
Membrane computing, P system, distributed computing, communication complexity, Chomsky hierarchyAbstract
Although P systems are distributed parallel computing devices, no explicit way of handling the input in a distributed way in this framework was considered so far. This note proposes a distributed architecture (based on cell-like P systems, with their skin membranes communicating through channels as in tissue-like P systems, according to specified rules of the antiport type), where parts of a problem can be introduced as inputs in various components and then processed in parallel. The respective devices are called dP systems, with the case of accepting strings called dP automata. The communication complexity can be evaluated in various ways: statically (counting the communication rules in a dP system which solves a given problem), or dynamically (counting the number of communication steps, of communication rules used in a computation, or the number of objects communicated). For each measure, two notions of “parallelizability" can be introduced. Besides (informal) definitions, some illustrations of these idea are provided for dP automata: each regular language is “weakly parallelizable" (i.e., it can be recognized in this framework, using a constant number of communication steps), and there are languages of various types with respect to Chomsky hierarchy which are “efficiently parallelizable" (they are parallelizable and, moreover, are accepted in a faster way by a dP automaton than by a single P automaton). Several suggestions for further research are made.References
H. Adorna, Gh. Păun, M.J. Pérez-Jiménez: On communication complexity in evolutioncommunication P systems. Manuscript, 2009.
L. Babai, P. Frankl, J. Simon: Complexity classes in communication complexity. Proc. 27th Annual Symp. Founf. Computer Sci., 1986, 337-347. http://dx.doi.org/10.1109/sfcs.1986.15
F. Bernardini, M. Gheorghe: Population P systems. J. Universal Computer Sci., 10, 5 (2004), 509- 539.
M. Cardona, M.A. Colomer, A. Margalida, I. Pérez-Hurtado, M.J. Pérez-Jiménez, D. Sanuy: A P system based model of an ecosystem of some scavenger birds. Membrane Computing. Proc. WMC10, Curtea de Arge¸s, 2009 (Gh. Păun et al., eds.), LNCS 5957, Springer, 2010, 182-195.
M. Cavaliere: Evolution-communication P systems. Membrane Computing. Proc. WMC 2002, Curtea de Arge¸s (Gh. Păun et al., eds.), LNCS 2597, Springer, Berlin, 2003, 134-145.
E. Csuhaj-Varjú: P automata. Membrane Computing. Proc. WMC5, Milano, 2004 (G. Mauri et al., eds.), LNCS 3365, Springer, Berlin, 2005, 19-35.
R. Freund, Gh. Păun, M.J. Pérez-Jiménez: Tissue-like P systems with channel-states. Theoretical Computer Sci., 330, 1 (2005), 101-116. http://dx.doi.org/10.1016/j.tcs.2004.09.013
J. Gruska: Descriptional complexity of context-free languages. Proc. Symp. on Mathematical Foundations of Computer Science, MFCS, High Tatras, 1973, 71-83.
J. Hromkovic: Communication Complexity and Parallel Computing: The Application of Communication Complexity in Parallel Computing. Springer, Berlin, 1997. http://dx.doi.org/10.1007/978-3-662-03442-2
M. Oswald: P Automata. PhD Thesis, TU Vienna, 2003.
Gh. Păun: Membrane Computing. An Introduction. Springer, Berlin, 2002. http://dx.doi.org/10.1007/978-3-642-56196-2
Gh. Păun, G. Rozenberg, A. Salomaa, eds.: Handbook of Membrane Computing. Oxford University Press, 2010. http://dx.doi.org/10.1007/978-3-642-11467-0
M.J. Pérez-Jiménez: A computational complexity theory in membrane computing. Membrane Computing. Proc. WMC10, Curtea de Arge¸s, 2009 (Gh. Păun et al., eds.), LNCS 5957, Springer, 2010, 125-148.
A.E. Porreca, A. Leporati, G. Mauri, C. Zandron: Introducing a space complexity measure for P systems. Intern. J. Computers, Communications and Control, 4, 3 (2009), 301-310.
G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. 3 volumes, Springer, Berlin, 1998.
A.C. Yao: Some complexity questions related to distributed computing. ACM Symposium on Theory of Computing, 1979, 209-213.
The P Systems Website: www.ppage.psystems.eu.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
