State complexity of deterministic Watson-Crick automata and time varying Watson-Crick automata

摘要

Watson-Crick automata are finite automata working on double strands. Extensive research work has already been done on non-deterministic Watson-Crick automata and on deterministic Watson-Crick automata. State complexity of Watson-Crick automata has also been discussed. In this paper we analyze the state complexity of deterministic Watson-Crick automata with respect to non-deterministic block automata and non-deterministic finite automata. We also introduce new finite automata combining the properties of Watson-Crick automata and time varying automata. These automata have the unique property that the 1-limited stateless variant of these automata have the power to count. We further discuss the state complexity of time varying automata and time varying Watson-Crick automata.