Why a process algebra is not an algebra of processes
I'd like to explain why I think a process algebra is not an algebra of processes.
I need to explain some minimal properties that an algebra of processes should have. Firstly finite state automata should be processes. Secondly such an algebra should have abstract operations; that is, the operation applied to isomorphic automata should produce isomorphic automata.
I will now demonstrate why these two properties are not satisfied by process algebras.
A typical process algebra has the operation "prefix an action". So for example if P is a process in a given state then aP is the process which first does action labelled a, then becomes P. A typical process algebra also has the operation aP+bQ which is the process which nondeterministically does either action a becoming P or action b becoming Q. A special process is the process NIL which does nothing.
Further, a typical process algebra permits recursive definitions.
This suggests that one might define finite state automata using the operations I described plus recursion. So for example the equation P=aP should describe the automaton with one state P and one transition a : P -> P.
Unfortunately this doesn't work. I will give you two examples.
EXAMPLE 1 The recursive equation Q=aaQ should be an automaton with two states Q, aQ, and two transitions a : Q -> aQ and a : aQ -> Q.
Further, the recursive equation R=a(aR+NIL) should be an automaton with two states R and (aR+ NIL) and two transitions a: R -> (aR+NIL), a : (aR+NIL) -> R.
Hence Q and R are isomorphic automata.
For the prefix operation to be abstract we obviously need that aQ and aR are isomorphic automata.
Unfortunately THEY ARE NOT.
EXAMPLE 2 The processes aaP and aaQ correspond to isomorphic automata each with three states
and two transitions both labelled a. The process bbP has three states bbP, bP and P with two
transitions b : bbP -> bP, b : bP -> P.
For the sum operation to be abstract we obviously need that aaP+bbP and aaQ+bbP correspond to isomorphic automata.
Unfortunately THEY DO NOT.
There is ambiguity in the word process. It can mean a system with state, or it can mean a behaviour of a system. I have taken the first meaning because in explaining process algebras people draw transition systems (automata) (See for example, Robin Milner's book on the Pi Calculus).
In the classical theory of automata there is a clear separation between automata and behaviours (languages). There is an algebra of automata and an algebra of languages, and a comparison between them.
The problem with process algebras is that there are not the two things, an algebra of systems and an algebra of behaviours, and a confrontation between them.
I need to explain some minimal properties that an algebra of processes should have. Firstly finite state automata should be processes. Secondly such an algebra should have abstract operations; that is, the operation applied to isomorphic automata should produce isomorphic automata.
I will now demonstrate why these two properties are not satisfied by process algebras.
A typical process algebra has the operation "prefix an action". So for example if P is a process in a given state then aP is the process which first does action labelled a, then becomes P. A typical process algebra also has the operation aP+bQ which is the process which nondeterministically does either action a becoming P or action b becoming Q. A special process is the process NIL which does nothing.
Further, a typical process algebra permits recursive definitions.
This suggests that one might define finite state automata using the operations I described plus recursion. So for example the equation P=aP should describe the automaton with one state P and one transition a : P -> P.
Unfortunately this doesn't work. I will give you two examples.
EXAMPLE 1 The recursive equation Q=aaQ should be an automaton with two states Q, aQ, and two transitions a : Q -> aQ and a : aQ -> Q.
Further, the recursive equation R=a(aR+NIL) should be an automaton with two states R and (aR+ NIL) and two transitions a: R -> (aR+NIL), a : (aR+NIL) -> R.
Hence Q and R are isomorphic automata.
For the prefix operation to be abstract we obviously need that aQ and aR are isomorphic automata.
Unfortunately THEY ARE NOT.
- aQ has two states aQ and Q and two transitions a : aQ -> Q, and a : Q -> aQ, while instead
- aR has three states aR, R, (aR+NIL), and transitions a : aR -> R, a : R -> (aR+NIL), and a : (aR+NIL) -> R.
EXAMPLE 2 The processes aaP and aaQ correspond to isomorphic automata each with three states
and two transitions both labelled a. The process bbP has three states bbP, bP and P with two
transitions b : bbP -> bP, b : bP -> P.
For the sum operation to be abstract we obviously need that aaP+bbP and aaQ+bbP correspond to isomorphic automata.
Unfortunately THEY DO NOT.
- aaP+bbP has four states aaP+bbP, aP, bP, P, whereas
- aaP+bbQ has five states aaP+bbQ, aP, bQ, P, Q.
There is ambiguity in the word process. It can mean a system with state, or it can mean a behaviour of a system. I have taken the first meaning because in explaining process algebras people draw transition systems (automata) (See for example, Robin Milner's book on the Pi Calculus).
In the classical theory of automata there is a clear separation between automata and behaviours (languages). There is an algebra of automata and an algebra of languages, and a comparison between them.
The problem with process algebras is that there are not the two things, an algebra of systems and an algebra of behaviours, and a confrontation between them.
Labels: computing
posted by Unknown at 1:47 PM
1 Comments:
Dear Bob Walters,
I'm not sure I understand what you mean by `abstract', nor exactly which process algebra you're using.
But I tend to think that one of the main interests of process algebra (or, rather, of the semantics of concurrency) is to replace the standard confrontation between automata and languages with a whole spectrum (to use van Glabbeek's word) of confrontations. You may chose your preferred notion of behaviour, from strong bisimilarity to language equivalence, or even invent your own when you find defects in the existing ones.
Am I missing your point?
Post a Comment
<< Home