Forbidding–enforcing systems

AbstractThis paper presents a model of molecular computing that is based on two kinds of “boundary conditions”: forbidding and enforcing. Forbidding conditions require that a contradictory (or conflicting) group of components (molecules) may not be present in a (molecular) system, as otherwise the system will “die”. An enforcing condition requires that if a certain group of components (molecules) is present in a system, then eventually other components will be present in the system—hence such an enforcing condition models a molecular reaction. Thus the evolution of a system is determined by the enforcing conditions, but it is constraint by the forbidding conditions. Such forbidding–enforcing systems (fe systems) are investigated in this paper in the framework of strings—i.e., molecules are represented by strings. Each fe system defines a family of languages (rather than just one language, which is standard in formal language theory)—each language in this family presents a set of molecules that satisfy both forbidding and enforcing constraints. In this paper we investigate basic computational properties of fe systems operating on strings