Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Non-regular unary language and parallel communicating Watson-Crick automata systems
Chatterjee K., Ray K.  Theoretical Computer Science 705  113-117, 2018. Type: Article
Date Reviewed: Feb 22 2018

Watson-Crick finite automata have been introduced as a possible model of DNA computation. They differ from their classical counterpart in that they are capable of working on double-stranded sequences. The strands are processed by two independent heads of the automaton. The movement of the heads is controlled by a single state. The characters that appear “on the corresponding positions of the two strands are connected by a complementarity relation” similar to the Watson-Crick complementarity of DNA nucleotides (Watson-Crick base pairings).

In [1], the authors emphasized that “the high hopes for the future of DNA computing are based on two fundamental features: (i) the massive parallelism of DNA strands, [and] (ii) Watson-Crick complementarity.” In an attempt to combine these two features into a DNA computing model, instead of using a single Watson-Crick finite automaton, Czeizler and Czeizler, in [2], proposed to consider “a set of Watson-Crick finite automata working independently on their own input tapes” (the input is the same on all of those tapes) and communicating with each other by special states on request. The combination is known as parallel communicating Watson-Crick automata systems.

These systems turned out to be more powerful than parallel communicating finite automata. They recognize all languages accepted by the latter and also some others, such as a non-regular unary language L={ an2 | n ≥ 2 }. In particular, in [3], it was proved that L is “accepted by a parallel communicating Watson-Crick automata [having] three components and a non-injective complementarity relation.”

This paper offers an improvement of that result. The authors show that parallel communicating Watson-Crick automata systems with just two components and a non-injective complementarity relation are powerful enough to accept L. Furthermore, they also prove that one component only is not sufficient to accept a unary non-regular language.

This short paper proves an interesting technical result. It would have been good if more general context and the importance of the result were also discussed.

Reviewer:  Temur Kutsia Review #: CR145874 (1805-0233)
1) Paun, G.; Rozenberg, G.; Salomaa, A. DNA computing: new computing paradigms. Springer, Berlin, 1998.
2) Czeizler, E.; Czeizler, E. Parallel communicating Watson-Crick automata systems. Acta Cybernetica 17, 4(2006), 685–700.
3) Czeizler, E.; Czeizler, E. On the power of parallel communicating Watson-Crick automata systems. Theoretical Computer Science 358, 1(2006), 142–147.
Bookmark and Share
  Editor Recommended
Automata (F.1.1 ... )
Would you recommend this review?
Other reviews under "Automata": Date
Regular language representations in the constructive type theory of Coq
Doczkal C., Smolka G.  Journal of Automated Reasoning 61(1-4): 521-553, 2018. Type: Article
Aug 16 2018
Languages with membership determined by single letter factors
Higgins P., Alwan S.  Theoretical Computer Science 680 15-24, 2017. Type: Article
Mar 8 2018
Link prediction in fuzzy social networks using distributed learning automata
Moradabadi B., Meybodi M.  Applied Intelligence 47(3): 837-849, 2017. Type: Article
Nov 28 2017

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2018 ThinkLoud, Inc.
Terms of Use
| Privacy Policy