| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436387 | Theoretical Computer Science | 2008 | 7 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
