Recombinant DNA ,Gene Splicing as Generative Devices of Formal Languages

1. Berstel, J., Perrin, D.: Theory of Codes. Academic Press, New York (1985)

   MATH  Google Scholar 

2. Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R.: Linear splicing and syntactic monoid (2004) (submitted)

   Google Scholar 

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. LNCS, vol. 2450, pp. 78–92. Springer, Heidelberg (2003)

   Chapter  Google Scholar 

4. Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R.: Regular languages generated by reflexive finite linear splicing systems. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 134–145. Springer, Heidelberg (2003)

   Chapter  Google Scholar 

5. Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R.: DNA and circular splicing. In: Condon, A., Rozenberg, G. (eds.) DNA 2000. LNCS, vol. 2054, pp. 117–129. Springer, Heidelberg (2001)

   Chapter  Google Scholar 

6. Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R.: Circular splicing and regularity. Theoretical Informatics and Appl. 38, 189–228 (2004)

   Article  MATH  MathSciNet  Google Scholar 

7. Bonizzoni, P., De Felice, C., Mauri, G., Zizza, R.: On the power of circular splicing (2004) (submitted)

   Google Scholar 

8. Bonizzoni, P., De Felice, C., Zizza, R.: The structure of reflexive regular splicing languages via Schützenberger constants. Theoretical Computer Science (2004) (to appear)

   Google Scholar 

9. Bonizzoni, P., Ferretti, C., Mauri, G., Zizza, R.: Separating some splicing models. Information Processing Letters 76(6), 255–259 (2001)

   Article  MathSciNet  Google Scholar 

10. Bonizzoni, P., Mauri, G.: Regular splicing languages and subclasses. Theoretical Computer Science (2004) (to appear)

    Google Scholar 

11. Culik, K., Harju, T.: Splicing semigroups of dominoes and DNA. Discrete Applied Math. 31, 261–277 (1991)

    Article  MATH  MathSciNet  Google Scholar 

12. Fagnot, I.: Splicing Systems and Chomsky hierarchy. In: Proc. of Journees Montoises 2004, Lieges, Belgium (2004)

    Google Scholar 

13. Laun, E.G.: Constants and splicing systems, PHD Thesis, Binghamton University (1999)

    Google Scholar 

14. Goode, E., Pixton, D.: Recognizing splicing languages: syntactic monoids and simultaneous pumping (2004) (submitted), available from http://www.math.binghamton.edu/dennis/Papers/index.html

15. Head, T.: Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviours. Bull. Math. Biol. 49, 737–759 (1987)

    MATH  MathSciNet  Google Scholar 

16. Head, T.: Splicing languages generated with one sided context. In: Paun, G. (ed.) Computing with bio-molecules: theory and experiments. Springer, Heidelberg (1998)

    Google Scholar 

17. Head, T., Paun, G., 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, pp. 295–360. Springer, Heidelberg (1996)

    Google Scholar 

18. Harrison, M.A.: Introduction to Formal Language Theory. Addison-Wesley, Reading (1978)

    MATH  Google Scholar 

19. Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (2001)

    MATH  Google Scholar 

20. Kim, S.M.: An algorithm for identifying spliced languages. In: Jiang, T., Lee, D.T. (eds.) COCOON 1997. LNCS, vol. 1276, pp. 403–411. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

21. Kim, S.M.: Computational modeling for genetic splicing systems. SIAM Journal of Computing 26, 1284–1309 (1997)

    Article  MATH  Google Scholar 

22. McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press, Cambridge (1971)

    MATH  Google Scholar 

23. Paun, G.: On the splicing operation. Discrete Applied Math. 70, 57–79 (1996)

    Article  MATH  MathSciNet  Google Scholar 

24. Paun, G., Rozenberg, G., Salomaa, A.: DNA computing, New Computing Paradigms. Springer, Heidelberg (1998)

    MATH  Google Scholar 

25. Perrin, D.: Finite Automata. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 1–57. Elsevier, Amsterdam (1990)

    Google Scholar 

26. Pixton, D.: Linear and circular splicing systems. In: Proc. of 1st Int. Symp. on Intelligence in Neural and Biological Systems, pp. 181–188. IEEE Computer Society Press, Los Alamitos (1996), Silver Spring

    Google Scholar 

27. Pixton, D.: Regularity of splicing languages. Discrete Applied Math. 69, 101–124 (1996)

    Article  MATH  MathSciNet  Google Scholar 

28. Schützenberger, M.P.: Sur certaines opérations de fermeture dans les langages rationnels. Symposia Mathematica 15, 245–253 (1975)

    Google Scholar 

29. Verlan, S., Zizza, R.: 1–splicing vs. 2–splicing: separating results. In: Proc. of Words 2003, Turku, Finland, pp. 320–331 (2003)

    Google Scholar 

Download references