Watson-Crick T0L Systems and Red-Green Register Machines

• Autorzy: Csuhaj-Varjú E. , Freund R. , Vaszil G.

Identyfikatory

DOI

10.3233/FI-2017-1578

• Języki publikacji: EN

Abstrakty

EN

In this paper we establish a connection between two concepts of unconventional computing, namely Watson-Crick T0L systems (schemes) and red-green Turing machines or redgreen register machines. Our research was inspired by the conceptual similarity of a mind change of a red-green Turing or register machine and of a turn to the complementary string in Watson-Crick T0L systems as well as by the fact that both red-green Turing or register machines and Watson-Crick T0L systems define infinite computations on finite inputs. We define language recognition for Watson-Crick T0L systems based on the infinite sequences they generate, and we show that the sets of (vectors of) natural numbers which can be recognized by so-called standard Watson-Crick T0L schemes (with a context-free trigger) include the sets recognized by red-green register machines (or red-green Turing machines). The obtained results imply that using Watson-Crick T0L schemes we may "go beyond Turing" as the red-green register machines and red-green Turing machines can do. Furthermore, we also show that for any deterministic Watson-Crick 0L scheme with a regular trigger the recognizability problem of a word is decidable.

Słowa kluczowe

EN

complementary relation; mind change; red-green register machines; red-green Turing machines; Watson-Crick T0L systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 1/2
• Strony: 111--129
• Opis fizyczny: Bibliogr. 13 poz., tab.

Twórcy

autor

Csuhaj-Varjú E.

• Department of Algorithms and Their Applications, Eötvös Loránd University Pázmány Péter sétány 1/c, 1117 Budapest, Hungary

autor

Freund R.

• Institut of Computer Languages, Technische Universität Wien Favoritenstrabe 9-11, 1040 Wien, Austria

autor

Vaszil G.

• Department of Computer Science, University of Debrecen Kassaiút 26, 4028 Debrecen, Hungary

Bibliografia

• [1] van Leeuwen J, Wiedermann J. Computation as an unbounded process. Theoretical Computer Science, 2012;429:202–212. URL https://doi.org/10.1016/j.tcs.2011.12.040.
• [2] Aman B, Csuhaj-Varjú E, Freund R. Red-green P automata. In: Gheorghe M, Rozenberg G, Salomaa A, Sosík P, Zandron C (eds.), CMC 2014, volume 8961 of Lecture Notes in Computer Science. Springer, 2014 pp. 139–157. doi:10.1007/978-3-319-14370-5_9.
• [3] Mihalache V, Salomaa A. Language-theoretic aspects of DNA complementarity. Theoretical Computer Science, 2001;250(1-2):163–178. URL https://doi.org/10.1016/S0304-3975(99)00129-2.
• [4] Csima J, Csuhaj-Varjú E, Salomaa A. Power and size of extended Watson-Crick L systems. Theoretical Computer Science, 2003;290(3):1665–1678. URL https://doi.org/10.1016/S0304-3975(02)00074-9.
• [5] Sosík P. Watson-Crick D0L systems: generative power and undecidable problems. Theoretical Computer Science, 2003;306(1-3):101–112. doi:10.1016/S0304-3975(03)00214-7.
• [6] Honkala J, Salomaa A. Watson-Crick D0L systems with regular triggers. Theoretical Computer Science, 2001;259(1-2):689–698. URL https://doi.org/10.1016/S0304-3975(01)00010-X.
• [7] Salomaa A, Sosík P. Watson-Crick D0L systems: the power of one transition. Theoretical Computer Science, 2003;301(1-3):187–200. URL https://doi.org/10.1016/S0304-3975(02)00580-7.
• [8] Salomaa A. Uni-transitional Watson-Crick D0L systems. Theoretical Computer Science, 2002;281(1-2):537–553. URL https://doi.org/10.1016/S0304-3975(02)00026-9.
• [9] Hopcroft JE, Ullman JD. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979. ISBN-10: 0321455363, 13: 978-0321455369.
• [10] Rozenberg G, Salomaa A (eds.). Handbook of Formal Languages. Springer-Verlag, Berlin Heidelberg, 1997. doi:10.1007/978-3-642-59136-5.
• [11] Budnik P. What Is and What Will Be. Mountain Math Software, 2006.
• [12] Staiger L. ω -Computations on Turing machines and the accepted languages. In: Theory of Algorithms, Pécs (Hungary), volume 44 of Colloquia Mathematica Societatis János Bolyai. 1984 pp. 393–403.
• [13] Ginsburg S, Rozenberg G. TOL schemes and control sets. Information and Control, 1975;27(2):109–125. URL https://doi.org/10.1016/S0019-9958(75)90106-0.