Forbidding and enforcing in membrane computing

Motivated by biochemistry and the non-deterministic reactions between molecules, the authors in (Ehrenfeucht and Rozenberg, 2003) introduced the concept of forbidding-enforcing systems (fe-systems) that define families of languages. Using the same concept we propose to study forbidding and enforcing within membrane systems. Two approaches are presented; in the first case the membrane system generates families of languages and in the second case the membrane system generates a single language. We show that by using forbidding-enforcing in membranes, families of languages that cannot be defined by any fe-system can be generated. When a single language is generated, we show that SAT can be solved in a constant time (at price of using an exponential space). Also we show an example of a context-free language that can be generated without any forbidders. © 2003 Kluwer Academic Publishers.