<p>Another line of work that's - I believe - related to but not the same as BioComputing (unfortunately I'm not too well versed in this area), is "membrane computing." </p>

<p>My understanding of membrane computing is that it uses metaphors largely developed in the process-caclui world (Dave Clarke's answer gave a good set of pointers there) explicitly to model cellular interactions. A good guide to membrane computing is probably the aptly-named <a href="http://dx.doi.org/10.1016/S0304-3975(02)00136-6">A guide to membrane computing</a> by Paun and Rozenberg in TCS. It was a few years ago (and I'm not inside of a paywall at the moment to check) but I believe some models of membrane computing have a notion of "forking" that is supposed to somehow mirror cellular mitosis.</p>

CC BY-SA 2.5
2010-11-08T17:19:39.860Z
Thanks, Rob.  Cardelli's work doesn't touch on membrane computing as far as I know.  It's more focused on building a programming language theory for DNA circuits.  I appreciate the pointer, but I guess I'm looking for something more "mainstream" (meaning not itself bio-related in any way).
Aaron Sterling
CC BY-SA 2.5
2010-11-09T07:31:28.300Z
This is certainly an alternative. @Aaron: Cardelli's *Brane Calculus* http://lucacardelli.name/Papers/Brane%20Calculi.pdf models membranes.
Dave Clarke
CC BY-SA 2.5
2010-11-09T13:33:55.367Z
Ha!  The power of crowdsourcing!  Thanks again! :-)
Aaron Sterling
CC BY-SA 2.5
2010-11-08T16:09:56.170Z
2010-11-09T16:32:22.243Z
2010-11-09T16:32:22.243Z
Rob Simmons
<p>Of course there are many systems for modelling processes. These fall under the category of <a href="http://en.wikipedia.org/wiki/Process_calculus">process algebras</a>.  The key examples are <a href="http://en.wikipedia.org/wiki/Pi_calculus">$\pi$-calculus</a>, <a href="http://en.wikipedia.org/wiki/Calculus_of_Communicating_Systems">CCS</a>, <a href="http://en.wikipedia.org/wiki/Algebra_of_Communicating_Processes">ACP</a> and <a href="http://en.wikipedia.org/wiki/Communicating_sequential_processes">CSP</a>. </p>

<p>Process calculi have basic mechanisms for specifying process behaviour including: sending and receiving of messages (synchronously or asynchronously), creating parallel processes, nondeterministic choice between behaviours, and the replication of processes. Although the calculi are small in terms of the number of constructs, they are very expressive and a vast amount of research has gone into studying their properties.</p>

<p>The $\pi$-calculus differs from the others in that it allows, in essence, processes to be passed as first class values. It actually allows channel names to be passed around as first class values, enabling changes in the dynamic topology. This is probably the calculus you want because it offers the greatest dynamicity.</p>

<p>CSP (communicating sequential processes) is a little odd, when seen from a perspective of modelling molecules. It does have plenty of backing theory and tool support. (Invented by C. A. R. Hoare.)</p>

<p>CCS and ACP have less dynamicity than the $\pi$-calculus, but they are much easier to analyse and simulate. A solid toolset called $\mu$CRL (and $\mu$CRL2) are available for ACP. Similar tools are sure to exist for CCS. </p>

<p>I'd start examining the related work (see below) and then find which of the modelling formalisms suit what you are looking for.</p>

<p>There has in fact been quite a lot of work modelling chemical reactions and biological processes using process algebra.
Probably the best place to look  is <a href="http://lucacardelli.name/indexPapers.html">Luca Cardelli</a>'s publication list. His whole line of research on <strong>BioComputing</strong> has probably 30 papers on the topic. This <a href="http://lucacardelli.name/Talks/2010-09-30%20Molecular%20Programming%20%28Berry%20Lectures,%20Edinburgh%29.pdf">talk</a> gives an overview of much of his work. This <a href="http://lucacardelli.name/Talks/2007-12-04%20Artificial%20Biochemisitry%20%28Leiden%29.pdf">one</a> is slightly more formal, though reading the papers is really the only way to see the details.</p>

<p>One approach that directly models chemical processes is <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.6983&amp;rep=rep1&amp;type=pdf">CHAM</a> (the chemical abstract machine). The key ingredient here is a solution of molecules and membranes. There are heating and cooling rules for rearranging the molecules and for removing junk. These rules are reversible. Finally there reaction rules which model reactions. In contrast to process algebras, CHAM models are not so worried about the syntax of processes, so you can invent your own representation of the molecules.</p>

<p>Rewrite logic as realised in the toolset <a href="http://maude.cs.uiuc.edu/">Maude</a> offers another more or less direct approach to specifying such reactions. One need only specify the rewrite rules, the handing of the "soup" is automatic. The toolset would enable the simulation and analysis of (smallish) chemical reactions. A probabilistic variant of Maude also exists. </p>

CC BY-SA 2.5
2010-11-08T15:57:36.457Z
Could petri-nets also be considered among the possibilities ? forking could be modelled by having a place with two outgoing transitions.
Mohammad Alaggan
CC BY-SA 2.5
2010-11-08T16:14:02.937Z
More generally, petri-net style interactions can be modeled in linear logic (for one example, though not the only one, see "A concurrent logical framework: The propositional fragment" by Watkins et al, TYPES 2003)
Rob Simmons
CC BY-SA 2.5
2010-11-08T17:22:36.173Z
Thank you, Dave.  Humorously, perhaps, one of my projects is extending work Cardelli did in a couple papers on that page you linked to.  My knowledge of process algebra is limited, so I've been trying to avoid formalizing things that way, if possible.  Cardelli does define bio-versions of the $\pi$-calculus, but I don't understand them very well. It certainly helps that you think that might be the best direction to go.  More reason for me to learn a new formalism at the very least.
Aaron Sterling
CC BY-SA 2.5
2010-11-09T08:07:49.377Z
@M. Alaggan: On the surface it seems that Petri nets could do the job. Each place could be considered as a pool of chemicals. Each transition could be considered as reaction. Thus if we had places called H and O and H2O, a transition could take two tokens from H one from O and put one token into H2O. The problem with modelling in this manner is that only one of each such transition can fire concurrently, in contrast to process algebras which would allow many such transitions to fire at a time.
Dave Clarke
CC BY-SA 2.5
2010-11-11T14:08:16.807Z
@Aaron: depending on what you are trying to do, more modern process calculi like BioPEPA might be useful to you.
András Salamon
CC BY-SA 2.5
2010-11-08T15:09:06.773Z
2010-11-09T09:19:05.197Z
2010-11-09T09:19:05.197Z
Dave Clarke
<p>My background is in complexity theory/logic (where there is just one process most of the time), and in distributed computing (where there are <span class="math-container">$n$</span> processes, and one or more might fail over time).  However, I now want to be able to say something about a process spawning/creating/spinning off another process.  Is there rigor in parallel computing, operating systems, etc., that accounts for this?</p>
<p>Motivation:</p>
<p>I am trying to construct models that abstract out certain features of molecular interactions.  I'd like to say that the set of chemical reactions <span class="math-container">$S$</span> is an independent process, and that at a certain time step <span class="math-container">$t$</span>, it spawns another independent process <span class="math-container">$S'$</span>.  Intuitively, these things feel like independent processes, because they have no contact with each other after time <span class="math-container">$t$</span> - or very little contact, only interchanging &quot;messages.&quot;</p>
<p>More formally:</p>
<blockquote>
<p>(1) Are there pre-existing CS definitions that capture the notion of one process spawning another independent process?  I am especially interested in being able to demarcate where <span class="math-container">$S$</span> stops and <span class="math-container">$S'$</span> starts, and why that is &quot;reasonable&quot; to do.</p>
<p>(2) If there is more than one answer to (1), what do you consider the pros and cons to the various definitions?</p>
</blockquote>
<p>(Note: I have no idea how to tag this appropriately, and plan to re-tag depending on the answers.)</p>

CC BY-SA 2.5
2010-11-08T15:06:28.557Z
I have always found the `fork` system call in Unix-like operating systems conceptually very elegant. You can see it as an atomic operation that *duplicates* the current process. Before a fork, there was just one process $S$, while after the fork, there are two processes $S$ and $S'$. If we oversimplify things, $S$ and $S'$ are *identical* in all other aspects, except that there is a one-bit indicator that lets $S'$ know that it is the "new" process while $S$ knows that it is the "original" process. After that $S$ and $S'$ can continue separately, and they can even *modify themselves*.
Jukka Suomela
CC BY-SA 2.5
2010-11-08T17:23:30.387Z
@Jukka: Thank you :-)  It would be sweet if there were a way to connect what I'm doing to a Unix primitive.
Aaron Sterling
<dc.parallel-comp><process-algebra>
When a process spawns another process
Aaron Sterling
# When a process spawns another process

(Asked by: username_0 on 2010-11-08)

My background is in complexity theory/logic (where there is just one process most of the time), and in distributed computing (where there are $n$ processes, and one or more might fail over time). However, I now want to be able to say something about a process spawning/creating/spinning off another process. Is there rigor in parallel computing, operating systems, etc., that accounts for this?

Motivation:

I am trying to construct models that abstract out certain features of molecular interactions. I'd like to say that the set of chemical reactions $S$ is an independent process, and that at a certain time step $t$, it spawns another independent process $S'$. Intuitively, these things feel like independent processes, because they have no contact with each other after time $t$ - or very little contact, only interchanging "messages."

More formally:

> (1) Are there pre-existing CS definitions that capture the notion of one process spawning another independent process? I am especially interested in being able to demarcate where $S$ stops and $S'$ starts, and why that is "reasonable" to do.
>
> (2) If there is more than one answer to (1), what do you consider the pros and cons to the various definitions?

(Note: I have no idea how to tag this appropriately, and plan to re-tag depending on the answers.)

**Tags:** dc.parallel-comp, process-algebra

> **Comments:**
> **username_1**: I have always found the `fork` system call in Unix-like operating systems conceptually very elegant. You can see it as an atomic operation that *duplicates* the current process. Before a fork, there was just one process $S$, while after the fork, there are two processes $S$ and $S'$. If we oversimplify things, $S$ and $S'$ are *identical* in all other aspects, except that there is a one-bit indicator that lets $S'$ know that it is the "new" process while $S$ knows that it is the "original" process. After that $S$ and $S'$ can continue separately, and they can even *modify themselves*.  
> **username_0**: @Jukka: Thank you :-)  It would be sweet if there were a way to connect what I'm doing to a Unix primitive.  

---

## 2 answers

### Answer by username_3 on 2010-11-08. Score: 13 | Accepted answer

Of course there are many systems for modelling processes. These fall under the category of [process algebras](http://en.wikipedia.org/wiki/Process_calculus). The key examples are [$\pi$-calculus](http://en.wikipedia.org/wiki/Pi_calculus), [CCS](http://en.wikipedia.org/wiki/Calculus_of_Communicating_Systems), [ACP](http://en.wikipedia.org/wiki/Algebra_of_Communicating_Processes) and [CSP](http://en.wikipedia.org/wiki/Communicating_sequential_processes).

Process calculi have basic mechanisms for specifying process behaviour including: sending and receiving of messages (synchronously or asynchronously), creating parallel processes, nondeterministic choice between behaviours, and the replication of processes. Although the calculi are small in terms of the number of constructs, they are very expressive and a vast amount of research has gone into studying their properties.

The $\pi$-calculus differs from the others in that it allows, in essence, processes to be passed as first class values. It actually allows channel names to be passed around as first class values, enabling changes in the dynamic topology. This is probably the calculus you want because it offers the greatest dynamicity.

CSP (communicating sequential processes) is a little odd, when seen from a perspective of modelling molecules. It does have plenty of backing theory and tool support. (Invented by C. A. R. Hoare.)

CCS and ACP have less dynamicity than the $\pi$-calculus, but they are much easier to analyse and simulate. A solid toolset called $\mu$CRL (and $\mu$CRL2) are available for ACP. Similar tools are sure to exist for CCS.

I'd start examining the related work (see below) and then find which of the modelling formalisms suit what you are looking for.

There has in fact been quite a lot of work modelling chemical reactions and biological processes using process algebra.
Probably the best place to look is [Luca Cardelli](http://lucacardelli.name/indexPapers.html)'s publication list. His whole line of research on **BioComputing** has probably 30 papers on the topic. This [talk](http://lucacardelli.name/Talks/2010-09-30%20Molecular%20Programming%20%28Berry%20Lectures,%20Edinburgh%29.pdf) gives an overview of much of his work. This [one](http://lucacardelli.name/Talks/2007-12-04%20Artificial%20Biochemisitry%20%28Leiden%29.pdf) is slightly more formal, though reading the papers is really the only way to see the details.

One approach that directly models chemical processes is [CHAM](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.122.6983&rep=rep1&type=pdf) (the chemical abstract machine). The key ingredient here is a solution of molecules and membranes. There are heating and cooling rules for rearranging the molecules and for removing junk. These rules are reversible. Finally there reaction rules which model reactions. In contrast to process algebras, CHAM models are not so worried about the syntax of processes, so you can invent your own representation of the molecules.

Rewrite logic as realised in the toolset [Maude](http://maude.cs.uiuc.edu/) offers another more or less direct approach to specifying such reactions. One need only specify the rewrite rules, the handing of the "soup" is automatic. The toolset would enable the simulation and analysis of (smallish) chemical reactions. A probabilistic variant of Maude also exists.

> **Comments:**
> **username_4**: Could petri-nets also be considered among the possibilities ? forking could be modelled by having a place with two outgoing transitions.  
> **username_2**: More generally, petri-net style interactions can be modeled in linear logic (for one example, though not the only one, see "A concurrent logical framework: The propositional fragment" by Watkins et al, TYPES 2003)  
> **username_0**: Thank you, Dave.  Humorously, perhaps, one of my projects is extending work Cardelli did in a couple papers on that page you linked to.  My knowledge of process algebra is limited, so I've been trying to avoid formalizing things that way, if possible.  Cardelli does define bio-versions of the $\pi$-calculus, but I don't understand them very well. It certainly helps that you think that might be the best direction to go.  More reason for me to learn a new formalism at the very least.  
> **username_3**: @M. Alaggan: On the surface it seems that Petri nets could do the job. Each place could be considered as a pool of chemicals. Each transition could be considered as reaction. Thus if we had places called H and O and H2O, a transition could take two tokens from H one from O and put one token into H2O. The problem with modelling in this manner is that only one of each such transition can fire concurrently, in contrast to process algebras which would allow many such transitions to fire at a time.  
> **username_5**: @Aaron: depending on what you are trying to do, more modern process calculi like BioPEPA might be useful to you.  

---

### Answer by username_2 on 2010-11-08. Score: 7

Another line of work that's - I believe - related to but not the same as BioComputing (unfortunately I'm not too well versed in this area), is "membrane computing."

My understanding of membrane computing is that it uses metaphors largely developed in the process-caclui world (username_3's answer gave a good set of pointers there) explicitly to model cellular interactions. A good guide to membrane computing is probably the aptly-named [A guide to membrane computing](http://dx.doi.org/10.1016/S0304-3975(02)00136-6) by Paun and Rozenberg in TCS. It was a few years ago (and I'm not inside of a paywall at the moment to check) but I believe some models of membrane computing have a notion of "forking" that is supposed to somehow mirror cellular mitosis.

> **Comments:**
> **username_0**: Thanks, Rob.  Cardelli's work doesn't touch on membrane computing as far as I know.  It's more focused on building a programming language theory for DNA circuits.  I appreciate the pointer, but I guess I'm looking for something more "mainstream" (meaning not itself bio-related in any way).  
> **username_3**: This is certainly an alternative. @Aaron: Cardelli's *Brane Calculus* http://lucacardelli.name/Papers/Brane%20Calculi.pdf models membranes.  
> **username_0**: Ha!  The power of crowdsourcing!  Thanks again! :-)  

---

