A New Sensing 5'–>3' Watson-Crick Automata Concept
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 extr...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2017-08-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1708.06469v1 |
| _version_ | 1818018031556624384 |
|---|---|
| author | Benedek Nagy Shaghayegh Parchami Hamid Mir-Mohammad-Sadeghi |
| author_facet | Benedek Nagy Shaghayegh Parchami Hamid Mir-Mohammad-Sadeghi |
| author_sort | Benedek Nagy |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-14T07:33:56Z |
| format | Article |
| id | doaj.art-61b06c6f2a9740e39aed5f25afa3d887 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-14T07:33:56Z |
| publishDate | 2017-08-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-61b06c6f2a9740e39aed5f25afa3d8872022-12-22T02:05:44ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802017-08-01252Proc. AFL 201719520410.4204/EPTCS.252.19:21A New Sensing 5'–>3' Watson-Crick Automata ConceptBenedek Nagy0Shaghayegh Parchami1Hamid Mir-Mohammad-Sadeghi2 Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University 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.http://arxiv.org/pdf/1708.06469v1 |
| spellingShingle | Benedek Nagy Shaghayegh Parchami Hamid Mir-Mohammad-Sadeghi A New Sensing 5'–>3' Watson-Crick Automata Concept Electronic Proceedings in Theoretical Computer Science |
| title | A New Sensing 5'–>3' Watson-Crick Automata Concept |
| title_full | A New Sensing 5'–>3' Watson-Crick Automata Concept |
| title_fullStr | A New Sensing 5'–>3' Watson-Crick Automata Concept |
| title_full_unstemmed | A New Sensing 5'–>3' Watson-Crick Automata Concept |
| title_short | A New Sensing 5'–>3' Watson-Crick Automata Concept |
| title_sort | new sensing 5 3 watson crick automata concept |
| url | http://arxiv.org/pdf/1708.06469v1 |
| work_keys_str_mv | AT benedeknagy anewsensing53watsoncrickautomataconcept AT shaghayeghparchami anewsensing53watsoncrickautomataconcept AT hamidmirmohammadsadeghi anewsensing53watsoncrickautomataconcept AT benedeknagy newsensing53watsoncrickautomataconcept AT shaghayeghparchami newsensing53watsoncrickautomataconcept AT hamidmirmohammadsadeghi newsensing53watsoncrickautomataconcept |