5'→3' Watson-Crick AutomataWith Several Runs

• Autorzy: Leupold P. , Nagy B.
• Języki publikacji: EN

Abstrakty

EN

5'→3' WK-automata are Watson-Crick automata whose two heads start on opposite ends of the input word and always run in opposite directions. One full reading in both directions is called a run. We prove that the expressive power of these automata increases with every additional run that they can make, both for deterministic and non-deterministic machines. This defines two incomparable infinite hierarchies of language classes between the regular and the context-sensitive languages. These hierarchies are complemented with classes defined by several restricted variants of 5'→3' WK-automata like stateless automata. Finally we show that several standard problems are undecidable for languages accepted by 5'→3' WK-automata in only one run, for example the emptiness and the finiteness problems.

Słowa kluczowe

EN

automata; formal languages; natural computing; Watson-Crick automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 1/2
• Strony: 71--91
• Opis fizyczny: Bibliogr. 13 poz., wykr.

Twórcy

autor

Leupold P.

autor

Nagy B.

• Fachbereich Elektrotechnik/Informatik, Fachgebiet Theoretische Informatik, Universität Kassel, Wilhelmshöher Allee 71–73, 34121 Kassel, Germany,

Bibliografia

• [1] Dassow, J., Mitrana, V., Salomaa, A.: Operations and language generating devices suggested by the genome evolution, Theoretical Computer Science, 270(1-2), 2002, 701-738.
• [2] Freund, R., P˘aun, G., Rozenberg, G., Salomaa, A.: Watson-Crick Finite Automata, Proceedings of the Third Annual DIMACS Symposium on DNA Based Computers, Philadelphia, 1994, 535-546.
• [3] Frisco, P., Ibarra, O. H.: On Stateless Multihead Finite Automata and Multihead Pushdown Automata, Developments in Language Theory (V. Diekert, D. Nowotka, Eds.), LNCS 5583, Springer, 2009, 240-251.
• [4] Harrison, M. A.: Introduction to Formal Language Theory, Addison-Wesley, Reading, Massachusetts, 1978.
• [5] Ibarra, O. H.: On Two-way Multihead Automata, Journal of Computer and System Sciences, 7(1), 1973, 28-36.
• [6] Kuske, D., Weigel, P.: The Role of the Complementarity Relation in Watson-Crick Automata and Sticker Systems, Developments in Language Theory (C. Calude, E. Calude, M. J. Dinneen, Eds.), LNCS 3340, Springer, 2004, 272-283.
• [7] Leupold, P., Nagy, B.: 5′ → 3′ Watson-Crick Automata with Several Runs, Non-Classical Models of Automata and Applications (NCMA) (H. Bordihn, R. Freund, M. Holzer, M. Kutrib, F. Otto, Eds.), Österreichische Computergesellschaft, [e-mail] Series, vol. 256, Wien, 2009, 167-180.
• [8] Monien B.: Two-way multihead automata over a one-letter alphabet, RAIRO Informatique Th´eorique et Applications, 14, 1980, 67-82.
• [9] Nagy, B.: On 5′ → 3′ Sensing Watson-Crick Finite Automata, DNA (M. H. Garzon, H. Yan, Eds.), LNCS 4848, Springer, 2007, 256-262.
• [10] Nagy, B.: On a Hierarchy of 5′ → 3′ Sensing WK Finite Automata Languages, Mathematical Theory and Computational Practice, CiE, Abstract Booklet, University of Heidelberg, 2009, 266-275.
• [11] Pǎun, G.: DNA Computing by Matching: Sticker Systems andWatson-Crick Automata, Pattern Formation in Biology, Vision and Dynamics (A. Carbone, M. Gromov, P. Prusinkiewicz, Eds.),World Scientific, Singapore, 2000, 336-362.
• [12] Pǎun, G., Rozenberg, G., Salomaa, A.: DNA Computing - New Computing Paradigms, Springer-Verlag, Berlin Heidelberg, 1998.
• [13] Salomaa, A.: Formal Languages, Academic Press, New York, 1973.