Splicing systems have been introduced twenty years ago as a basic abstract model of the DNA recombination mechanism. In fact, it was the first of a long series of computational models based on a molecular process. Much research has been done on the generative capacity of these systems, mostly considering enhanced variants of the original definition. However, some important questions about the original finite systems are still unsolved. For example, we do not have any systematic way to go about constructing a splicing system for a given language, and we still lack significant algorithmic results for this model. In this work, we survey new research directions on finite splicing that could suggest a new approach to the solution of these basic problems and could shed a new light on the splicing formalism. These include an alternative definition of the splicing language, splicing systems as accepting devices, and complexity issues for splicing systems.
Bonizzoni, P., Loss, R. (2009). Finite splicing: Generative capacity, new models and complexity aspects. In A. Condon, D. Harel, J. N. Kok, A. Salomaa, E. Winfree (a cura di), Algorithmic Bioprocesses (pp. 313-329). Berlin : Springer [10.1007/978-3-540-88869-7_17].
Finite splicing: Generative capacity, new models and complexity aspects
BONIZZONI, PAOLA;
2009
Abstract
Splicing systems have been introduced twenty years ago as a basic abstract model of the DNA recombination mechanism. In fact, it was the first of a long series of computational models based on a molecular process. Much research has been done on the generative capacity of these systems, mostly considering enhanced variants of the original definition. However, some important questions about the original finite systems are still unsolved. For example, we do not have any systematic way to go about constructing a splicing system for a given language, and we still lack significant algorithmic results for this model. In this work, we survey new research directions on finite splicing that could suggest a new approach to the solution of these basic problems and could shed a new light on the splicing formalism. These include an alternative definition of the splicing language, splicing systems as accepting devices, and complexity issues for splicing systems.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.