×

The role of modern algebra in computing. (English) Zbl 0241.68003

Computers Algebra Number Theory, Proc. Sympos. Appl. Math. Am. Math. Soc., Soc. Industr. Appl. Math. 1970, SIAM-AMS Proc. 4, 1-47 (1971).
The survey article is devoted to the role of modern algebraic ideas and techniques in the science of digital computing. While applications of classical algebra to numerical computation involve many ideas from analysis and should better be described as modern applied arithmetic than “numerical algebra”, the author states that modern algebra as the science of symbol manipulation (including Boolean algebras and lattices, binary relations and graphs, and combinatorial algebra) is important for the developing science of nonnumerical computation. The highly interesting paper presents known facts in a fresh light, contains some unpublished technical results and observes that problems of computation (especially attempts to solve various problems of optimization and computational complexity) influence algebra and contribute to deepened understanding of potentialities and limitations of algebraic symbol manipulation.
Contents: 1. Introduction.
Part A (Binary algebra; lattices; semigroups).
2. Boolean algebra. It is stated that if switching theory is defined as the branch of modern (i.e. nonnumerical) algebra concerned with optimizing logic design (for a network which will realize a given Boolean function \(f: 2^n\to 2\) by AND-gates, QR-gates and inverters), the main theoretical problem of this theory has not yet been solved.
3. Binary groups. The properties of these groups (the Abelian groups of order \(2^n\)) are used for codes which synthesize reliable message-transmitting “organisms” (including computers) from unreliable components. In order to minimize the probability of error in message transmission, encoding-decoding procedures called binary \((m,n)\) group codes are used. Algebraic coding theory [cf. the author and T. C. Bartee, Modern applied algebra. New York: McGraw Hill (1970; Zbl 0215.31302)]; the article of E. R. Berlekamp [Recent Progress Comb., Proc. 3rd Waterloo Conf. 1968, 3–11 (1969; Zbl 0199.54101)] aims at constructing simpler optimal (or near-optimal) codes than in Shannon’s existence theorem. Two related optimal packing problems (for disjoint spheres of given radius) are mentioned.
4. Binary relations and graphs. (The algebra \(2^{S\times T}\) of binary relations, computer logic, graphs, programs, networks, configurations, incidence and adjacency.)
5. Lattices. (Partitions, closure and dependence, linear, affine subspaces and convex subsets of a vector space as closed subsets, subgeometries, exchange property, Jordan-Dedekind chain condition, Radon property, combinatorial characterization problems [cf. V. Klee and D. W. Walkup, Acta Math. 117, 53–78 (1967; Zbl 0163.16801)].
6. Combinatorial complexes. (Complexes with covering relation as semilattices, decomposing plates and shells into polygonal elements for the solution of typical problems of solid mechanics on computers.)
7. Semigroups. (Monoids, semigroups acting on a set.)
Part B (Automata and universal algebra).
8. Algebras. (Algebraic systems \(A= \langle S,F\rangle\), \(F= \langle f_i: S^{n(i)} \to S\rangle \), \(n(i)\in N\), universal proofs, cryptomorphisms (algebraic equivalences in the sense of A. I. Mal’cev) which are in relation to algebraic functors in the sense of F. W. Lawvere).
9. State machines.
(Theorem of K. B. Krohn and J. Rhodes, free (homogeneous) state machine).
10. Heterogeneous algebras.
(Sequential machines or automata as heterogeneous algebras, cf. also the author and J. Lipson [J. Comb. Theory 8, 115–133 (1970; Zbl 0211.02003)].)
11. Partial algebras.
(p-morphisms \(\varphi: A\to B\) and free partial algebras in the sense of V. Poythress [Partial algebras, Ph. D. Thesis (Harvard Univ. 1970), see Algebra Univers. 3, 182–202 (1973; Zbl 0274.08008)]; when \(A, B\) are fields, then \(\varphi\) is what is called a specialization. Here also R. Kerkhoff [Gleichungsdefinierbare Klassen partieller Algebren, Diss. (Freiburg 1968), see Math. Ann. 185, 112–133 (1970; Zbl 0179.03402)] should be noticed).
12. Mathematical logic.
(Symbolic (i.e. algebraic) mathematical logic, theorem proving as a branch of algebra, the goal of Leibniz, Frege, Peano, Whitehead and Russell, Hilbert-Ackermann, Gödel; the author has not yet found a satisfactory definition of Turing machines as “algebras”, without including \(Z\) pretty obviously.)
13. Mathematical linguistics.
(Declarative and imperative statements, correctness of a compiler, a refined more realistic model of a computer with (i) capabilities for storing addresses, (ii) an integer arithmetic unit, (iii) Boolean logic capabilities, (iv) a standard word-length (“byte”) to aid in parsing, and (v) alphanumeric output capabilities, relations to universal algebra.)
Part C (Combinatorial algebra).
14. Relevance to computing. 15. Incidence algebras and Möbius functions. 16. Critical problems; symmetry. 17. Flow-graphs.
Part D (Linear systems).
18. General remarks. 19. Successive overrelaxation. 20. Gauss elimination. 21. Symmetric Gauss elimination. 22. Optimal ordering.
Part E (Piecewise polynomial interpolation).
23. G. D. Birkhoff’s problem. 24. Piecewise polynomial interpolation. 25. Bivariate splines. 26. Lattice structures involved.
Appendix A (Subdivided rectangular polygons).
1. Classification of rectangular polygons. 2. Cell addresses.
There are 110 references.
[This article was published in the book announced in this Zbl 0236.00006.]

MSC:

68-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science
68W99 Algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
94B99 Theory of error-correcting codes and error-detecting codes
94C11 Switching theory, applications of Boolean algebras to circuits and networks
93C05 Linear systems in control theory
68Q45 Formal languages and automata