We will consider here the splicing systems, generative devices inspired by cut and paste phenomena on DNA molecules under the action of restriction and ligase enzymes. A DNA strand can be viewed as a string over a four letter alphabet (the four nucleotides), therefore we can model DNA computation within the framework of formal language theory. In spite of a vast literature on splicing systems, briefly surveyed here, a few problems related to their computational power are still open. We intend to evidence how classical techniques and concepts in automata theory are a legitimate tool for investigating some of these problems.

Bonizzoni, P., De Felice, C., Mauri, G., & Zizza, R. (2002). Decision problems for linear and circular splicing systems. In Developments in Language Theory (pp.221-224). Berlin : Springer [10.1007/3-540-45005-X_7].

Decision problems for linear and circular splicing systems

BONIZZONI, PAOLA;MAURI, GIANCARLO;
2002

Abstract

We will consider here the splicing systems, generative devices inspired by cut and paste phenomena on DNA molecules under the action of restriction and ligase enzymes. A DNA strand can be viewed as a string over a four letter alphabet (the four nucleotides), therefore we can model DNA computation within the framework of formal language theory. In spite of a vast literature on splicing systems, briefly surveyed here, a few problems related to their computational power are still open. We intend to evidence how classical techniques and concepts in automata theory are a legitimate tool for investigating some of these problems.
slide + paper
Scientifica
splicing systems
English
International Conference on Developments in Language Theory
978-3-540-40431-6
Bonizzoni, P., De Felice, C., Mauri, G., & Zizza, R. (2002). Decision problems for linear and circular splicing systems. In Developments in Language Theory (pp.221-224). Berlin : Springer [10.1007/3-540-45005-X_7].
Bonizzoni, P; De Felice, C; Mauri, G; Zizza, R
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/17534
Citazioni
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 13
Social impact