Closure and decidability properties of some language classes with respect to ciliate bio-operations
✍ Scribed by Mark Daley; Oscar H. Ibarra; Lila Kari
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 285 KB
- Volume
- 306
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
The process of gene unscrambling in ciliates (a type of unicellular protozoa), which accomplishes the di cult 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 di erent 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 signiÿes one of the deÿned bio-operations.