Solving Problems in a Distributed Way in Membrane Computing: dP Systems

TitleSolving Problems in a Distributed Way in Membrane Computing: dP Systems
Publication TypeJournal Papers
Year of Publication2010
AuthorsPaun, G., & Pérez-Jiménez M. J.
Journal TitleInternational Journal of Computers, Communications and Control
PublisherAgora University Editing House - CCC Publications
Place PublishedOradea, Romania
Date Published06/2010

Although P systems are distributed parallel computing devices, noexplicit way of handling the input in a distributed way in this framework wasconsidered so far. This note proposes a distributed architecture (based on cell-likeP systems, with their skin membranes communicating through channels as intissue-like P systems, according to specified rules of the antiport type), whereparts of a problem can be introduced as inputs in various components and thenprocessed in parallel. The respective devices are called dP systems, with the caseof accepting strings called dP automata. The communication complexity can beevaluated in various ways: statically (counting the communication rules in a dPsystem which solves a given problem), or dynamically (counting the number ofcommunication steps, of communication rules used in a computation, or the numberof objects communicated). For each measure, two notions of “parallelizability" canbe introduced. Besides (informal) definitions, some illustrations of these idea areprovided for dP automata: each regular language is “weakly parallelizable" (i.e., itcan be recognized in this framework, using a constant number of communicationsteps), and there are languages of various types with respect to Chomsky hierarchywhich are “efficiently parallelizable" (they are parallelizable and, moreover, areaccepted in a faster way by a dP automaton than by a single P automaton). Several suggestions for further research are made.

Keywordschomsky hierarchy, communication complexity, distributed computing, Membrane computing, P system
Impact Factor



38/60 - Q3

ISSN Number1841-9836
408.pdf115.75 KB