Multi-head Watson–Crick automata. Issue 2 (2nd April 2016)

• Record Type: Journal Article
• Authors: Chatterjee, Kingshuk; Ray, Kumar Sankar
• Is Part Of: International journal of computer mathematics. Volume 1:Issue 2(2016)
• Page Start: 57
• Page End: 73
• Publication Date: 2016-04-02
• Subjects: Non-deterministic Watson–Crick automata -- deterministic Watson–Crick automata -- parallel communicating Watson–Crick automata systems -- parallel communicating finite automata systems -- multi-head finite automata; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2016.1246477
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: Inspired by multi-head finite automata and Watson–Crick automata, in this paper, we introduce a new structure, namely multi-head Watson–Crick automata, where we replace the single tape of a multi-head finite automaton by a DNA double strand. The content of the second tape is determined using a complementarity relation similar to the Watson–Crick complementarity relation. We establish the superiority of our model over multi-head finite automata and also show that both the deterministic and non-deterministic variants of the model can accept non-regular unary languages. We also compare our model with parallel communicating Watson–Crick automata systems and prove that both of them have the same computational power.