Talk:Computational Aspects of Mobile Membranes, Brane Calculi and Mobile Ambients

WE ARE GRATEFUL TO THE REVIEWERS FOR THEIR USEFUL COMMENTS AND SUGGESTIONS. THIS WORK WAS PARTIALLY SUPPORTED BY CNCSIS PROJECT IDEI 402/2007 AND POSDRU/89/1.5/S/49944.

Scholarpedia Review

Summary: the article attempts to provide an overview of the computational aspects of mobile membranes, and the relationship between mobile membranes and other related formal calculi. The article is written by two accomplished researchers in the field and is of a high quality. Copious references are provided, including references to many of the major publications in the field. The quality of English, and the structure of the article, is very good.

Suggested changes: My suggested changes are minor, mostly focussed on the typography of the article, reflecting the technical soundness of the article's content:

 * The first use of "Mobile ambients" in the section entitled "Mobile ambients" is not hyperlinked nor
   bolded.  Compare this to the second and third uses of the term in the same section, which are linked,
   albeit to a non-existent article.  The term need only be linked once, on the first occurence.

WE HAVE MODIFIED ACCORDING TO THE REMARK.

 * Similarly, it may be nice to highlight the most important definitions in a section, in order to draw
   the eye toward them, using bolding.  That is, bold the first occurrences of "Mobile ambients",
   "Safe ambients", etc. and throughout the rest of the article.

WE HAVE MODIFIED ACCORDING TO THE REMARK.

 * The BNF grammar for "Processes" isn't at first clear, as the same glyph ($\mid$) is used both as a
   part of the grammar of processes (A | B) and also as a means of defining a BNF.  Things would be made
   clearer by tightening the spacing in A | B.

WE HAVE MODIFIED ACCORDING TO THE REMARK.

 * There are several technical terms used in the article that should probably have a dedicated Scholarpedia
   page for them.  For instance, "operational semantics", "Bioambients", "endocytosis", "monoid" etc.
   Making the first use of these terms a Wikilink will reflect the fact that these pages are missing.

WE HAVE MODIFIED ACCORDING TO THE REMARK.

 * The passage "imagine that the original membrane buckles towards inside and pinches off." sounds awkward.
   Replace with "imagine that the original membrane buckles in and then pinches off."

WE HAVE MODIFIED ACCORDING TO THE REMARK.

 * "It proceeds by the Q membrane wrapping around the P membrane and joining itself on the other side." is
   better stated "It proceeds by the Q membrane wrapping around the P membrane and then joining back onto
   itself on the other side."

WE HAVE MODIFIED ACCORDING TO THE REMARK.

 * "Mobile membranes represents a formalism which describes the movement of membranes inside a spatial
   structure by applying rules from a given set of rules." is better stated "Mobile membranes represent
   a formalism describing the movement of membranes inside a spatial structure by applying rules from a
   given set."

WE HAVE MODIFIED ACCORDING TO THE REMARK.

 * There is inconsistent capitalisation of the rule names used in the article.  For instance, in the
   section entitled "Embedding Brane Calculi into Mobile Membranes" the rules Pino, etc. are capitalised,
   whereas in other sections, rule names are left in all lower case.

WE HAVE MODIFIED ACCORDING TO THE REMARK.

This article discusses two classes of models of hierarchical calculi that, in recent years, have been used in computational systems biology to model compartmentalized biological systems.

The first class contains ambient and Brane calculi. These are process calculi developed to model computational processes where the space of computation is organized as an hierarchy of physical locations called ambients that can change their position during the computations. As all process algebras, these calculi are based on a set of processes with two orthogonal structures: an algebraic structure that encodes the compositionality features of processes and a coalgebraic structure that encodes their behavior. Both structures are described by appropriate functors with a “synchronized effect” guaranteed by the structural operational semantics (SOS): the behavior of an algebraic combination of processes is defined by the algebraic combination of behaviours of the components. This elegant mathematical structure (called bialgebra) guarantees the success of process algebras mainly due to the structural similarity with programming languages. In this field, the main issues are related to bisimulation and congruences that can be defined on processes.

The second class of models contains P-systems. These are computational models that build on automata theory and formal languages to explicitly encode space in the form of containment. The research in this field is focused mainly on complexity and computability aspects of systems. These models have also been used for modeling in systems biology. Given the semantic similarities between P-systems and ambient calculi, it is natural to consider the relation between the two paradigms.

The authors of this article have introduced a new calculus, called mobile membranes, that combines features of the two paradigms. The systems are defined as an algebra endowed with an equational theory of structural congruence, while the behaviour is defined by the kind of rewriting rules used in P-systems combined with rules similar to those of SOS formats. In effect, they obtain a hybrid mathematical structure for their calculus that is neither a bialgebra nor a rewriting system.

The authors compare mobile membranes and Brane Calculus from a semantic perspective. Below are some technical suggestions. However, I also feel that the article would benefit from a careful adjusting of the style of English and an extention of the bibliography to include some of the relevant papers currently missing (see the comments bellow).

In general, I feel that the article would be improved if the concepts involved are better explained. The first phrase, for instance, “Mobile ambients represent a formalism introduced in [9] to describe the movement of processes and devices” is too vague. Please explain what “processes” and “devices” mean.

BY REMOVING THE SYNTAX OF AMBIENT CALCULUS, I HAVE ALSO REMOVED THIS PHRASE.

You present the syntax of ambient calculus and no operational semantics for it. Please add the SOS or remove the syntax which, as it is, has no meaning. However, you have a complete description of the syntax and SOS for safe ambients in the next paragraph which seems to be the one you need.

WE HAVE REMOVED THE SYNTAX FOR AMBIENT CALCULUS.

In the definition of safe ambients, when you introduce the parallel operator, you use "A|B" instead of "A|A" and this is not the correct BNF form.

WE HAVE MODIFIED ALL DEFINITIONS TO BE IN BNF FORM.

Please extend the bibliography to include relevant titles on process algebra side. The paper by Danos and Pradalier “Projective Brane Calculi”, for instance, is an important paper on this subject. I want also to remind you that, historically speaking, there was an intermediate step between Ambient Calculus and Brane calculus: BioAmbients, with a significant number of papers. Moreover, there was a reason for which people moved from Ambients to BioAmbients and further to Brane and Projective Brane Calculi. All these have to do with encoding the cellular activities. I believe that these aspects need to be explained and placed in their bibliographic context.

THE PAPERS DEFINING THE BIOAMBIENTS AND PROJECTIVE BRANE CALCULUS ARE CITED AND THE CONNECTIONS OF THIS CALCULI WITH AMBIENT CALCULUS AND BRANE CALCULI ARE DISSCUSED.

“pino “, “exo”, “phago”, “mate”, “drip”, “bud” are actions with a special signification in systems biology. There is a reason for which they have been chosen as atomic actions in spite of the fact that some of them can be encoded by the others. Please explain.

Structural congruence, in general, has been introduced in process algebra as an analogy with chemistry (see the "Chemical Abstract Machines"). Your explanations, given the purpose of this article, should go deeper. The phrase “The structural congruence relation is a way of rearranging the system such that the interacting parts come together” is not enough to explain why an equational theory is needed in a modeling language. I don't think that structural congruence rearranges the system; I would rather say that it equates processes that are ment to represent the same system.

THIS SECTION IS INTENDED AS AN INTRODUCTION TO BRANE CALCULI. MORE DETAILS ABOUT WHY THE SIX BIOLOGICAL OPERATIONS ARE CHOSEN AS SIGNIFICANT AND THE FACT THAT STRUCTURAL CONGRUENCE IS USED TO CHARACTERIZE FLUIDITY PROPERTIES CAN BE FOUND IN [8].

Here I feel there should be a section about P-systems. I think this article should emphasize the fact that P-systems are build on formal languages and automata theory and that they are a completely different mathematics to process calculi.

SINCE THERE IS AN ARTICLE IN SCHOLARPEDIA ABOUT P SYSTEMS (SEE Membrane Computing Gheorghe Paun (2010), Scholarpedia, 5(1):9259.) I THINK THERE IS NO NEED OF SUCH A THING.

Please explain what the rules are (e.g., rewriting rules are not structural SOS-like rules). In the same context you need to explain what the maximal parallelism is. Remember that for process calculi there is no similar concept and your calculus is a kind of process calculus. Why do you need maximal parallelism? Why do you use maximal parallelism on rewriting rules only?

WHEN DESCRIBING THE MOBILE MEMBRANE MODEL WE HAVE ADDED THE FOLLOWING STATEMENT: "A MOVEMENT RULE CONSISTS IN FACT IN TWO STEPS: REWRITING THE OBJECTS THAT INITIATED THE MOVEMENT TO MULTISETS OF OBJECTS AND CHANGING THE MEMBRANE STRUCTURE."

You mention "elementary membranes", "external membranes" and "external elementary membranes". What are these? Please explain.

AN ELEMENTARY MEMBRANE IS A MEMBRANE WHICH DOES NOT CONTAIN OTHER MEMBRANES, WHILE BY EXTERNAL MEMBRANES WE MEANT TO SAY SIBLING MEMBRANES (TWO MEMBRANES PLACED INSIDE THE SAME MEMBRANE). WE HAVE REPLACED EXTERNAL BY SIBLING.

You speak about “objects” and elements of an alphabet, but it is not clear to the reader that this alphabet is intended to denote the “objects”.

WE HAVE CORRECTED THIS BY SAYING THAT V IS A FINITE ALPHABET OF OBJECTS.

From your definition of behaviour for mobile membranes it is not clear that you use, in the same time, rewriting rules at the level of objects and structural rules at the level of membranes. Take, for instance, the case of (local object evolution) in Simple Mobile Membranes. You do not explain why “a” becomes “v”. This observation applies to the rest of the article.

WHEN DESCRIBING THE MOBILE MEMBRANE MODEL WE HAVE ADDED THE FOLLOWING STATEMENT: "A MOVEMENT RULE CONSISTS IN FACT IN TWO STEPS: REWRITING THE OBJECTS THAT INITIATED THE MOVEMENT TO MULTISETS OF OBJECTS AND CHANGING THE MEMBRANE STRUCTURE."

It is not clear to me, if the focus of this article is the relationship between Brane Calculi, Ambients and Mobile membranes, why you include all the complexity theorems. They are only true in your model where the maximal parallelism can be used and they represent, in fact, results from P-systems. What is their relevance concerning Ambients and Brane calculi? An answer to this question would improve a lot the consistency of this article.

AS IT RESULTS FROM THE FIRST PHRASE OF THE ARTICLE, THE TITLE OF IT SHOULD HAVE BEEN "Computational Aspects of Mobile Membranes and Relationships with Brane Calculi and Mobile Ambients". SINCE THERE IS NO ARTICLE ABOUT MOBILE MEMBRANES IN SCHOLARPEDIA, WE TRIED TO GIVE A SURVEY OF ALL RESULTS CONNECTED TO THIS SUBJECT. MOREOVER, COMPUTABILITY RESULTS REPRESENT A MAIN DIRECTION OF RESEARCH IN MEMBRANE COMPUTING.

Again, please emphasize the role of maximal parallelism and discuss the similarities and the differences between the two classes of calculi in term of applying the maximal parallelism. Can you mimick, in process algebra, the maximal parallelism, or your embedding of mobile membranes into Brane uses extra states? If this is the case, then the embedding only reffers to rechability problems. If, on the other hand, the embedding is "perfect", then a lot of techniques used in process algebras might be imported to P-systems such as model checking based on temporal or Hennessy-Milner logics, abstract interpretation techniques, etc.

FIRST OF ALL WE DO NOT EMBED MOBILE MEMBRANES IN PROCESS ALGEBRA BUT THE OTHER WAY AROUND. AS IT RESULTS FROM THE GIVEN PROPOSITIONS, THE OBTAINED TRANSLATION CAN PERFORM ADDITIONAL STEPS. THE EMBEDDING CAN BE USED TO TACKLE ONLY THE REACHABILITY PROBLEM (THIS IS PRESENTED IN A PAPER: B. Aman, G.Ciobanu. On the Reachability Problem in P Systems with Mobile Membranes. Lecture Notes in Computer Science, vol.4860, 113–123, 2007.).

Reviewer C

This article describes various calculi: mobile ambients, brane calculi and mobile membranes, and recalls some computational results for these systems. It also provides some relationships between mobile membranes and mobile ambients/brane calculi (embedding mobile ambients and brane calculi into mobile membranes).

---

General comments:

First of all, giving some examples of system evolution would help to understand the differences between Mobile Membranes and Safe Ambients/Brane Calculi, and also between the different variants of Mobile Membranes. Similarly, giving some biological intuitions would help in understanding/justifying the reduction rules of the different Mobile Membranes calculi.

DUE TO A LIMITED SPACE, WE ARE NOT ABLE TO PRESENT EXAMPLES. WE JUST MENTION THAT SOME EXAMPLES ARE PRESENTED IN [2], [3], [8] AND [9].

---

More specific comments:

Reduction rules of Mobile Ambients: the "amb" subscript is missing in the "Struc" rule. The "Comp2" rule seems unusual: is it from the regular Safe Ambients semantics, or has it been added in order to have operational correspondence with Mobile Membranes? As for Mobile Membranes (Par2 rule), the rule seems to be present to obtain maximally parallel reductions but no such statement is made for Mobile Ambients and no intuition is given for such a requirement.

WE HAVE ADDED THE SUBSCRIPT AMB TO THE STRUCTURAL CONGRUENCE RELATION FROM RULE STRUCT. WE HAVE ELIMINATED THIS PROBLEM BY KEEPING ONLY THE PARALELISM RULE FOR MEMBRANES, AND THE INTERLEAVING RULE FOR AMBIENTS.

Syntax of Brane calculi: the null process is denoted by O in the syntax and 0 in the abbreviations.

WE HAVE REPLACED O BY 0 IN SYNTAX.

Syntax and rules of Brane calculi: because no precedence rule is defined, the reduction rules are ambiguous.

THE PRECEDENCE RULE WAS ADDED\[a.\sigma|\tau\] stands for \((a.\sigma)|\tau\).

Mobile Membranes: You do not really explain what it mean for an object to be associated to a membrane; e.g. in the membrane [ [ a | b ] | c ], the objects associated to the outer membrane are a,b,c or only c? (I suppose it is the latter)

WE EXPLAIN BETTER WHAT MEANS THAT A MEMBRANE CONTAINS A MULTISET OF OBJECTS, AND HAS ON ITS SURFACE ANOTHER MULTISET OF OBJECTS.

Structural congruence definition: a "M" is missing in the last equation.

THE PROBLEM IS SOLVED.

Simple Mobile Membranes: What is the biological intuition behind the difference between the local object evolution rule and global one?

FOR ALL VARIANTS OF MOBILE MEMBRANES, BIOLOGICAL MOTIVATIONs OF THE RULES ARE PRESENTED IN [2], [3].

IMAGINE WE HAVE A BACTERIUM WHICH ENTERS AN INJURED ORGANISM. CHEMICAL REACTIONS MAY TAKE PLACE INSIDE IT, WHILE THE BACTERIUM CIRCULATES THROUGH THE ORGANISM. IN THIS CASE WE MAY MODEL THIS INTERNAL REACTIONS BY GLOBAL EVOLUTION RULES SINCE WE DO NOT CARE WHERE THE BACTERIUM IS POSITIONED. HOWEVER, WHEN A BACTERIUM IS ENGULFED BY A DENDRITIC CELL, DIFFERENT CHEMICAL REACTIONS TAKE PLACE INSIDE THE BACTERIUM THAT CAUSE THE DISSOLUTION, REACTIONS CAUSED BY THE POSITIONING INSIDE THE DENDRITIC CELL. IN THIS CASE WE MAY MODEL THIS INTERNAL REACTIONS BY LOCAL EVOLUTION RULES. THIS IS WHY WE DECIDED TO USE BOTH LOCAL OBJECT EVOLUTION AND GLOBAL OBJECT EVOLUTION RULES, RULES WHICH ARE INSPIRED FROM BIOLOGICAL FACTS.

Enhanced Mobile Membranes: What is the biological intuition behind the difference between the endocytosis and the enhanced endocytosis rules (and similarly for the exocytosis rules)?

THE ENDOCYTOSIS RULES CAN BE USED TO MODEL THE FACT THAT A VIRUS ENTERS A CELL, WHILE THE ENHANCED ENDOCYTOSIS RULE CAN BE USED TO MODEL THE FACT THAT A DENDRITIC CELL ENGULFS THE BACTERIUM. THE MAIN DIFFERENCE IS GIVEN BY THE FACT THAT IN THE FIRST CASE THE VIRUS PERFORMS THE MOVEMENT, WHILE IN THE SECOND THE DENDRITIC CELL MAKES THE MOVE BY EATING THE BACTERIUM. FOR MORE DETAILS SEE [1].

Mutual Membranes with object on surface: are the theorems presented in this section new results? You do not cite any reference paper in this section. Same remark for the next section (embedding of Brane Calculi into Mobile Ambients).

ALL THESE RESULTS ARE SUBMITTED FOR PUBLICATION TO A JURNAL; WE CAN ADD A REFERENCE AFTER RECEIVING ACCEPTANCE.

---

Minor comments:

Brane calculi: The "phago" rule is sometimes called "phago" and sometimes "phage" in the figures' captions of this section.

WE HAVE REPLACED PHAGE BY PHAGO IN ALL PLACES.

Brane calculi: rho is undefined.

WE HAVE DEFINED \RHO.

Embedding Brane Calculi into Mobile Membranes: In your translation T : P -> M, "Q | R" should be "Q o R". The translation S is defined from P to V*, but P is the set of systems, not the set of branes.

WE HAVE MODIFIED THE FIRST PART AS SUGGESTED. FOR THE SECOND PART WE HAVE DEFINED \MATHCAL{B} THE SET OF BRANES, THUS DEFINING S FROM B TO V*.

Embedding Mobile Ambients into Mobile Membranes: In the definition of this section, T is already defined as a translation P -> M and "cap" is undefined. The sentence just before the second proposition is strangely formulated.

WE HAVE DENOTED THIS TRANSLATION BY T1 AND ALSO DEFINED CAP. WE HAVE REPHRASED THE SENTENCE BEFORE THE SECOND PROPOSITION.

Last proposition: "If there is" -> "If there exists". "is equal with" -> "is equal to".

WE HAVE MODIFIED AS SUGGESTED.

Last theorem: "If ... then exists".

WE DO NOT UNDERSTAND PROPERLY. ANYWAY, WE CHANGED IN "IF...THEN THERE IS...".