On flowchart theories. II: The nondeterministic case
type: Item
instance of: scholarly article
title: On flowchart theories. II: The nondeterministic case
zbMATH Open document ID: 0642.68020
DOI: 10.1016/0304-3975(87)90114-9
author: Gh. Ştefănescu
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
review text: 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 repetiti…
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 18C10
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4047050
zbMATH Keywords: flowchart schemes
zbMATH Keywords: algebraic theory
zbMATH Keywords: nondeterminism
zbMATH Keywords: dualistic properties
zbMATH Keywords: matrix theories
zbMATH Keywords: repetition function
reviewed by: Stephen L. Bloom
MaRDI profile type: Publication
full work available at URL: 0304-3975(87)90114-9
OpenAlex ID: W2111851448
cites work: Iterative and recursive matrix theories
cites work: Recursion and iteration in continuous theories: the ''M-construction''
cites work: Vector Iteration in Pointed Iterative Theories
cites work: Partial abstract types
cites work: Q5639639
cites work: Equivalences and transformations of regular systems - applications to recursive program schemes and grammars
cites work: Q4079524
cites work: Q4091917
cites work: Matricial theories
cites work: Algebras of iteration theories
cites work: Nondeterministic flowchart programs with recursive procedures: Semantics and correctness. I
cites work: Correctness of recursive parallel nondeterministic flow programs
cites work: Initial Algebra Semantics and Continuous Algebras
cites work: Q3704880
cites work: Deterministic and nondeterministic flowchart interpretations
cites work: Equidivisible semigroups
cites work: Two Complete Axiom Systems for the Algebra of Regular Events
cites work: Q5751953
description: scientific article; zbMATH DE number 4047050