Solving Problems Through a Single Membrane System
|Author||Orellana Martín, David
Valencia Cabrera, Luis
Riscos Núñez, Agustín
Pérez Jiménez, Mario de Jesús
|Department||Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial|
|Published in||CMC20: 20th International Conference on Membrane Computing (2019), pp. 439-449.|
|Abstract||The tape of a deterministic Turing machine contains an unbounded number
of cells. Thanks to that, a single machine can solve decision problems with an infinite
number of instances. Nevertheless, in the framework of ...
The tape of a deterministic Turing machine contains an unbounded number of cells. Thanks to that, a single machine can solve decision problems with an infinite number of instances. Nevertheless, in the framework of membrane computing, traditionally a \solution" to an abstract decision problem consists of a family of membrane systems (where each system of the family is associated with a finite set of instances of the problem to be solved). An interesting question is to analyze the possibility to find a single membrane system able to deal with the infinitely many instances of a decision problem. In this context, it is fundamental to define precisely how the instances of the problem are introduced into the system. In this paper, two different methods are considered. The first one relies on a pre-computing process, where a polynomial-time computable function will be in charge of producing a multiset of objects associated with the instance to be solved. On the other hand, the second one assumes that the input alphabet of the system is equal to the alphabet of instances, and therefore instances are directly introduced in the initial configuration of the system. Polynomial complexity classes associated with these two approaches are introduced and some complexity aspects are studied.
|Citation||Orellana Martín, D., Valencia Cabrera, L., Riscos Núñez, A. y Pérez Jiménez, M.d.J. (2019). Solving Problems Through a Single Membrane System. En CMC20: 20th International Conference on Membrane Computing (439-449), Curtea de Arges, Romania: IMCS: International Membrane Computing Society.|