论文标题
可逆Watson-Crick Automata的状态复杂性
State Complexity of Reversible Watson-Crick Automata
论文作者
论文摘要
Chatterjee et.Al引入的可逆Watson-Crick Automata。是Watson-Crick Automata的可逆变体。已经显示，在可逆自动机中添加DNA性能会显着增加模型的计算能力。在本文中，我们分析了可逆的Watson-Crick自动机的状态复杂性相对于非确定性有限自动机的状态复杂性。我们表明，尽管在自然界中可逆，但可逆的沃森 - 克里克自动机与非确定性有限自动机相比，具有国家复杂性优势。结果很有趣，因为从非确定性到确定性自动机的转换导致状态数量的指数爆炸，并且自动机的头部数量通常无法补偿确定性和可逆模型中的非确定性。
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.
