Computations over finite monoids and their test complexity (Q1178692)

With the increasing complexity of VLSI circuits, the chip testing costs became prohibitive and led to the definition of a new design methodology, known as design for testability. One of the most important results in this area is that the problem of testing a complex VLSI chip can be reduced to the test of all its combinatorial building blocks \textit{E. B. Eichelberger} and \textit{T. W. Williams} [A logic design structure for LSI testability, J. Design Automation Fault-Tolerant Comput. 2, 165-178 (1978)]; \textit{B. Koonemann, J. Mucha} and \textit{G. Zwiehoff} [Built-in logic block observation technique, Proc. IEEE Test. Conf. (1979)]. Henceforth, what remains to be done, is to search for ``optimal'' strategies to test the combinatorial blocks of a chip. Many important combinatorial circuits such as PLA's, multipliers, adders, have a very (mostly geometrically) regular structure, and it has been extensively studied how these structural properties can be used for deriving small test sets \textit{H. Fujiwara} and \textit{K. Kinoshita} [A design of programmable logic arrays with universal tests, IEEE Trans. Comput. C30, No. 11, 823-828 (1981; Zbl 0467.94027)]; \textit{B. Becker} and \textit{U. Sparmann} [A uniform test approach for RCC-Adders, Proc. 3rd Aegean Workshop of Computing (1988)]. The authors generalize a concept that was first introduced in the preceding cite. They consider the test pattern generation problem for circuits which compute expressions over some algebraic structure, specifically, the family of all finite monoids. The test complexity of a monoid with respect to a specific computation problem is measured by the number of tests needed to check the best testable circuit (in a certain computational model) solving that problem. Two important computation problems over finite monoids, namely expression evaluation and parallel prefix computation are considered, and the relation between algebraic properties of a monoid and its test complexity (with respect to these problems) is studied. The authors show that in both cases, the set of all finite monoids partitions into exactly three classes with constant, logarithmic and linear test complexity, respectively. These classes are then characterized using algebraic properties; for example, groups are exactly the monoids with constant test complexity. For each class, optimal test circuits and efficient methods to decide the membership problem for a given finite monoid are provided.