Closure and decidability properties of some language classes with respect to ciliate bio-operations

被引:30
作者
Daley, M
Ibarra, OH [1 ]
Kari, L
机构
[1] Univ Calif Santa Barbara, Dept Comp Sci, Santa Barbara, CA 93106 USA
[2] Univ Western Ontario, Dept Comp Sci, London, ON N6A 5B7, Canada
关键词
D O I
10.1016/S0304-3975(03)00139-7
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 LlozengeY=R, XlozengeL=R where L and R are given languages, X and Y are unknowns, and lozenge signifies one of the defined bio-operations. (C) 2003 Elsevier B.V. All rights reserved.
引用
收藏
页码:19 / 38
页数:20
相关论文
共 19 条
[1]   REVERSAL-BOUNDED MULTIPUSHDOWN MACHINES [J].
BAKER, BS ;
BOOK, RV .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 8 (03) :315-332
[2]  
DALEY M, 2002, 6 INT C DEV LANG THE, P122
[3]   Operations and language generating devices suggested by the genome evolution [J].
Dassow, J ;
Mitrana, V ;
Salomaa, A .
THEORETICAL COMPUTER SCIENCE, 2002, 270 (1-2) :701-738
[4]  
EHRENFEUCHT A, 2001, EVOL COMPUT, P45
[5]   On some operations on strings suggested by gene assembly in ciliates [J].
Freund, R ;
Martín-Vide, C ;
Mitrana, V .
NEW GENERATION COMPUTING, 2002, 20 (03) :279-293
[6]  
Ginsburg S., 1975, ALGEBRAIC AUTOMATA T
[7]  
HARJU T, 2001, IN PRESS P 28 INT C, P579
[8]  
Hopcroft J.E., 2001, INTRO AUTOMATA THEOR
[9]   REVERSAL-BOUNDED MULTICOUNTER MACHINES AND THEIR DECISION PROBLEMS [J].
IBARRA, OH .
JOURNAL OF THE ACM, 1978, 25 (01) :116-133
[10]   ON LANGUAGE EQUATIONS WITH INVERTIBLE OPERATIONS [J].
KARI, L .
THEORETICAL COMPUTER SCIENCE, 1994, 132 (1-2) :129-150