Name
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 namely investigate closure operations of language families under the mentioned bio-operations and study language equations involving them. Among the problems addressed, we study the decidability of 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 | Venue | Keywords |
|---|---|---|
2002 | Developments in Language Theory | language family,linear version,language theoretic point,closure operation,re-arranging gene segment,ciliate bio-operations,study language,circular strand,computational power,form l,dna strand,closure operator |
Field | DocType | Volume |
Discrete mathematics,Language equation,Combinatorics,Algebra,Of the form,Closure (mathematics),Decidability,Encryption,Formal grammar,Regular language,Mathematics | Conference | 2450 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-40431-7 | 13 |
PageRank | References | Authors |
1.11 | 6 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Daley | 1 | 166 | 22.18 |
| Lila Kari | 2 | 1123 | 124.45 |