On flowchart theories. II: The nondeterministic case (Q1101203)

This paper continues the author's program of viewing a flowchart as a morphism in a coproduct of a certain type of algebraic theory T and a ranked set of variables X. The morphisms in T are viewed as ``known computational processes'' and the variables are ``unknown processes''. Part I [J. Comput. Syst. Sci. 35, 163-191 (1987; Zbl 0628.68018)] dealt with deterministic flowcharts and involved theories with a feedback or iteration operation. The nondeterministic case involves theories with an operation of repetition. The motivation for the mathematical model of nondeterminism derives from the following view of the world (taken from the introduction). ``The deterministic case corresponds to the physical world; physical processes have deterministic evolutions; two processes many be considered equivalent if they evolve in the same way.... The nondeterministic case corresponds to the living world. Living processes are based on physical processes, their characteristic feature consisting in the ability of fixing aims. In view of its aim, a living process can choose between several variants, or can top if it feels that it cannot reach its aim and restart trying another way. This shows that nondeterministic flowcharts may be considered naturally equivalent if they have the same set of successful paths....''. From these two unassailable premises the author jumps immediately to the following hypothesis: nondeterminism \(=\) determinism \(+\) dual determinism. The meaning of the hypothesis is that all deterministic laws and their duals (obtained by reversing arrows) are to be considered valid nondeterministic laws. Although the mathematical meaning of the hypothesis becomes clear in the paper, how this interesting looking hypothesis was found is unclear. It turns out that the algebraic theories which have the dualistic properties desired are the matrix theories, i.e. matrices over a semiring S. The collection of n by n matrices over S is equipped with an operation called repetition \(A\mapsto A^*\). (It is not immediately clear if the repetition operation is determined by its restriction to S.) Several propositions are given pointing out the relationships among various properties of the repetition function. The main result of the paper is that a certain quotient of the schemes over the repetition theory T is (almost) freely generated by T (and the variables).