2020/04/29 by Kingshuk Chatterjee, Chatterjee, Kingshuk, Debayan Ganguly +4
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Artificial intelligence #Automaton #Base pair #Biology #Computer science #DNA #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Genetics #Machine Learning and Algorithms #Mathematical economics #Mathematics #Molecular Structure of Nucleic Acids: A Structure for Deoxyribose Nucleic Acid #Quantum Computing Algorithms and Architecture #State (computer science) #Theoretical computer science #Watson #cs.FL
paper · pdf · doi:10.48550/arxiv.2005.10126
arxiv created 2020/04/29 · openalex publication_date 2020/04/29 · arxiv updated 2020/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Reversible Watson-Crick automata introduced by Chatterjee et.al. is a reversible variant of an Watson-Crick automata. It has already been shown that the addition of DNA properties to reversible automata significantly increases the computational power of the model. In this paper, we analyze the state complexity of Reversible Watson-Crick automata with respect to non-deterministic finite automata. We show that Reversible Watson-Crick automata in spite of being reversible in nature enjoy state complexity advantage over non deterministic finite automata. The result is interesting because conversion from non deterministic to deterministic automata results in exponential blow up of the number of states and classically increase in number of heads of the automata cannot compensate for non-determinism in deterministic and reversible models.