A New Sensing 5'–>3' Watson-Crick Automata Concept

Benedek Nagy
(Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University)
Shaghayegh Parchami
(Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University)
Hamid Mir-Mohammad-Sadeghi
(Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University)

Watson-Crick (WK) finite automata are working on a Watson-Crick tape, that is, on a DNA molecule. Therefore, it has two reading heads. While in traditional WK automata both heads read the whole input in the same physical direction, in 5'–>3' WK automata the heads start from the two extremes and read the input in opposite direction. In sensing 5'–>3' WK automata the process on the input is finished when the heads meet. Since the heads of a WK automaton may read longer strings in a transition, in previous models a so-called sensing parameter took care for the proper meeting of the heads (not allowing to read the same positions of the input in the last step). In this paper, a new model is investigated, which works without the sensing parameter (it is done by an appropriate change of the concept of configuration). Consequently, the accepted language classes of the variants are also changed. Various hierarchy results are proven in the paper.

In Erzsébet Csuhaj-Varjú, Pál Dömösi and György Vaszil: Proceedings 15th International Conference on Automata and Formal Languages (AFL 2017), Debrecen, Hungary, September 4-6, 2017, Electronic Proceedings in Theoretical Computer Science 252, pp. 195–204.
Published: 21st August 2017.

ArXived at: http://dx.doi.org/10.4204/EPTCS.252.19 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org