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

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