Abstract: A Watson-Crick automaton is recently introduced as a
computational model of DNA computing framework. It works on
tapes consisting of double stranded sequences of symbols. Symbols
placed on the corresponding cells of the double-stranded sequences are
related by a complimentary relation. In this paper, we investigate a
variation of Watson-Crick automata in which both heads read the tape
in reverse directions. They are called reverse Watson-Crick finite
automata (RWKFA). We show that all of following four classes, i.e.,
simple, 1-limited, all-final, all-final and simple, are equal to
non-restricted version of RWKFA.
Abstract: This paper presents a formalisation of the different existing code mutation techniques (polymorphism and metamorphism) by means of formal grammars. While very few theoretical results are known about the detection complexity of viral mutation techniques, we exhaustively address this critical issue by considering the Chomsky classification of formal grammars. This enables us to determine which family of code mutation techniques are likely to be detected or on the contrary are bound to remain undetected. As an illustration we then present, on a formal basis, a proof-of-concept metamorphic mutation engine denoted PB MOT, whose detection has been proven to be undecidable.