Portal de Periódicos da CAPES

On the power of P systems with valuations

2001; National Polytechnic Institute; Volume: 5; Issue: 2 Linguagem: Espanhol

10.13053/cys-5-2-975

2007-9737

Víctor Miltrana, Gheorghe Păun, Carlos Martín Vide,

Cellular Automata and Applications

CONSIDERAMOS PEQUENAS VARIANTES DE SISTEMA P CON VALORACION TAL COMO SE PRESENTAN EN MARTIN-VIDE Y MITRANA (2000), Y ESTUDIAMOS SU CAPACIDAD GENERATIVA Y SU EFICIENCIA COMPUTACIONAL. CUANDO LA REESCRITURA TIENE LUGAR SOLAMENTE EN LAS PARTES FINALES DE LAS CADENAS, TODO LENGUAJE RECURSIVAMENTE ENUMERABLE PUEDE SER GENERADO POR MEDIO DE UN SISTEMA CON SOLO DOS MEMBRANAS. SI SE PERMITE LA REPLICACION DE LA CADENA (CUANDO UNA VALORACION DE UNA CADENA PERMITE A ESTA IR A VARIAS MEMBRANAS SE ENVIAN COPIAS DE LAS CADENAS DE TODAS ELLAS), ENTONCES SE PUEDEN RESOLVER EL PROBLEMA NO-COMPLETOS EN TIEMPO LINEAL. PROBAMOS ESTO PARA HHP (LA EXISTENCIA DE UN CAMINO HAMILTONIANO EN UN GRAFO ORIENTADO) Y OFRECEMOS ALGUNOS COMENTARIOS INFORMALES SOBRE UNA SOLUCION SIMILAR PARA SAT.