Affiliations: Fachbereich Elektrotechnik/Informatik, Fachgebiet Theoretische Informatik, Universität Kassel, Germany. Peter.Leupold@web.de | Department of Computer Science, Faculty of Informatics, University of Debrecen, 4032 Debrecen, Egyetem tér 1., Hungary. nbenedek@inf.unideb.hu
Note: [] This work was done in part, while Peter Leupold was funded as a post-doctoral fellow by the Japanese Society for the Promotion of Science under grant number P07810, and in part, while he was funded by the Alexander von Humboldt-Stiftung as a return fellow. Address for correspondence: Fachbereich Elektrotechnik/Informatik, Fachgebiet Theoretische Informatik, Universität Kassel, Wilhelmshöher Allee 71–73, 34121 Kassel, Germany
Note: [] This work was done in part during a visit of Benedek Nagy in Kyoto under a project funded by the Hungarian Science and Technology Foundation (TéT) and during a visit in Kassel under a project funded by a bilateral project by the Hungarian Scholarship Board (Balassi Institute) and DAAD; the project is also funded by the National Office for Research and Technology (NKTH), Hungary.
Abstract: 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.
