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.