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.