On Deterministic 1-Limited 5′ → 3′ Sensing Watson–Crick Finite-State Transducers

Nagy, Benedek; Kovács, Zita

RAIRO. Theoretical Informatics and Applications, Tome 55 (2021), article no. 5

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.

Classification : 68Q45
Keywords: Watson–Crick transducers, 5′ → 3′ WK automata, Sensing WK automata, Finite state transducers

[1] R. Alur and P. Cerný, Expressiveness of streaming string transducers, in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15–18, 2010, Chennai, India (2010) 1–12. | Zbl

[2] M. Cavaliere, Computing by observing: A brief survey, in Logic and Theory of Algorithms, 4th Conference on Computability in Europe, CiE 2008, Athens, Greece, June 15-20, 2008, Proceedings (2008) 110–119. | MR | Zbl

[3] E. Czeizler, E. Czeizler, L. Kari and K. Salomaa, Watson-Crick automata: determinism and state complexity, in 10th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2008, Charlottetown, Prince Edward Island, Canada, July 16–18, 2008, edited by C. Câmpeanu and G. Pighizzini. University of Prince Edward Island (2008) 121–133.

[4] R. Freund, Gh. Păun, G. Rozenberg and A. Salomaa, Watson-Crick finite automata, in DNA Based Computers, Proceedings of a DIMACS Workshop, Philadelphia, Pennsylvania, USA, June 23-25, 1997 (1997) 297–328. | MR | Zbl

[5] M. A. Harrison, Introduction to Formal Language Theory. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st ed. (1978). | MR | Zbl

[6] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979). | MR | Zbl

[7] R. Kocman, B. Nagy, Z. Krivka and A. Meduna, A jumping $5^{\text{'}}\to 3^{\text{'}}$ Watson-Crick finite automata model, in Tenth Workshop on Non-Classical Models of Automata and Applications, NCMA 2018, Košice, Slovakia, August 21-22, 2018 (2018) 117–132. | MR | Zbl

[8] P. Leupold and B. Nagy, $5^{\text{'}}\to 3^{\text{'}}$ Watson-Crick automata with several runs, in Workshop on Non-Classical Models for Automata and Applications – NCMA 2009, Wroclaw, Poland, August 31–September 1, 2009. Proceedings (2009) 167–180. | MR | Zbl

[9] P. Leupold and B. Nagy, $5^{\text{'}}\to 3^{\text{'}}$ Watson-Crick automata with several runs. Fundam. Inform. 104 (2010) 71–91. | MR | Zbl | DOI

[10] R. Loukanova, Linear context free languages, in ICTAC 2007, Proc., edited by C. Jones, Z. Liu and J. Woodcock. Vol. 4711 of LNCS. Springer, Heidelberg (2007) 351–365. | Zbl

[11] G. H. Mealy, A method for synthesizing sequential circuits. Bell Syst. Tech. J. 34 (1955) 1045–1079. | MR | DOI

[12] B. Nagy, On $5^{\text{'}}\to 3^{\text{'}}$ sensing Watson-Crick finite automata, in DNA Computing, 13th International Meeting on DNA Computing, DNA13, Memphis, TN, USA, June 4–8, 2007, Revised Selected Papers, Lecture Notes in Computer Science 4848, Heidelberg. Springer (2008) 256–262. | Zbl

[13] B. Nagy, On a hierarchy of $5^{\text{'}}\to 3^{\text{'}}$ sensing WK finite automata languages, in CiE 2009, Computability in Europe 2009: Mathematical Theory and Computational Practice, Abstract Booklet, University of Heidelberg, Germany (2009) 266–275.

[14] B. Nagy, A class of 2-head finite automata for linear languages. Triangle 8 (2012) 89–99.

[15] B. Nagy, On a hierarchy of $5^{\text{'}}\to 3^{\text{'}}$ sensing Watson-Crick finite automata languages. J. Log. Comput. 23 (2013) 855–872. | MR | Zbl | DOI

[16] B. Nagy, $5^{\text{'}}\to 3^{\text{'}}$ Watson-Crick pushdown automata. Inf. Sci. 537 (2020) 452–466. | MR | Zbl | DOI

[17] B. Nagy and Z. Kovács, On simple $5^{\text{'}}\to 3^{\text{'}}$ sensing Watson-Crick finite-state transducers, in Eleventh Workshop on Non-Classical Models of Automata and Applications, NCMA 2019, Valencia, Spain, July 2-3, 2019 (2019) 155–170.

[18] B. Nagy and F. Otto, Two-head finite-state acceptors with translucent letters, in SOFSEM 2019, Proc., edited by B. Catania, R. Královič, J. Nawrocki and G. Pighizzini. Lecture Notes in Computer Science 11376, Springer, Heidelberg (2019) 406–418. | MR | Zbl

[19] B. Nagy and F. Otto, Linear automata with translucent letters and linear context-free trace languages. RAIRO-ITA: Theor. Inf. Appl. 54 (2020) 3. | MR | Zbl | Numdam

[20] B. Nagy and S. Parchami, On deterministic sensing $5^{\text{'}}\to 3^{\text{'}}$ Watson-Crick finite automata – a full hierarchy in 2detLIN. Acta Inf . 58 (2021) 153–175. | MR | Zbl | DOI

[21] B. Nagy, S. Parchami and H. M. M. Sadeghi, A new sensing $5^{\text{'}}\to 3^{\text{'}}$ Watson-Crick automata concept, in Proceedings 15th International Conference on Automata and Formal Languages, AFL 2017, Debrecen, Hungary, September 4 -6, 2017., EPTCS 252 (2017) 195–204. | MR | Zbl

[22] S. Parchami and B. Nagy, Deterministic sensing $5^{\text{'}}\to 3^{\text{'}}$ Watson-Crick automata without sensing parameter, in Unconventional Computation and Natural Computation – 17th International Conference, UCNC 2018, Fontainebleau, France, June 25–29, 2018, Proceedings. Lecture Notes in Computer Science 10867. Springer, Heidelberg (2018) 173–187. | MR | Zbl

[23] Gh. Păun, G. Rozenberg and A. Salomaa, DNA Computing – New Computing Paradigms, Texts in Theoretical Computer Science. An EATCS Series. Springer (1998). | Zbl | MR

[24] G. Rozenberg and A. Salomaa (Eds.), Handbook of Formal Languages, Volume 1: Word, Language, Grammar. Springer (1997). | Zbl

[25] J. M. Sempere, A note on the equivalence and complexity of linear grammars. Grammars 6 (2003) 115–126. | MR | Zbl | DOI

[26] J. M. Sempere, A representation theorem for languages accepted by Watson-Crick finite automata. Bull. EATCS 83 (2004) 187–191. | MR | Zbl

[27] S. Yu, Regular languages, in Handbook of Formal Languages, Volume 1: Word, Language, Grammar, edited by G. Rozenberg and A. Salomaa. Springer (1997) 41–110. | MR | DOI