3
$\begingroup$

In the literature, the terms of "process calculus" and "process algebra" are often interchangeable. Meanwhile, it confused me.

My questions are:

  1. Are there formal, standard, and widely-accepted definitions of "calculus" and "algebra"?
  2. What are the significant distinctions (maybe informally) between "calculus" and "algebra"?
  3. What are the features that make a theory kind of "calculus" or "algebra"?
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ My intuition, but it may be personnal, is that it is two views, two sides of the same coin, à la Curry-Howard. Algebra emphasizes more the structural and relational aspect of mathematical entities. Calculus emphasizes more the algorithmic aspect, the way algebraic properties can be used to solve problems. This was my first instinctive answer before I started looking at other sources, and realized I had already answered that question. $\endgroup$
    – babou
    Commented Oct 9, 2014 at 17:21
  • 1
    $\begingroup$ I do not understand why this has been marked as a duplicate: this question needs a more specific answer than a definition of "algebra" versus "calculus"; it concerns the specific techniques used in concurrency theory. $\endgroup$
    – Bordaigorl
    Commented Oct 9, 2014 at 20:41

2 Answers 2

Reset to default
5
$\begingroup$

To my knowledge the two terms do not have a formal established definition and are often used interchangeably.

There are different characteristics associated to each however, as @Dave already pointed out. I'll try to elaborate a bit further.

In both cases you start by introducing the syntax of a language for expressing (concurrent) systems. This introduces what the basic "combinators" (constructs) for assembling systems together are. The real distinction comes when you start to specify their semantics.

The process calculi approach is calculational in the sense that you focus on the reduction semantics, i.e. what are the steps a system can perform when executing it. This operational view helps a lot when using these languages for simulation for example. The chief notion in this case is the concept of "observation": what can you observe about the evolution of a system? Using this idea one can determine when two systems are equivalent. The technical word for this concept is bisimilarity. Then, in some situations, you find that processes which are bisimilar can be interchanged in any context without altering the behaviour of the system overall. This is the approach Milner and his collaborators took in defining many calculi such as CCS and π-calculus.

The algebraic view instead avoids specifying a model for the semantics directly and opts for a more axiomatic view: a series of laws (equations between expressions of the language) establish which processes have the same behaviours. The focus is in proving equivalences and enriching the calculus with different combinators. Even the "execution" of a system is expressed as an equivalence between a system and a (simpler expression used as a) specification (see the step laws for CSP for instance). The equivalence between two systems is established by using the laws instead of referring to a particular model for their behaviour. The chief concept in this context is the one of refinement. This approach is the basis of the work of Hoare and his collaborators in defining CSP and its variants.

That said, most of the languages mentioned have being studied with a mixture of these approaches so the distinction is more about the specific method used in a specific construction rather than about a language as a whole.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I am no longer very familiar whith these issues, so please correct me if I am wrong. It seems to me that your remark about specifying a model should be mitigated by the fact that you will usually choose an initial model to define semantics with a calculus, so that both the algebra and the calculus can be specialized hand in hand to any interpretation. So the idea that you specify a model (choose a specific model) for the calculus is not really accurate: you do not choose it, but it is given, imposed up to isomorphism. $\endgroup$
    – babou
    Commented Oct 10, 2014 at 10:56
  • $\begingroup$ We are probably speaking about different things when saying "model". The "initial model" gives you syntax and a structural recursion principle. What I mean by model here is a "concrete abstract machine", an operational semantics which is in a sense external to syntax...does this make sense? $\endgroup$
    – Bordaigorl
    Commented Oct 10, 2014 at 11:15
  • $\begingroup$ The difference between laws and concrete models is also made explicit by the fact that you need to prove that they match, it is not automatic. However, do not get me wrong, as I said none of the works I have seen take a "pure" view on these constructions, there are semantics models for CSP, for example. It's just that both viewpoints can spot different (and powerful) light on these systems. $\endgroup$
    – Bordaigorl
    Commented Oct 10, 2014 at 11:19
  • $\begingroup$ I think your remarks do bring significant light on the issues. I am not familiar with the process view, which may make a difference. My impression was that the abstract computation machine, the operational semantics, is often derived from the syntactic model of the algebra. For example, you take known identities, provable algebraically, and use them directionally as a rewriting system, at least to get normal forms. But then, this is probably too simple to apply to all algebras, or to all problems for a given type of algebra. $\endgroup$
    – babou
    Commented Oct 10, 2014 at 12:15
  • $\begingroup$ Given that an algebra is an axiomatic view, and that a calculus is more an algorithmic view, i.e. a proof view, I would guess that the two views may run into Gödel type of incompleteness results, so that they are not quite equivalent, even though they aim to be so. All you need is enough arithmetics in the algebra. I have no idea whether that is the case for process algebra. Still, as soon as you use the algebra to prove things, an equivalence for example, it is no better than a calculus in that respect. Am I making sense? $\endgroup$
    – babou
    Commented Oct 10, 2014 at 12:15
4
$\begingroup$

The distinction is not so clear. Nevertheless, here is an attempt to provide an alternative answer to your question.

A calculus involves calculation. Thus a process calculus will involve a notion of reduction. Examples include the $\pi$-calculus and CCS (and others from the Milner School).

Algebra involves equations. A a process algebra will be phrased in terms of equations. Examples include process calculus ACP (and others from the Amsterdam School).

Improve this answer
$\endgroup$
1
  • $\begingroup$ I nuked my comment and your reference to it, since my comment isn't very useful now that your more detailed answer has superseded it. $\endgroup$
    – David Richerby
    Commented Oct 9, 2014 at 14:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.