P-functions and Boolean matrix factorization. A unified approach for wired, programmed and microprogrammed implementations of discrete algorithms (Q1060560)

The author's extensive in-depth studies concerning general methodology of discrete algorithm implementations resulted in this monograph. Written in an excellent exhaustive and descriptive style, it provides the readers with all the background needed to fully understand his previously published papers [IEEE Trans. Comput. C-33, 289-300 (1984; Zbl 0528.68018) and ibid. C-33, 861-868 (1984; Zbl 0546.68031)]. The book presents an algebraic model for the representation of algorithms as well as the computation tools for the synthesis of algorithms. The basic formalism is the matrix description of instructions of which the algorithms are composed. The high- and low-level instructions considered in the text are represented by certain Boolean matrices. By synthesis of instructions the transformation of high-level instructions in terms of low-level instructions is understood. The set of low-level instructions is in the text limited to ''if-then-else'', ''transpose-if-then-else'', ''fork'' and ''join'' instructions. The low-level instructions may be implemented in software as well as in hardware leading to program or logic circuit implementation of algorithms. In order that the presented methodology of deterministic algorithm implementation be general, all cases of ''and''-as well as ''or''- interpretations of rows and columns of the matrix instructions are considered. Moreover, transposition of an instruction matrix is an important operation. It is shown that the synthesis of an instruction reduces to the transformations between two systems of the so-called P- functions, using composition laws corresponding to the low-level instructions. A P-function is defined as follows: The pair of Boolean functions \(<g;h>\) is a P-function of a Boolean function f if and only if \(fg=hg\). The study of P-functions as a tool associated with the concepts of Boolean functions and discrete functions is the prupose of an independent part of the book. This part presents the algebra of P- functions, which are then extended to the multivalued and vectorial cases. The book relates the proposed algebraic model to other models of computation, especially to the synchronous algorithmic state machines introduced by \textit{V. M. Glushkov} [Kibernetika, Kiev 1965, No.5, 1-9 (1965; Zbl 0156.018) and ibid. 1970, No.2, 3-13 (1970; Zbl 0242.68056)] and to the parallel flowcharts (equivalent to Petri nets), which are issued from the work of \textit{R. M. Karp} and \textit{R. E. Miller} [J. Comput. Syst. Sci. 3, 147-195 (1969; Zbl 0198.326)] and \textit{R. M. Keller} [J. Assoc. Comput. Mach. 20, 514-537, 696-710 (1973; Zbl 0273.68011 and Zbl 0279.68011)] devoted to asynchronous parallel program schemata. Special attention is paid to the fact that the parallel flowcharts and their associated vector addition systems are a tool for describing the composition of instructions, and thus complements the algebra of P- functions which is mainly a synthesis tool for implementing high-level instructions in terms of low-level instructions. Making efforts in advancing the presented methodology to the actual problems the author elaborated more widely two problems. The first is hardware-oriented and deals with the asynchronous implementation of instructions while the second is more software-oriented and concerns the synthesis of safe programs (this means programs in which faulty repetitions of instruction executions are not allowed). These problems show what is one of the most important advantages of the book - the similarities and differences between hardware and software implementations of algorithms. The book is illustrated by several examples of which the most utilized in many variants is the problem of choice of routes at a computer network node. To conclude let us cite from the foreword by S. B. Akers: ''This book makes an original, timely and unifying contribution to the process of digital design''.