Descripción
|
|
---|---|
Abstract We study the computational power of pure insertion grammars. We show that pure insertion grammars of weight 3 can characterize all recursively enumerable languages. This is achieved by either applying an inverse morphism and a weak coding, or a left (right) quotient with a regular language. We also study an application in DNA computing and improve some known results concerning the power of insertion–deletion DNA systems. | |
Internacional
|
Si |
JCR del ISI
|
Si |
Título de la revista
|
THEORETICAL COMPUTER SCIENCE |
ISSN
|
0304-3975 |
Factor de impacto JCR
|
0,735 |
Información de impacto
|
|
Volumen
|
396 |
DOI
|
doi:10.1016/j.tcs.2008.01.037 |
Número de revista
|
1 |
Desde la página
|
264 |
Hasta la página
|
270 |
Mes
|
MAYO |
Ranking
|