Name
Title | ||
|---|---|---|
Closure and decidability properties of some language classes with respect to ciliate bio-operations |
Abstract | ||
|---|---|---|
The process of gene unscrambling in ciliates (a type of unicellular protozoa), which accomplishes the difficult task of re-arranging gene segments in the correct order and deleting non-coding sequences from an “encrypted” version of a DNA strand, has been modeled and studied so far from the point of view of the computational power of the DNA bio-operations involved. Here we concentrate on a different aspect of the process, by considering only the linear version of the bio-operations, that do not involve thus any circular strands, and by studying the resulting formal operations from a purely language-theoretic point of view. We investigate closure properties of language families under the mentioned bio-operations and study language equations involving them. We also study the decidability of the existence of solutions to equations of the form L¿Y=R, X¿L=R where L and R are given languages, X and Y are unknowns, and ¿ signifies one of the defined bio-operations. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0304-3975(03)00139-7 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
study language,language class,language family,decidability property,linear version,re-arranging gene segment,computational power,language-theoretic point,form l,closure property,dna strand,circular strand | Journal | 306 |
Issue | ISSN | Citations |
1 | Theoretical Computer Science | 19 |
PageRank | References | Authors |
1.02 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Daley | 1 | 166 | 22.18 |
| Oscar H. Ibarra | 2 | 3235 | 741.44 |
| Lila Kari | 3 | 1123 | 124.45 |