Past exam of the computer science course of the University of Oxford 2015 Concurrency 1 a Solution 2026-10-31
The unique fixed point principle says that a suitably guarded recursion has a unique solution in the chosen CSP semantic model. In particular, for a guarded process expression ,The same principle applies to a mutually recursive system: two tuples satisfying the same guarded equations are componentwise equal. Thus an algebraic proof may show that a candidate satisfies the defining equations, instead of comparing arbitrarily long executions individually.
A guarded recursion must make visible progress before re-entering its recursive dependency. For an equation built from CSP prefixing and CSP choice, the usual sufficient condition is that every recursive occurrence lies behind a visible CSP prefixing operation. For mutually recursive equations, every dependency cycle must pass such a guard. The guard must survive enclosing operators: an event subsequently removed by CSP hiding does not provide visible progress. Equivalently, in the usual semantic formulation the recursion functional must be contractive in observable depth. Merely seeing an arrow somewhere before the variable is insufficient.
Past exam of the computer science course of the University of Oxford 2015 Concurrency 1 b Solution 2026-10-31
Take a fresh CSP event and defineThe apparent guard is removed by CSP hiding. Each unfolding can perform a CSP internal action and return to the same situation without any visible CSP event. Operationally this is an infinite internal loop, a CSP divergence, so the equation is not a guarded recursion. This is precisely why a syntactic test that counts every occurrence of would be wrong.
Unique fixed point principle 2026-10-31
For a suitably guarded recursion, two solutions of the same defining equation denote the same CSP process. There is also a mutually recursive version, comparing tuples of solutions.