RAIRO-Theor. Inf. Appl.
Volume 55, 2021
11th Workshop on Non-classical Models of Automata and Applications (NCMA 2019)
|Number of page(s)||18|
|Published online||22 July 2021|
On deterministic 1-limited 5′ → 3′ sensing Watson–Crick finite-state transducers
Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, Famagusta,
via Mersin-10, Turkey.
2 Department of Computer Science, Faculty of Informatics, University of Debrecen, 4032 Debrecen, Egyetem tér 1., Hungary.
* Corresponding author: firstname.lastname@example.org
Accepted: 25 March 2021
Finite automata and finite state transducers belong to the bases of (theoretical) computer science with many applications. On the other hand, DNA computing and related bio-inspired paradigms are relatively new fields of computing. Watson–Crick automata are in the intersection of the above fields. These finite automata have two reading heads as they read the upper and lower strands of the input DNA molecule, respectively. In 5′ → 3′ Watson–Crick automata the two reading heads move in the same biochemical direction, that is, from the 5′ end of the strand to the direction of the 3′ end. However, in the double-stranded DNA, the DNA strands are directed in opposite way to each other, therefore 5′ → 3′ Watson–Crick automata read the input from the two extremes. In sensing 5′ → 3′ automata the automata sense if the two heads are at the same position, moreover, the computing process is finished at that time. Based on this class of automata, we define WK transducers such that, at each transition, exactly one input letter is being processed, and exactly one output letter is written on a normal output tape. Some special cases are defined and analyzed, e.g., when only one of the reading heads is being used and when the transducer has only one state. We also show that the minimal transducer is uniquely defined if the transducer is deterministic and it has marked output, i.e., the output letter written in a step identifies the reading head that is used in that transition. We have also used the functions ‘processing order’ and ‘reading heads’ to analyze these transducers.
Mathematics Subject Classification: 68Q45
Key words: Watson–Crick transducers / 5′ → 3′ WK automata / Sensing WK automata / Finite state transducers
© The authors. Published by EDP Sciences, 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.