Operational Semantics and Rewriting Logic in Membrane Computing

The existing results in membrane computing refer mainly to the P systems char-
acterization of Turing computability, and to some polynomial solutions to NP-
complete problems by using an exponential workspace created in a \biological way”.
In this paper we de ne an operational semantics of these P systems, and give a trans-
lation of the operational semantics into rewriting logic. We present some results re-
garding this translation, including an operational correspondence, and discuss why
such a translation is relevant in order to take advantage of good features of both
structural operational semantics and rewriting logic.

Sidebar