Miscellaneous Subjects

Literature references and annotations by Dick Grune, dick@dickgrune.com.
Last update: Mon Sep 09 11:15:10 2024.

These references and annotations were originally intended for personal use and are presented here only in the hope that they may be useful to others. There is no claim to completeness or even correctness. Each annotation represents my understanding of the text at the moment I wrote the annotation.
No guarantees given; comments and content criticism welcome.

Jan Willen Klop, A Wonderful Stream, in Liber Amicorum Jaco de Bakker, ed. by Frank de Boer, et al., Amsterdam, CWI, 2002, pp. 125-142.
Entertaining but serious work on the Thue-Morse sequence. The sequence is related to square-free sequences, process algebra, the Toeplitz stream, various algebras of streams, the Mephistowals, and to various tilings (tessellations), which are shown in full color.

Jan Friso Groote, Bits, trits, qits, pits of hits, (in Dutch: Bits, Trits, Qits, Pits or Hits), in Liber Amicorum Jaco de Bakker, ed. by Frank de Boer, et al., Amsterdam, CWI, 2002, pp. 89-92.
In addition to the two-state bit, introduces the three-state trit, the four-state qit, the five-state pit, and the six-state hit. Then demonstrates that, for a given number of states, trits allow more numbers to be represented than any of the other N-its. For example, given 12 states, one could set up 6 (12/2) bits with them, allowing $ 2 sup 6 = 64 $ numbers to be represented. But one can also acquire 4 trits (12/3) with them, allowing $ 3 sup 4 = 81 $ numbers to be represented! Equipping 3 qits with the 12 states gives us $ 4 sup 3 = 64 $ numbers again. No proof given.

Jan van Eijck, De Thue Morse reeks (Afscheid van Jaco), (in Dutch: The Thue Morse Sequence (Farewell to Jaco)), in Liber Amicorum Jaco de Bakker, ed. by Frank de Boer, et al., Amsterdam, CWI, 2002, pp. 61-77.
A playful treatment of the Thue-Morse sequence, the sequence S in which $ S_2n ... S_2(n+1)-1 $ is the inverse (and the reverse) of $ S_0 ... S_2n-1 $. With examples programmed in Haskell.

Henry G. Baker, March Möbius madness, with a polynomial postscript March 32, 1998, ACM SIGPLAN Notices, vol. 33, #3, March 1998, pp. 24-35.
Amusing account of finding roots of polynomials, with awful puns.

Helmut Kopka, Patrick W. Daly, A Guide to LaTeX 2e, (2nd Edn.), Addison-Wesley, Wokingham, UK, 1995, pp. 553.
Accessible guide, "for beginners and advanced users", as is says --correctly-- in the subtitle. Covers everything, from lists of all funny characters to advice on how to maintain a bibtex file. The last 125 pages are command and book indexes, very useful.

Günter Born, The File Formats Handbook, Int. Thomson Computer Press, London, 1995, pp. 1274.
Extensive descriptions of some 90 formats, mainly from the PC world: data bases, spreadsheets, word processors, graphics, Windows and OS/2, sounds, and page descriptions. Most of them are binary formats, but PCL, SGML, RTF and PostScript are included. No mention of uuencode or MIME formats. Some of the formats have been constructed by reverse engineering (for example the Windows GRP file format).
     The book consists mainly of tables and the interspersed text is terse. Occasionally the author just uses a wrong word, which given the low redundancy of the text can be confusing. The JPEG format is described but its meaning and the process is not explained (perhaps wisely so).

Simon L. Peyton Jones, John Hughes, John Launchbury, How to give a good research talk, ACM SIGPLAN Notices, vol. 28, #11, Nov. 1993, pp. 9-12.
Tons of good advice, for example, ask yourself "If someone remembers only one thing from my talk, what would I like it to be?".

Henry G. Baker, Complex Gaussian integers for 'Gaussian graphics', ACM SIGPLAN Notices, vol. 28, #11, Nov. 1993, pp. 22-27.
Fascinating account of the properties of complex Gaussian integers, and their use in the design of graphic screens. Full of footnotes, puns and oblique references.

Yiya Yang, Anatomy of the design of an undo support facility, Int. J. Man-Machine Studies, vol. 36, 1992, pp. 81-95.
Describes the design decisions that went into an extended form of the Emacs undo facility, and is mainly concerned with the user aspects and ease of use; the implementation of the Emacs undo is taken for granted. Based on the author's PhD thesis.

Benjamin C. Pierce, Basic Category Theory for Computer Scientists, Foundations of Computing, MIT Press, Cambrigde, Mass., 1991, pp. 100.
Incomprehensible right from page 1, I'm sorry to say.

Igor Aleksander, Helen Morton, An Introduction to Neural Computing, Chapman & Hall, London, 1990, pp. 240.
A neuron is a specialized cell with about a dozen cord-like protuberances, called dendrites. One dendrite, the axon, is much longer than the others and serves as the output cord. The signal is passed down the axon along a number of relay stations, "nodes", to sequentialize things. The sides of the other dendrites serve as input connection places for the axons of other neurons; these connections are called "synapses". The synapses do not constitute electric connections. When the signal arrives at the synapse, it releases neurotransmitters, which cross the synaptic cleft to excite the post-synaptic membrane of the receiving dendrite. Depending on the nature of the post-synaptic membrane at that synapse, it will admit more or fewer positive or negative ions into the dendrite and thus into the neuron. If enough positive ions are amassed, the neuron fires.
     An artificial neuron (according to McCulloch & Pitts) consists of a set of weights, one for each input, and a function. The weighted sum of the inputs is calculated at time t and fed into the function to obtain the output at time t+1. It is not unusual for one or more of the weights to be so negative as to inhibit any output if the corresponding input is non-zero.
     There are two main questions here: can a given configuration of artificial neurons exhibit a given input-output behaviour; and if so, how do we find the weights.
     A single neuron with N inputs can only implement a flat linear cut through N-space; so it certainly cannot detect parity in its inputs.
     A perceptron is a neuron that can detect relations between its inputs. To this end, groups of its inputs are first fed into so-called association units. Association units are like neurons, except that their inputs are not weighted: they are just added and the sum is compared to a threshold. If the threshold is exceeded, the association unit fires. The outputs of the association units are the inputs to a traditional McCulloch & Pitts neuron. All this hardware together is called the perceptron.
     A perceptron is more powerful than a single neuron: it is much better at recognizing shapes. Still, it cannot detect parity, connectedness, etc.
     Full Boolean expressions can be handled by two-layer networks: one layer does the And-s and the second (one-neuron) layer does the Or-s, or vice versa. Single neurons are easy to train, perceptrons are more difficult and two-layer networks are very difficult.
     An example is the multi-discriminator system WISARD, the input to which is supposed to consist of many bits, e.g. N x N. The WISARD contains a number of discriminators, one for each shape to be recognized (e.g. an A, a B, etc.) and a comparison unit. Each discriminators contains a number of decoders and a summing device. Each decoder is connected to a subset of the input, say k bits, uses the k bits to address an array of 2^k 1-bit integers and yields the integer found. A summing device sums the integers from the decoders, and yields the result of the the discriminator. The comparison unit picks the highest discriminator result and declares the corresponding shape recognized. When taught properly (to teach = to set the arrays) a WISARD can distinguish between a picture of a room with a person in it and one without one (intruder detection).
     A second simplification to the arbitrarily connected network with arbitrary weights is the Hopfield net. In a Hopfield net, all connections are bidirectional and symmetric (which they certainly aren't in practice!). All neurons are supposed to fire at arbitrary but frequent intervals, until an equilibrium is reached.
     For a Hopfield net, an energy function can be defined: each state change of a neuron will decrease the energy. Thus the system will settle in a local minimum-energy state. A network with N neurons has 2^N states, only a few of which are minima.
     Sample application: a network to distinguish between predominantly horizontal and predominantly vertical patterns. Suppose 16 input values are derived from the pattern (in a 4x4 matrix). Then the net must have 16 neurons, and the input values are their initial states. The network is then trained to have two minima, horizontal and vertical, using a number of training patterns. Then, given an arbitrary pattern as initial state, the net will settle in one of these two minima.
     During training false minima develop. Also, as with the McCulloch & Pitts model, the Hopfield net cannot recognize parity.
     False minima cannot be avoided, but the system can be prevented from settling in one, by shaking ("heating") the system. Initially, a percentage of transitions in which the energy increases is allowed, depending on the virtual temperature. As this virtual temperature is reduced ("simulated annealing"), this percentage decreases. This increases the likelihood of the system settling in a deep minimum. A Hopfield net with simulated annealing is called a "Boltzmann machine".
     The parity problem can again be solved by adding hidden neurons, i.e. neurons not directly initialized by the input. As usual, this makes teaching the net a lot harder. Techniques for teaching Hopfield and Boltzmann nets are: "clamping", in which a number of input values are clamped (fixed) to the correct output value; effectively this teaches the net to handle a subproblem, which is then extended by freeing more and more output values. And "error propagation", in which sets of differential equations are used to determine the direction in which errors must be propagated to achieve the desired effect; this is effectively curve fitting on the entire net.

Ben Shneiderman, Greg Kearsley, Hypertext Hands-On!: An Introduction to a New Way of Organizing and Accessing Information, Addison-Wesley, Reading, Mass., 1989, pp. 165.
Hypertext intends to be the screen version of book text. Information in Hypertext is stored in (small) records, each fitting on one or two screens; terms (words) in the text may be connected through hyperties to other records. Such words are highlighted and the trails laid out by them can be followed forward and backward. There are various other facilities.

David Barron, Mike Rees, Text Processing and Typesetting with Unix, Addison-Wesley, Reading, Mass., 1987,
Mainly about nroff.

Sandra L. Emerson, Karen Paulsell, troff Typesetting for UNIX Systems, Prentice-Hall, Englewood Cliffs, NJ, 1987, pp. 359.
Entertaining and knowledgeable. Treats troff primitives, macro writing, escape sequences, -ms, -mm, -man, tbl, eqn, the typesetting pipeline, and ditroff.

David Harel, Algorithms, The Spirit of Computing, Addison-Wesley, Wokingham, England, 1987, pp. 425.
Excellent introductory book to CS and algorithms.

Jeffrey D. Ullman, Computational Aspects of VLSI, Computer Science Press, Rockville, Md, 1984, pp. 495.
General treatment of same: models, lower bounds, layout algorithms, processor organization, systolic algorithms, high-wire, existing design systems, silicon compilation, optimization, and general algorithms.

Herman Koningsveld, Het verschijnsel wetenschap -- Een inleiding tot de wetenschapsfilosofie, (in Dutch: Science as a phenomenon -- Introduction to science philosophy), Boom, Meppel, 1978, pp. 211.
From Hume to Feyerabend.

Kim Gostelow, Vincent G. Cerf, Gerald Estrin, Saul Volansky, Proper termination of flow-of-control in programs involving concurrent processes, (ACM Annual Conference, Vol II, pp. 742-754), ACM SIGPLAN Notices, vol. 7, #11, Nov. 1972, pp. 15-27.
Communicating parallel programs are modeled using a token machine operating on a complex bigraph, which is an extension of a Petri net. A complex directed graph is a directed graph in which the arcs are complex arcs. A complex arc is a (named) arc that runs from a set of nodes to a set of nodes.
     Resources (processors, data, open files, tape units, etc.) are modeled as tokens that are absorbed by and produced by nodes. For each node N there is a (restricted) Boolean expression, depending on the presence of tokens on the incoming complex arcs of N, and telling if N may fire; if N fires the required tokens are consumed. There is also a formula which tells how many tokens are produces on which outgoing complex arcs of N when N terminates.
     The token machine starts with exactly one token on the start arc of the complex bigraph [why bi-??] of the program, and terminates properly when there is exactly one token on the outgoing arc of the bigraph, and no other tokens are left behind. A program is properly terminating if there is no run of the token machine that can terminate improperly.
     To compute proper termination, the complex bigraph is transformed into a computation flow graph, using rules given in the paper. The program will terminate properly iff the computation flow graph is finite and all states have a path to the final state. This transformation is computation-intensive, and a faster algorithm is given, which reduces the computation flow graph. No cost analysis of the algorithm is given.

Friedrich L. Bauer, Andrei und das Untier, (in German: Andrei and the Monster), Bayrischer Schulbuch-Verlag, München, 1972, pp. 80.
Six amusing non-trivial lessons in computer science, for children and adults: 1. the nature of commands; 2. modification of commands; parameters; repetition; 3. conditions; recursion; 4. variables; 5. nesting; structs/records; 6. linked lists; graphs; transition diagrams. Programs are in a simple Algol68 with German keywords. Great pains are taken in explaining the concept of a variable, culminating in the Algol 68 definition 'ref' 'int' i = 'loc' 'int'. Parameter packs are recognized as an instance of structs! The chess example in Chapter 6 is very complicated. An appendix on the history of computer science in a much more academic style closes the book.
     The story is set in Russia/Georgia, using Russian names and occasionally using Russian and Georgian letters for identifiers; the author explains this from the book being conceived during his stay in Novosibirsk.

Leo Geurts, Lambert Meertens, Reind van de Riet, Aad van Wijngaarden, Physionomie, psyche en chironomie, Mathematisch Centrum, Amsterdam, Oct. 4, 1969, pp. 32.
Very early example of morphing. The first 3 pages give a derivation of a morphing algorithm, presented jokingly as the "diffusion of physionomy and psyche", controlling the development using a variable $\chi$. It is the applied in the next 25 pages to the morphing of the portrait of the parting curator and geometrical algebra expert Prof. J.A. Schouten into the symbol for the Lie derivative $ \math L \over v $. At the end $\chi$ becomes negative...

J. Riguet, Programmation et th\'eories de catégories, (in French: Programming and category theory), in Symposium on Symbolic Languages in Data Processing, Gordon and Breach, New York, 1962, pp. 83-98.
After a very accessible introduction to category theory, the latter is used to construct a model of computation. Function composition in category theory is compared to transition composition in a special kind of FS automaton. This FS automaton has two kinds of transitions: choice transitions, which are marked with strings from the language and which can be taken when a segment of the data matches the string; and action transitions, which are marked with an action to be performed on the data. Each state has either a set of outgoing choice transitions or a single outgoing action transition. An algorithm for multiplication in the unary system is given for this model; it is Turing-machine-like. Remarkably, the explanation of the programming model and the example can be understood without reference to the category theory part.

Grace Murray Hopper, The education of a computer, in Proc. ACM National Conference, Pittsburgh PA, ACM, 1952,
reprinted in Annals of the History of Computing, Vol. 9, No. 3/4, 1988, pp. 271-281.