A process algebra is an algebra for describing processes, or more accurately, discrete systems. Being an algebra, it consists of a set of operations, and equivalence rules on constructions that can be built from those operations. A simple example: let's have the following three operations:

  a | b
  a ; b
  a*
We can build expressions with them, e.g. (a | b)* or b*(a ; b*)*.

Now let's interpret these expressions as follows.

  • | means 'or'
  • ; means 'and then'
  • * means 'zero or more times'
So we're interpreting the operations as ways in which a bigger process can be composed of smaller processes, and ultimately, elementary steps.

For instance, (a | b)* means: zero or more times either a or b. Or, if you wish, an arbitrary sequence of a and b.

With this interpretation, we probably want to consider some expressions as equivalent. One of the equivalence rules of our algebra might be, for instance:


  a ; (b | c)  =  (a ; b) | (a ; c)

i.e. to say that I first anger my roommate and then either boil an egg or clean the table, is the same as saying that I either anger my roommate and then boil an egg or anger my roommate and then clean the table.

Or is it?

This is where things become tricky. It is easy to state rules for when two expressions "really mean the same thing". But whether your rules are justified depends on your processes and how you look at them. For example, if we are only interested in the possible sequences of steps that a process allows, then the given equivalence rule is certainly valid. (In fact, in that case, what we're looking at is regular expressions.) But if we suppose that the expressions also indicate the moment of choice, and if the moment of choice is important, then the equivalence does not hold: in a ; (b | c) I first do a and only then choose how to continue, while in (a ; b) | (a ; c) I make the choice before doing a.

So different ideas of what matters when describing processes lead to different equivalence rules, even for the same operations. But we can also introduce different operations: for example,


  a & b    "a and b both happen, in any order"

Is this equivalent to saying

  (a ; b) | (b ; a)

? Well, only if we do not want to distinguish the situation in which a and b happen at exactly the same time.

This should give you an idea of what process algebra is, and why there are so many of them.

Log in or registerto write something here or to contact authors.