A process algebra is an algebra
for describing process
es, 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
We can build expressions with them, e.g.
(a | b)*
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 a
nger my roommate and then either
oil an egg or c
lean the table, is the same as saying that
I either a
nger my roommate and then b
oil an egg or
nger my roommate and then c
lean 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
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.