Coding properties of DNA languages. (English) Zbl 1044.68095
Summary: The computation language of a DNA-based system consists of all the words (DNA strands) that can appear in any computation step of the system. In this work we define properties of languages which ensure that the words of such languages will not form undesirable bonds when used in DNA computations. We give several characterizations of the desired properties and provide methods for obtaining languages with such properties. The decidability of these properties is addressed as well. As an application we consider splicing systems whose computation language is free of certain undesirable bonds and is generated by nearly optimal comma-free codes.
MSC:
| 68Q45 | Formal languages and automata |
References:
| [1] | J. Berstel, D. Perrin, Theory of Codes, Academic Press, Inc., Orlando, FL. 1985.; J. Berstel, D. Perrin, Theory of Codes, Academic Press, Inc., Orlando, FL. 1985. · Zbl 0587.68066 |
| [2] | R. Deaton, M. Garzon, R. Murphy, D.R. Franceschetti, S.E. Stevens, Genetic search of reliable encodings for DNA-based computation, First Conference on Genetic Programming GP-96, Stanford University, 1996, pp. 9-15.; R. Deaton, M. Garzon, R. Murphy, D.R. Franceschetti, S.E. Stevens, Genetic search of reliable encodings for DNA-based computation, First Conference on Genetic Programming GP-96, Stanford University, 1996, pp. 9-15. |
| [3] | Deaton, R.; Murphy, R.; Garzon, M.; Franceschetti, D. R.; Stevens, S. E., Good encodings for DNA-based solutions to combinatorial problems. DNA-based computers II, (Landweber, L. F.; Baum, E., AMS DIMACS Series, Vol. 44 (1998), American Mathematical Society: American Mathematical Society Providence, RI), 247-258 · Zbl 0919.68044 |
| [4] | M. Garzon, R. Deaton, P. Neathery, D.R. Franceschetti, R.C. Murphy, A new metric for DNA computing, Proc. Second Genetic Programming Conf., Morgan-Kaufmann, Stanford, CA, 1997, pp. 472-478.; M. Garzon, R. Deaton, P. Neathery, D.R. Franceschetti, R.C. Murphy, A new metric for DNA computing, Proc. Second Genetic Programming Conf., Morgan-Kaufmann, Stanford, CA, 1997, pp. 472-478. |
| [5] | M. Garzon, R. Deaton, L.F. Nino, S.E. Stevens Jr., M. Wittner, Genome encoding for DNA computing, Proc. Third Genetic Programming Conf., Madison, WI, 1998, pp. 684-690.; M. Garzon, R. Deaton, L.F. Nino, S.E. Stevens Jr., M. Wittner, Genome encoding for DNA computing, Proc. Third Genetic Programming Conf., Madison, WI, 1998, pp. 684-690. |
| [6] | Harju, T.; Karhumäki, J., Morphisms, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, Vol. 1 (1997), Springer: Springer Berlin), 439-510 · Zbl 0866.68057 |
| [7] | Head, T., Formal language theory and DNAan analysis of the generative capacity of recombinant behaviors, Bull. Math. Biol., 49, 737-759 (1987) · Zbl 0655.92008 |
| [8] | Jürgensen, H.; Konstantinidis, S., Codes, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, Vol. 1 (1997), Springer: Springer Berlin), 511-607 · Zbl 0790.94008 |
| [9] | L. Kari, DNA computing: arrival of biological mathematics, in: The Mathematical Intelligencer, Vol. 19(2), Springer, Berlin, 1997, pp. 9-22.; L. Kari, DNA computing: arrival of biological mathematics, in: The Mathematical Intelligencer, Vol. 19(2), Springer, Berlin, 1997, pp. 9-22. · Zbl 0942.68562 |
| [10] | L. Kari, R. Kitto, G. Thierrin, Codes, involutions and DNA encoding, in: W. Baver, H. Ehrig, J. Karhumäki, A. Salomaa (Eds.), Formal and Natural Computing Lecture Notes in Computer Science 2300 (2002) 376-393.; L. Kari, R. Kitto, G. Thierrin, Codes, involutions and DNA encoding, in: W. Baver, H. Ehrig, J. Karhumäki, A. Salomaa (Eds.), Formal and Natural Computing Lecture Notes in Computer Science 2300 (2002) 376-393. · Zbl 1060.68600 |
| [11] | Marathe, A.; Condon, A.; Corn, R., On combinatorial DNA word design, DNA based Computers V, (Winfree, E.; Gifford, D., DIMACS Series (2000), American Mathematical Society Press: American Mathematical Society Press Providence, RI), 75-89 · Zbl 0969.68070 |
| [12] | Paun, G.; Rozenberg, G.; Salomaa, A., DNA ComputingNew Computing Pradigms (1998), Springer: Springer Berlin · Zbl 0940.68053 |
| [13] | Shyr, H. J., Free Monoids and Languages (1991), Hon Min Book Company, Taichung: Hon Min Book Company, Taichung Taiwan, Republic of China · Zbl 0746.20050 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
