- Para el p-System de la computadora, consulte UCSD p-System .
Un sistema P es un modelo computacional en el campo de la informática que realiza cálculos utilizando un proceso de inspiración biológica. Se basan en la estructura de las células biológicas , abstrayéndose de la forma en que los productos químicos interactúan y atraviesan las membranas celulares . El concepto fue introducido por primera vez en un informe de 1998 [1] por el informático Gheorghe Păun , cuyo apellido es el origen de la letra P en «P Systems». Las variaciones en el modelo del sistema P llevaron a la formación de una rama de investigación conocida como " computación de membrana ".
Aunque está inspirado en la biología, el interés principal de la investigación en los sistemas P está relacionado con su uso como modelo computacional, más que como modelo biológico , [2] aunque esto también se está investigando. [3] [4] [5]
Descripción informal
El sistema AP se define como una serie de membranas que contienen sustancias químicas (en cantidades finitas ), catalizadores y reglas que determinan las posibles formas en que las sustancias químicas pueden reaccionar entre sí para formar productos. Las reglas también pueden hacer que los productos químicos pasen a través de las membranas o incluso que las membranas se disuelvan .
Al igual que en una célula biológica, donde una reacción química solo puede tener lugar en el caso fortuito de que las moléculas químicas requeridas colisionen e interactúen (posiblemente también con un catalizador), las reglas en un sistema P se aplican al azar. Esto hace que el cálculo proceda de una manera no determinista , lo que a menudo da como resultado que se encuentren múltiples soluciones si se repite el cálculo.
El sistema AP continúa hasta que alcanza un estado en el que no son posibles más reacciones. En este punto, el resultado del cálculo son todos los productos químicos que han pasado fuera de la membrana más externa, o de lo contrario, los que han pasado a una membrana de "resultado" designada. [4]
Componentes de un sistema P
Aunque existen muchas variedades del sistema P, la mayoría comparten los mismos componentes básicos. Cada elemento tiene un papel específico que desempeñar, y cada uno tiene un fundamento en la arquitectura celular biológica en la que se basan los sistemas P.
El entorno
El medio ambiente es el entorno del sistema P. En el estado inicial de un sistema P, solo contiene el contenedor-membrana, y aunque el entorno nunca puede contener reglas, es posible que se le pasen objetos durante el cálculo. Los objetos que se encuentran dentro del entorno al final del cálculo constituyen todo o parte de su "resultado".
Membranas
Las membranas son las principales "estructuras" dentro de un sistema P. Una membrana es una unidad discreta que puede contener un conjunto de objetos (símbolos / catalizadores), un conjunto de reglas y un conjunto de otras membranas contenidas en su interior. La membrana más externa, que se mantiene dentro del medio ambiente, a menudo se denomina "membrana del recipiente" o "membrana de la piel". Como lo sugiere su homónimo, las membranas son permeables y los símbolos resultantes de una regla pueden cruzarlas. Una membrana (pero no la membrana del recipiente) también puede “disolverse”, en cuyo caso su contenido, salvo reglas (que se pierden), migrará a la membrana en la que estaba contenido. [2]
Algunas variantes del sistema P permiten que una membrana se divida, posea una carga o tenga una permeabilidad variable al cambiar el grosor de la membrana. [2]
Simbolos
Los símbolos representan sustancias químicas que pueden reaccionar con otras sustancias químicas para formar algún producto. En un sistema P, cada tipo de símbolo se representa típicamente con una letra diferente. Por tanto, el contenido de símbolos de una membrana está representado por una cadena de letras. Debido a que la multiplicidad de símbolos en una región es importante, los conjuntos múltiples se utilizan comúnmente para representar el contenido de símbolos de una región.
Existen símbolos de casos especiales, por ejemplo, un delta minúscula (δ) se usa a menudo para iniciar la disolución de una membrana, y esto solo se encontrará en la salida de una regla: al encontrarse, invoca una reacción y es utilizado en el proceso.
Catalizadores
Los catalizadores son similares a sus homónimos en química. Se representan y se usan de la misma manera que los símbolos, pero nunca se consumen durante una " reacción ", son simplemente un requisito para que ocurra.
Reglas
Las reglas representan una posible reacción química dentro de una membrana, lo que hace que evolucione a un nuevo estado. Una regla tiene un conjunto requerido de objetos de entrada (símbolos o catalizadores) que deben estar presentes para que se aplique. Si los objetos requeridos están presentes, los consume y produce un conjunto de objetos de salida. También se puede especificar que una regla tenga prioridad sobre otras reglas, en cuyo caso las reglas menos dominantes solo se aplicarán cuando no sea posible aplicar una regla más dominante (es decir, las entradas requeridas no están presentes).
Hay tres (en el modelo básico del sistema P) formas distintas en las que una regla puede manejar sus objetos de salida. Por lo general, los objetos de salida se pasan a la membrana actual (la misma membrana en la que residen la regla y las entradas), conocida como regla aquí . Sin embargo, hay dos modificadores que se pueden especificar en los objetos de salida cuando se definen las reglas, dentro y fuera . El modificador in hace que el objeto se pase a uno de los hijos de la membrana actual (viajando hacia adentro en relación con la estructura del sistema P), elegido al azar durante el cálculo. El modificador de salida hace que el objeto salga de la membrana actual y pase a su membrana madre oa una membrana hermana, especificada durante la especificación del sistema P.
Proceso de computación
Un cálculo funciona desde un estado inicial hasta un estado final a través de una serie de pasos discretos . Cada etapa implica la iteración a través de todas las membranas en el sistema P y la aplicación de reglas, que se produce tanto en un máximo paralelo y no determinista manera. [4]
Trabajando paso a paso, un cálculo se detiene cuando no puede tener lugar una evolución adicional (es decir, cuando no se pueden aplicar reglas). En este punto, cualquier objeto que se haya pasado al medio ambiente, o dentro de una membrana de 'resultado' designada, se cuenta como resultado del cálculo. [4]
Aplicación de reglas
En cada paso de un cálculo, un objeto solo se puede usar una vez, ya que las reglas lo consumen cuando se aplican. El método de aplicar una regla dentro de una membrana es el siguiente:
- Asignar símbolos del contenido de una membrana a las entradas de la regla
- Si se satisfacen todas las entradas, elimine todos los símbolos asignados de la membrana
- Cree símbolos de salida y manténgalos presionados hasta que se haya realizado toda la asignación de reglas, para todas las membranas.
- Agregue símbolos de salida a las membranas específicas.
- Disuelva las membranas según sea necesario
Los resultados no se pasan inmediatamente a las membranas porque esto contravendría la naturaleza máximamente paralela de la aplicación de reglas, sino que se distribuyen después de que se hayan aplicado todas las reglas posibles.
Aplicación no determinista
El orden de aplicación de las reglas se elige al azar. El orden de aplicación de las reglas puede tener un efecto significativo sobre qué reglas se pueden aplicar en un momento dado y el resultado de un paso de ejecución.
Considere una membrana que contiene solo un símbolo "a" y las dos reglas a → ab y a → aδ. Como ambas reglas se basan en la presencia de un símbolo "a", del cual solo hay uno, el primer paso del cálculo permitirá que se aplique la primera o la segunda regla, pero no ambas. Los dos posibles resultados de este paso son muy diferentes:
- La membrana pasa al siguiente paso del cálculo con un símbolo "a" y un símbolo "b" presentes, y nuevamente una de las dos reglas se asigna aleatoriamente al símbolo "a".
- La membrana se disuelve y se pasa un solo símbolo "a" a la membrana contenedora.
Aplicación máximamente paralela
Esta es una propiedad de la aplicación de reglas por la cual todas las posibles asignaciones de reglas deben tener lugar durante cada paso del cálculo. En esencia, esto significa que la regla a → aa tiene el efecto de duplicar el número de símbolos "a" en su membrana contenedora en cada paso, porque la regla se aplica a cada aparición de un símbolo "a" presente.
Como modelo computacional
La mayoría de las variantes de los sistemas P son computacionalmente universales . [4] Esto se extiende incluso para incluir variantes que no usan prioridades de reglas, generalmente un aspecto fundamental de los sistemas P. [6]
Como modelo de cálculo, los sistemas P ofrecen la atractiva posibilidad de resolver problemas NP-completos en un tiempo inferior al exponencial . [4] Se sabe que algunas variantes del sistema P son capaces de resolver el problema SAT (satisfacibilidad booleana) en tiempo lineal [7] y, debido a que todos los problemas NP-completos son equivalentes , esta capacidad se aplica a todos estos problemas. Como no existe un método actual para implementar directamente un sistema P por derecho propio, su funcionalidad se emula en cambio [8] y, por lo tanto, la resolución de problemas NP-completos en tiempo lineal sigue siendo teórica. Sin embargo, también se ha demostrado que cualquier sistema P determinista puede simularse en una máquina de Turing en tiempo polinomial . [2]
Ejemplo de cálculo
La imagen que se muestra muestra el estado inicial de un sistema P con tres membranas. Debido a su naturaleza jerárquica, los sistemas de P se representan a menudo gráficamente con dibujos que se asemejan a los diagramas de Venn o David Harel 's Higraph (ver Statechart ).
La membrana más externa, 1, es la membrana contenedor para este sistema P y contiene un solo cabo regla. La membrana 2 contiene cuatro reglas aquí , con dos en una relación de prioridad: cc → c siempre se aplicará con preferencia a c → δ. El símbolo delta representa el símbolo especial de "disolución". La membrana más interna, 3, contiene un conjunto de símbolos ("ac") y tres reglas, del tipo aquí . En este estado inicial no se aplican reglas fuera de la membrana 3: no hay símbolos fuera de esa membrana. Sin embargo, durante la evolución del sistema, a medida que los objetos pasan entre las membranas, las reglas de otras membranas se activarán.
Cálculo
Debido a la naturaleza no determinista de los sistemas P, hay muchas rutas de cálculo diferentes de las que es capaz un solo sistema P, lo que lleva a resultados diferentes. La siguiente es una posible ruta de cálculo para el sistema P representado.
Paso 1
Desde la configuración inicial, solo la membrana 3 tiene contenido de objeto: "ac"
- "c" se asigna a c → cc
- "a" se asigna a a → ab
Paso 2
La membrana 3 ahora contiene: "abcc"
- "a" se asigna a a → bδ
- "c" se asigna a c → cc
- "c" se asigna a c → cc
Observe el comportamiento paralelamente máximo de la aplicación de reglas que lleva a que la misma regla se aplique dos veces durante un paso.
Observe también que la aplicación de la segunda regla (a → bδ) en oposición a la primera (a → ab) no es determinista y puede presumirse aleatoria. El sistema también podría haber continuado aplicando la primera regla (y al mismo tiempo duplicando las partículas c) indefinidamente.
La membrana 3 ahora se disuelve, ya que se ha encontrado el símbolo de disolución (δ) y todo el contenido del objeto de esta membrana pasa a la membrana 2.
Paso 3
La membrana 2 ahora contiene: "bbcccc"
- "b" se asigna a b → d
- "b" se asigna a b → d
- "cc" se asigna a cc → c
- "cc" se asigna a cc → c
Paso 4
La membrana 2 ahora contiene: "ddcc"
- "d" se asigna ad → de
- "d" se asigna ad → de
- "cc" se asigna a cc → c
Paso 5
La membrana 2 ahora contiene: "dedec"
- "d" se asigna ad → de
- "d" se asigna ad → de
- "c" se asigna a c → δ
Observe que la prioridad sobre c → δ se ha eliminado ahora que las entradas requeridas para cc → c ya no existen. La membrana 2 ahora se disuelve y todo el contenido del objeto pasa a la membrana 1.
Paso 6
La membrana 1 ahora contiene: "deedee"
- "e" se asigna a e → e out
- "e" se asigna a e → e out
- "e" se asigna a e → e out
- "e" se asigna a e → e out
La computación se detiene
La membrana 1 ahora contiene: "dd" y, debido a la regla out e → e out , el entorno contiene: "eeee". En este punto, el cálculo se detiene ya que no es posible realizar más asignaciones de objetos a las reglas. El resultado del cálculo son cuatro símbolos "e".
Las únicas elecciones no deterministas ocurrieron durante los pasos 1 y 2, al elegir dónde asignar el símbolo "a" solitario. Considere el caso en el que "a" se asigna a a → bδ durante el paso 1: al disolverse la membrana 3, solo existirían un solo objeto "b" y dos "c", lo que llevaría a la creación de un solo objeto "e" para eventualmente pasar como resultado del cálculo.
Ver también
- Biología Celular)
- Computación de inspiración biológica
- Lenguaje formal
- Hypergraph
- MGS
- Biologia de sistemas
Referencias
- ^ Păun, Gheorghe (1998). Computación con membranas . Informe TUCS 208. Centro Turku de Ciencias de la Computación. ISBN 978-952-12-0303-9. Consultado el 16 de diciembre de 2012 .
- ^ a b c d Păun, Gheorghe ; Grzegorz Rozenberg (2002). "Una guía para la computación de membrana". Informática Teórica . 287 (1): 73–100. CiteSeerX 10.1.1.76.8425 . doi : 10.1016 / S0304-3975 (02) 00136-6 . ISSN 0304-3975 .
- ^ Ardelean, Ioan; Matteo Cavaliere (junio de 2003). "Modelado de procesos biológicos mediante el uso de un software de sistema p probabilístico". Computación natural . 2 (2): 173-197. doi : 10.1023 / A: 1024943605864 . ISSN 1567-7818 .
- ^ a b c d e f Păun, Gheorghe (2006). "Introducción a la Computación de Membranas". Aplicaciones de la Computación de Membranas . Springer Berlín Heidelberg. págs. 1-42. ISBN 978-3-540-29937-0.
- ^ Nash, Anthony; Sara Kalvala (2019). "Modelo de sistema AP de enjambre y agregación en una colonia de Myxobacterial" . Journal of Membrane Computing . 1 : 103-11. doi : 10.1007 / s41965-019-00015-0 .
- ^ Freund, Rudolf; Kari, Lila; Oswald, Marion; Sosík, Petr (2005). "Sistemas P computacionalmente universales sin prioridades: dos catalizadores son suficientes" . Informática Teórica . 330 (2): 251–266. doi : 10.1016 / j.tcs.2004.06.029 . ISSN 0304-3975 .
- ^ Păun, Gheorghe (2001). "Sistemas P con membranas activas: atacando problemas NP-completos" (PDF) . Autómatas, lenguajes y combinatorios . 6 (1): 75–90 . Consultado el 3 de febrero de 2008 .
- ^ Zandron, Claudio; Claudio Ferretti; Giancarlo Mauri (2000). "Resolución de problemas NP-Complete utilizando sistemas P con membranas activas". Modelos de computación no convencionales . págs. 289-301. ISBN 1-85233-415-0.
enlaces externos
- P Systems : sitio web para la investigación de sistemas P.