Let Q_0 denote the rational numbers expanded to a ‘meadow’, that is, after taking its zero-totalized form (0^{−1}=0) as the preferred interpretation. In this paper, we consider ‘cancellation meadows’, i.e. meadows without proper zero divisors, such as Q_0 and prove a generic completeness result. We apply this result to cancellation meadows expanded with differentiation operators, the sign function, and with floor, ceiling and a signed variant of the square root, respectively. We give an equational axiomatization of these operators and thus obtain a finite basis for various expanded cancellation meadows.

We investigate the expressiveness of backward jumps in a frame work of formalized sequential programming called program algebra and characterize established non-uniform complexity classes in terms of instruction sequences, backward jumps and auxiliary registers.

A combination of program algebra with the theory of meadows is designed leading to a theory of computation in algebraic structures. It is proven that total functions on cancellation meadows can be computed by straight-line programs using at most five auxiliary variables. A similar result is obtained for signed meadows.

Abstract Ameadowis a commutative ring with an inverse operator satisfying 0−1= 0. We determine the initial algebra of the meadows of characteristic 0 and prove a normal form theorem for it. As an immediate consequence we obtain the decidability of the closed term problem for meadows and the computability of their initial object.

Threads as contained in a thread algebra emerge from the behavioral abstraction from programs in an appropriate program algebra. Threads may make use of services such as stacks, and a thread using a single stack is called a pushdown thread. Equivalence of pushdown threads is shown decidable whereas pushdown thread inclusion is undecidable. This is again an example of a borderline crossing where the equivalence problem is decidable, whereas the inclusion problem is not.

In this note, we prove that having unique head-normal forms is a sufficient condition on partial combinatory algebras to be completable. As application, we show that the pca of strongly normalizing CL-terms as well as the pca of natural numbers with partial recursive function application can be extended to total combinatory algebras.

We propose an extension of purely equational reasoning with an induction rule, to obtain an intermediate between the equational theory of an algebraic specification and its ω-closure.

We introduce iteration in process algebra by means of (the original, binary version of) Kleene's star operation: x * y is the process that chooses between x and y, and upon termination of x has this choice again. We add this operation to a whole range of process algebra axiom systems, starting from BPA (Basic Process Algebra). In the case of the most complex system under consideration, ACP τ , every regular process can be defined with handshaking (two-party communication) and auxiliary actions. Next we introduce nesting in process algebra: x#y is defined by the equation x#y=x(x#y)x+y