Watson-crick (D)0 L systems: a survey
Tóm tắt
Watson-Crick L systems are string generating formal models obtained by augmenting Lindenmayer systems with the Watson-Crick morphism inspired by the Watson-Crick complementarity principle. The Watson-Crick morphism is controlled by a trigger—a boolean condition eventually met by the generated word. Despite their simplicity, Watson-Crick (D)0 L systems have interesting mathematical properties, a strong generative power, and they can also characterize some open decision problems. Furthermore, networks of Watson-Crick D0L systems are capable of trading space for time, and thus of characterizing linear time solutions to intractable problems. We provide a survey of results in this field since its origin in 1997 to the present, and we conclude with a series of open research problems and ideas.
Tài liệu tham khảo
Csima, J., Csuhaj-Varjú, E., & Salomaa, A. (2003). Power and size of extended Watson-Crick L systems. Theoretical Computer Science, 290(3), 1665–1678.
Csuhaj-Varjú, E.: Watson-Crick complementarity, L systems, computation. In: Durand-Lose, J., Verlan, S. (eds.) Machines, Computations, and Universality: 8th International Conference. Lecture Notes in Computer Science, vol. 10881. Springer, Cham (2018). pp. XI–XII
Csuhaj-Varjú, E. (2000). Computing by networks of standard Watson-Crick D0L systems. In M. Ito (Ed.), Algebraic Systems, Formal Languages and Computations (Vol. 1166, pp. 42–51). Kyoto University, Research Institute for Mathematical Sciences.
Csuhaj-Varjú, E. (2004). Networks of standard Watson-Crick D0L systems with incomplete information communication. In J. Karhumäki, H. Maurer, G. Păun, & G. Rozenberg (Eds.), Theory Is Forever (pp. 35–48). Cham: Springer.
Csuhaj-Varjú, E., Freund, R., & Vaszil, G. (2017). Watson-Crick T0L systems and red-green register machines. Fundamenta Informaticae, 155(1–2), 111–129.
Csuhaj-Varjú, E., Martín-Vide, C., Păun, G., & Salomaa, A. (2003). From Watson-Crick L systems to Darwinian P systems. Natural Computing, 2(3), 299–318.
Csuhaj-Varjú, E., & Salomaa, A. (2003). Networks of Watson-Crick D0L systems. In M. Ito & T. Imaoka (Eds.), Words, Languages & Combinatorics III (pp. 134–150). Singapore: World Scientific.
Csuhaj-Varjú, E., & Salomaa, A. (2003). The power of networks of Watson-Crick D0L systems. In N. Jonoska, G. Păun, & G. Rozenberg (Eds.), Aspects of Molecular Computing (pp. 106–118). Cham: Springer.
Honkala, J. (2003). Decidability results for Watson-Crick D0L systems with nonregular triggers. Theoretical Computer Science, 302(1–3), 481–488.
Honkala, J. (2017). Discrete Watson-Crick dynamical systems. Theoretical Computer Science, 701, 125–131.
Honkala, J., & Salomaa, A. (2001). Watson-Crick D0L systems with regular triggers. Theoretical Computer Science, 259(1–2), 689–698.
Kuich, W., Salomaa, A.: Semirings, Automata, Languages. EATCS monographs on theoretical computer science, vol. 5. Springer, Cham (2012)
Mihalache, V., & Salomaa, A. (1997). Watson-Crick D0L systems. EATCS Bulletin, 62, 160–175.
Mihalache, V., & Salomaa, A. (2001). Language-theoretic aspects of DNA complementarity. Theoretical Computer Science, 250(1–2), 163–178.
Rozenberg, G., & Salomaa, A. (2012). Handbook of Formal Languages. Cham: Springer.
Salomaa, A. (1999). Watson-Crick walks and roads on dol graphs. Acta Cybernetica, 14(1), 179–192.
Salomaa, A. (2002). Uni-transitional Watson-Crick D0L systems. Theoretical Computer Science, 281(1–2), 537–553.
Salomaa, A., & Soittola, M. (2012). Automata-theoretic Aspects of Formal Power Series. Cham: Springer.
Salomaa, A., & Sosík, P. (2003). Watson-Crick D0L systems: the power of one transition. Theoretical Computer Science, 301(1–3), 187–200.
Sears, D., & Salomaa, K. (2012). Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes. Natural Computing, 11(4), 653–664.
Sosík, P.: D0L system + Watson-Crick complementarity = universal computation. In: Machines, Computations, and Universality, Third International Conference. Lecture Notes in Computer Science, vol. 2055, pp. 308–319 (2001). Springer
Sosık, P. (2002). Universal computation with Watson-Crick D0L systems. Theoretical Computer Science, 289(1), 485–501.
Sosík, P. (2003). Watson-Crick D0L systems: generative power and undecidable problems. Theoretical Computer Science, 306(1–3), 101–112.