# zbMATH — the first resource for mathematics

Geometry of interaction. II: Deadlock-free algorithms. (English) Zbl 0716.03047
Colog-88, Proc. Int. Conf., Tallinn/USSR 1988, Lect. Not. Comput. Sci. 417, 76-93 (1990).
[For the entire collection see Zbl 0709.00021.]
In part I [Logic colloq. ’88, Proc. Colloq., Padova/Italy 1988, Stud. Logic. Found. Math. 127, 221-260 (1989; Zbl 0686.03030)] an explicit formula for cut-elimination was established: $$EX(u,\sigma)=(1-\sigma^ 2)CP(u,\sigma)(1-\sigma^ 2)$$ where $$CP(u,\sigma)=u(1-\sigma u)^{-1}$$. Here u describes the derivation and $$\sigma$$ describes cuts. In the present part II this formula in the more general situation of operator algebra is taken as a starting point of a general treatment of algorithms. An algorithm is defined as a pair (u,$$\sigma$$) of suitable oprators. CP(u,$$\sigma$$) is compared to $$\mu$$ yT(e,x,y) in Kleene normal form for partial recursive functions, and the remaining part of EX(u,$$\sigma$$) is compared with the value-extracting function. An algorithm (u,$$\sigma$$) is defined to be deadlock-free iff $$\sigma$$ u is weakly nilpotent, i.e. $$(\sigma u)^ n$$ converges to 0 in weak topology. An application of algorithms is defined and fixed points are treated.
Reviewer: G.Mints

##### MSC:
 03F05 Cut-elimination and normal-form theorems 03B70 Logic in computer science 46L99 Selfadjoint operator algebras ($$C^*$$-algebras, von Neumann ($$W^*$$-) algebras, etc.)