México
| Artículos de revistas
On the Power of P Systems with Valuations
| dc.creator | MILTRANA , VÍCTOR | |
| dc.creator | PAUN , GHEORGHE | |
| dc.creator | VIDE , CARLOS MARTÍN | |
| dc.date | 2009-10-05 | |
| dc.date.accessioned | 2018-03-16T14:22:51Z | |
| dc.date.available | 2018-03-16T14:22:51Z | |
| dc.identifier | http://ojs.unam.mx/index.php/cys/article/view/2547 | |
| dc.identifier.uri | http://repositorioslatinoamericanos.uchile.cl/handle/2250/1190419 | |
| dc.description | CONSIDERAMOS PEQUEÑAS VARIANTES DE SISTEMA P CON VALORACIÓN 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 REPLICACIÓN DE LA CADENA (CUANDO UNA VALORACIÓN DE UNA CADENA PERMITE A ESTA IR A VARIAS MEMBRANAS SE ENVÍAN 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 SOLUCIÓN SIMILAR PARA SAT. | es-ES |
| dc.description | WE CONSIDER SOME SLIGTH VARIANTS OF P SYSTEMS WITH VALUATION AS INTRODUCED IN MARTIN-VIDE AND MITRANA (2000) AND WE STUDY THEIR GENERATIVE POWER AN D COMPUTACIONAL EFFICIENCY. WHEN REWRITING TAKES PLACE ANLY IN THE ENDS OF THE STRINGS, EACH RECURSIVELY ENUMERABLE LANGUAGE CON BE GENERATED BY A SYSTEM WITH ONLY TWO MENBRANES. IF THE STRING REPLICATION IS ALLOWED (WHEN THE VALUATION OF A STRING ALLOWS THE STRING TO GO TO SEVERAL MEMBRANES, THEN COPIES OF THE STRING ARE SENT TO ALL THESE MEMBRANES), THEN NP-COMPLETE PROBLEMS CAN BE SOLVED IN LINEAR TIME. WE PROVE THIS FOR HPP (THE EXISTENCE OF A HAMILTONIAN PATH IN A DIRECTED GRAPH) AND GIVE SOME INFORMAL AXPLANATIONS ON A SIMILAR SOLUTION FOR SAT. | en-US |
| dc.format | application/pdf | |
| dc.language | spa | |
| dc.publisher | Computación y Sistemas | es-ES |
| dc.relation | http://ojs.unam.mx/index.php/cys/article/view/2547/2108 | |
| dc.source | Computación y Sistemas; Vol 5, No 002 (2001) | es-ES |
| dc.source | 1405-5546 | |
| dc.subject | SISTEMAS P; MEMBRANA; VALORACION; POLARIZACION; GRAMATICA DE VALENCIAS; PROBLEMA DE CAMINO HAMILTONIANO | es-ES |
| dc.title | On the Power of P Systems with Valuations | es-ES |
| dc.type | Artículos de revistas | |
| dc.type | Artículos de revistas |