CONTEXTUAL INSERTIONS DELETIONS AND COMPUTABILITY/

We investigate two generalizations of insertion and deletion of words, that have recently become of interest in the context of molecular com puting. Given a pair of words (x, y), called a context, the (x, y)-con textual insertion of a word v into a word u is performed as follows. F or each occurrence of xy as a subword in u, we include in the result o f the contextual insertion the words obtained by inserting v into u, b etween x and y. The (x, y)-contextual deletion operation is defined in a similar way. We study closure properties of the Chomsky families un der the defined operations, contextual ins-closed and del-closed langu ages, and decidability of existence of solutions to equations involvin g these operations. Moreover, we prove that every Turing machine can b e simulated by a system based entirely on contextual insertions and de letions. (C) 1996 Academic Press.