The splicing operation was introduced in 1987 by Head as a mathematical model of the recombination of DNA molecules under the influence of restriction and ligases enzymes. This operation allows us to define a computing (language generating) device, called a splicing system. Other variants of this original definition were also proposed by Paun and Pixton respectively. The computational power of splicing systems has been thoroughly investigated. Nevertheless, an interesting problem is still open, namely the characterization of the class of regular languages generated by finite splicing systems. In this paper, we will solve the problem for a special class of finite splicing systems, termed reflexive splicing systems, according to each of the definitions of splicing given by Paun and Pixton. This special class of systems contains, in perticular, finite Head splicing systems. The notion of a constant, given by Schützenberger, once again intervenes.

The structure of reflexive regular splicing languages via Schutzenberger constants

DE FELICE, Clelia;ZIZZA, ROSALBA
2005

Abstract

The splicing operation was introduced in 1987 by Head as a mathematical model of the recombination of DNA molecules under the influence of restriction and ligases enzymes. This operation allows us to define a computing (language generating) device, called a splicing system. Other variants of this original definition were also proposed by Paun and Pixton respectively. The computational power of splicing systems has been thoroughly investigated. Nevertheless, an interesting problem is still open, namely the characterization of the class of regular languages generated by finite splicing systems. In this paper, we will solve the problem for a special class of finite splicing systems, termed reflexive splicing systems, according to each of the definitions of splicing given by Paun and Pixton. This special class of systems contains, in perticular, finite Head splicing systems. The notion of a constant, given by Schützenberger, once again intervenes.
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: http://hdl.handle.net/11386/1002845
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? ND
social impact