Limits on Efficient Computation in P Systems with Symport/Antiport Rules
| Autor: | Macías Ramos, Luis Felipe, Song, Bosheng, Song, Tao, Pan, Linqiang, Pérez Jiménez, Mario de Jesús |
|---|---|
| Přispěvatelé: | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla. TIC193: Computación Natural, Ministerio de Ciencia e Innovación (MICIN). España |
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | idUS. Depósito de Investigación de la Universidad de Sevilla instname |
| Popis: | Classical membrane systems with symport/antiport rules observe the con- servation law, in the sense that they compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves. In these systems the environment plays an active role because the systems not only send objects to the environment, but also bring objects from the environment. In the initial configuration of a system, there is a special alphabet whose elements appear in an arbitrary large number of copies. The ability of these computing devices with infinite copies of some objects has been widely exploited in the design of efficient solutions to computationally hard problems. This paper deals with computational aspects of P systems with symport/antiport rules and membrane division rules or membrane separation rules. Specifically, we study the limitations of such P systems when the only communication rules allowed have length 1. Ministerio de Ciencia e Innovación TIN2012-37434 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|