Regular Languages Generated by Reflexive Finite Splicing Systems

  • Paola Bonizzoni
  • Clelia De Felice
  • Giancarlo Mauri
  • Rosalba Zizza
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


Splicing systems are a generative device inspired by a cut and paste phenomenon on DNA molecules, introduced by Head in 1987 and subsequently defined with slight variations also by Paun and Pixton respectively [8, 13, 17]. We will face the problem of characterizing the class of regular languages generated by finite splicing systems. We will solve this problem for the special class of the reflexive finite splicing systems introduced in [9, 10]. As a byproduct, we give a characterization of the regular languages generated by finite Head splicing systems. As in already known results, the notion of constant, given by Schützenberger in [19], intervenes.


Canonical Transformation Regular Language State Automaton Discrete Apply Mathematic Formal Language Theory 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Berstel, J., Perrin, D.: Theory of codes. Academic Press, New York (1985)zbMATHGoogle Scholar
  2. 2.
    Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R.: The structure of reflexive regular splicing languages via Schützenberger constants. manuscript (2003)Google Scholar
  3. 3.
    Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R.: Decision Problems on Linear and Circular Splicing. In: Ito, M., Toyama, M. (eds.): DLT 2002. Lecture Notes in Computer Science, Springer-Verlag, New York (2003)Google Scholar
  4. 4.
    Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R.: On the power of linear and circular splicing. submitted (2002)Google Scholar
  5. 5.
    Bonizzoni, P., Ferretti, C., Mauri, G., Zizza, R.: Separating some splicing models. Information Processing Letters 79:6 (2001) 255–259zbMATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Gatterdam, R.W.: Algorithms for splicing systems. SIAM Journal of Computing 21:3 (1992) 507–520zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    Goode, E., Head, T., Pixton, D. private communication (2002)Google Scholar
  8. 8.
    Head, T.: Formal Language Theory and DNA. An analysis of the generative capacity of specific recombinant behaviours. Bull. Math. Biol. 49 (1987) 737–759zbMATHMathSciNetGoogle Scholar
  9. 9.
    Head, T.: Splicing languages generated with one sided context. In: Paun, Gh. (ed.): Computing with Bio-molecules. Theory and Experiments, Springer-Verlag Singapore (1998)Google Scholar
  10. 10.
    Head, T., Paun, Gh., Pixton, D.: Language theory and molecular genetics. Generative mechanisms suggested by DNA recombination. In: Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, Vol. 2. Springer-Verlag (1996) 295–360Google Scholar
  11. 11.
    Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. 2nd edn. Addison-Wesley, Reading, Mass. (2001)zbMATHGoogle Scholar
  12. 12.
    McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge, Mass. (1971)zbMATHGoogle Scholar
  13. 13.
    Paun, Gh.: On the splicing operation. Discrete Applied Mathematics 70 (1996) 57–79zbMATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Paun, Gh., Rozenberg, G., Salomaa, A.: Computing by splicing. Theoretical Computer Science 168:2 (1996) 321–336zbMATHCrossRefMathSciNetGoogle Scholar
  15. 15.
    Paun, Gh., Rozenberg, G., Salomaa, A.: DNA computing, New Computing Paradigms. Springer-Verlag (1998)Google Scholar
  16. 16.
    Perrin, D.: Finite Automata. In: van Leeuwen, J. (ed.): Handbook of Theoretical Computer Science, Vol. B. Elsevier (1990) 1–57Google Scholar
  17. 17.
    Pixton, D.: Linear and Circular Splicing Systems. In: Proc. of 1st Int. Symp. on Int. in Neural and Biological Systems (1996) 181–188Google Scholar
  18. 18.
    Pixton, D.: Regularity of splicing languages. Discrete Applied Mathematics 69 (1996) 101–124zbMATHCrossRefMathSciNetGoogle Scholar
  19. 19.
    Schützenberger, M.-P.: Sur certaines opérations de fermeture dans le langages rationnels. Symposia Mathematica 15 (1975) 245–253Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Paola Bonizzoni
    • 1
  • Clelia De Felice
    • 2
  • Giancarlo Mauri
    • 1
  • Rosalba Zizza
    • 2
  1. 1.Dipartimento di Informatica Sistemistica e ComunicazioneUniversità degli Studi di Milano - BicoccaMilanoItaly
  2. 2.Dipartimento di Informatica ed ApplicazioniUniversità di SalernoBaronissi (SA)Italy

Personalised recommendations