A logical analysis of string manipulation systems is presented that provide
s a unification of many formalisms and suggests a framework for the investi
gation of complex discrete dynamics. Namely, several characterizations of c
omputational universality are given in terms of logical representability wi
thin models and theories; moreover, combinatorial schemata, as a formal cou
nterpart of DNA basic recombinant mechanisms, are logically expressed. In t
his way a general definition of derivation systems is given to which many c
lassical systems can be easily reduced, and where some regulation mechanism
s can be naturally represented. As a further consequence, systematic method
s are provided for translating derivation systems into monoidal theories. F
inally, new possibilities of this logical approach are outlined in the form
alization of molecule manipulation systems inspired by chemical and biochem
ical processes. (C) 2001 Elsevier Science B.V. All rights reserved.