Low Disruption Transformations on Cyclic Automata

• Autorzy: Martin G.M. , Vico F.J. , Dassow J. , Truthe B.
• Języki publikacji: EN

Abstrakty

EN

We extend the edit operators of substitution, deletion, and insertion of a symbol over an word by introducing two new operators (partial copy and partial elimination) inspired by biological gene duplication. We define a disruption measure for an operator over a word and prove that whereas the traditional edit operators are disruptive, partial copy and partial elimination are non-disruptive. Moreover, we show that the application of only edit operators does not generate (with low disruption) all the words over a binary alphabet, but this can indeed be done by combining partial copy and partial elimination with the substitution operator.

Słowa kluczowe

EN

cyclic automata; disruption of the operators

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 1/2
• Strony: 93--110
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Martin G.M.

autor

Vico F.J.

autor

Dassow J.

autor

Truthe B.

• Departamento de Lenguajes y Ciencias de la Computaci´on, Universidad de Malaga, Severo Ochoa, 4, Parque Tecnol´ogico de Andalućýa, E-29590 Campanillas - Malaga, Spain,

Bibliografia

• [1] Alhazov, A., Dassow, J., Martın-Vide, C., Rogozhin, Yu., Truthe, B.: On Networks of Evolutionary Processors with Nodes of Two Types, Fundamenta Informaticae 91 (2009) 1-15.
• [2] Castellanos, J., Mart´ın-Vide, C., Mitrana, V., Sempere, J.: Solving NP-complete Problems with Networks of Evolutionary Processors, Proc. IWANN, Lecture Notes in Computer Science 2084, Springer-Verlag, Berlin, 2001, 621-628.
• [3] Csuhaj-Varj´u, E., Mitrana, V.: Evolutionary Systems: A Language Generating Device Inspired by Evolving Communities of Cells, Acta Inf. 36 (2000) 913-926.
• [4] Dassow, J., Mart´ın, G. M., Vico, F. J.: A Similarity Measure for Cyclic Unary Regular Languages. Fundamenta Informaticae 96 (2009) 71-88.
• [5] Davey, M., Mackay, D.: Reliable Communication over Channels with Insertions, Deletions, and Substitutions, IEEE Transactions on Information Theory 47 (2001) 687-698.
• [6] Gusfield, D., Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York, 1997.
• [7] Jürgensen, H., Konstantinides, S., Error Correction for Channels with Substitutions, Insertions, and Deletions, Lecture Notes in Computer Science 1133, Springer-Verlag, Berlin, 1996, 149-163.
• [8] Messer, P., Arndt, P., Lässig, M., Solvable Sequence Evolution Models and Genomic Correlations, Phys. Rev. Lett. 94(13) (2005) art. no. 138103.
• [9] Ohno, S., Evolution by Gene Duplication. Springer-Verlag, Berlin, 1970.
• [10] Oommen, B., String Alignment with Substitution, Insertion, Deletion, Squashing, and Expansion Operations, Information Sciences 83 (1995) 89-107.
• [11] Oommen, B., Loke, R., Pattern Recognition of Strings with Substitutions, Insertions, Deletions and Generalized Transpositions, Pattern Recognition 30 (1997) 789-800.
• [12] Rozenberg, G., Salomaa, A., Handbook of Formal Languages. Springer-Verlag, Berlin, 1997.
• [13] Saakian, D., Evolution Models with Base Substitutions, Insertions, Deletions, and Selection, Phys. Rev. 78(6) (2008) art. no. 061920.
• [14] Zhang, J., Evolution by Gene Duplication: An Update, Trends in Ecology and Evolution 18 (2003) 292-298.