publication . Preprint . 2015

Multi-head Watson-Crick automata

Chatterjee, Kingshuk; Ray, Kumar Sankar;
Open Access English
  • Published: 14 Oct 2015
Abstract
Inspired by multi-head finite automata and Watson-Crick automata in this paper, we introduce new structure namely multi-head Watson-Crick automata where we replace the single tape of multi-head finite automaton by a DNA double strand. The content of the second tape is determined using a complementarity relation similar to 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 variant 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 t...
Subjects
arXiv: Computer Science::Formal Languages and Automata TheoryQuantitative Biology::BiomoleculesNonlinear Sciences::Cellular Automata and Lattice Gases
ACM Computing Classification System: TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
free text keywords: Computer Science - Formal Languages and Automata Theory
Download from
Any information missing or wrong?Report an Issue