Computations over finite monoids and their test complexity
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.
- Finite Monoids: From Word to Circuit Evaluation
- Circuits over monoids: A fault model, and a trade-off between testability and circuit delay
- The Complexity of Fault Detection Problems for Combinational Logic Circuits
- Complexity issues of checking identities in finite monoids
- scientific article; zbMATH DE number 1419259
- A design of programmable logic arrays with universal tests
- A Regular Layout for Parallel Adders
- An easily testable optimal-time VLSI-multiplier
- Depth-size trade-offs for parallel prefix computation
- Design of Testable Structures Defined by Simple Loops
- scientific article; zbMATH DE number 4181296 (Why is no real title available?)
- scientific article; zbMATH DE number 3959293 (Why is no real title available?)
- On Realizations of Boolean Functions Requiring a Minimal or Near-Minimal Number of Tests
- Parallel Prefix Computation
- Size-time complexity of Boolean networks for prefix computations
- Testing in two-dimensional iterative logic arrays
- The Complexity of Fault Detection Problems for Combinational Logic Circuits
- Complexity results on the conjugacy problem for monoids
- Circuits over monoids: A fault model, and a trade-off between testability and circuit delay
- scientific article; zbMATH DE number 4216027 (Why is no real title available?)
- Finite Monoids: From Word to Circuit Evaluation
- THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS
- Some remarks on the test complexity of iterative logic arrays (extended abstract)
- Computable Følner monotilings and a theorem of Brudno
- Finite basis problem for 2-testable monoids.
This page was built for publication: Computations over finite monoids and their test complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1178692)
