Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. Via automata properties we show that it is decidable whether a regular language L on a one-letter alphabet is generated by a finite (Paun) circular splicing system: L has this property if and only if there is a unique final state qn on the closed path in the transition diagram of the minimal finite state automaton A recognizing L and qn is idempotent (i.e., δ(qn,an)=qn). This result is obtained by an already known characterization of the unary languages L generated by a finite (Paun) circular splicing system and, in turn, allows us to simplify the description of the structure of L. This description is here extended to the larger class of the uniform languages, i.e., the circularizations of languages with the form AJ=∪j∈JAj, J being a subset of the set N of the nonnegative integers. Finally, we exhibit a regular circular language, namely ∼((A2)*∪(A3)*), that cannot be generated by any finite circular splicing system. © 2005 Elsevier B.V. All rights reserved.

Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R. (2005). On the power of circular splicing. DISCRETE APPLIED MATHEMATICS, 150(1-3), 51-66 [10.1016/j.dam.2005.02.012].

On the power of circular splicing

BONIZZONI, PAOLA;MAURI, GIANCARLO;
2005

Abstract

Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. Via automata properties we show that it is decidable whether a regular language L on a one-letter alphabet is generated by a finite (Paun) circular splicing system: L has this property if and only if there is a unique final state qn on the closed path in the transition diagram of the minimal finite state automaton A recognizing L and qn is idempotent (i.e., δ(qn,an)=qn). This result is obtained by an already known characterization of the unary languages L generated by a finite (Paun) circular splicing system and, in turn, allows us to simplify the description of the structure of L. This description is here extended to the larger class of the uniform languages, i.e., the circularizations of languages with the form AJ=∪j∈JAj, J being a subset of the set N of the nonnegative integers. Finally, we exhibit a regular circular language, namely ∼((A2)*∪(A3)*), that cannot be generated by any finite circular splicing system. © 2005 Elsevier B.V. All rights reserved.
Articolo in rivista - Articolo scientifico
formal languages, circular splicing
English
51
66
16
Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R. (2005). On the power of circular splicing. DISCRETE APPLIED MATHEMATICS, 150(1-3), 51-66 [10.1016/j.dam.2005.02.012].
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/1902
Citazioni
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 9
Social impact