Miscellaneous Subjects
Literature references and annotations by Dick Grune, dick@dickgrune.com.
Last update: Tue Aug 10 09:12:48 2010.
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.
"The LaTeX Graphics Companion",
2nd Edition,
Michel Goossens,
Frank Mittelbach,
Sebastian Rahtz,
Denis Roegel,
Herbert Voß,
Addison Wesley,
Upper Saddle River, NJ.,
2007,
pp. 976.
Thomas J. Bergin,
"Oral History, Interview with Jean_Sammet",
pp. 78.
2006,
Jan Willen Klop,
"A Wonderful Stream",
in Liber Amicorum Jaco de Bakker,
ed. by Frank de Boer, et al.,
Amsterdam,
CWI,
2002,
pp. 125142.
Entertaining but serious work on the ThueMorse sequence.
The sequence is related to squarefree 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. 8992.
In addition to the twostate bit, introduces
the threestate trit,
the fourstate qit,
the fivestate pit, and
the sixstate hit.
Then demonstrates that, for a given number of states, trits allow more
numbers to be represented than any of the other Nits.
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. 6177.
A playful treatment of the ThueMorse sequence, the sequence S in which
S_2n ... S_2(n+1)1 is the inverse (and the reverse) of S_0 ... S_2n1 .
With examples programmed in Haskell.
Eleanor Rieffel,
Wolfgang Polak,
"An introduction to quantum computing for nonphysicists",
ACM Computing Surveys,
32,
#3,
Sept. 2000,
pp. 300335.
Harry R. Lewis,
Christos H. Papadimitriou,
"Elements of the Theory of Computation",
PrenticeHall,
Upper Saddle River, New Jersey 07458,
1998,
pp. 361.
Henry G. Baker,
"March Möbius madness, with a polynomial postscript March 32, 1998",
ACM SIGPLAN Notices,
33,
#3,
March 1998,
pp. 2435.
Amusing account of finding roots of polynomials, with awful puns.
Helmut Kopka,
Patrick W. Daly,
"A Guide to LaTeX 2e",
2nd Edn.,
AddisonWesley,
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).
Martin D. Davis,
Ron Sigal,
Elaine J. Weyuker,
"Computability, Complexity and Languages",
Academic Press,
???,
1994,
pp. 609.
Leslie Lamport,
"Latex  A Document Preparation System",
Addison Wesley,
Boston,
1994,
pp. 272.
Simon L. Peyton Jones,
John Hughes,
John Launchbury,
"How to give a good research talk",
ACM SIGPLAN Notices,
28,
#11,
Nov. 1993,
pp. 912.
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,
28,
#11,
Nov. 1993,
pp. 2227.
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.
Christos H. Papadimitriou,
"Computational complexity",
Reading, Mass.,
AddisonWesley,
1993,
pp. ???.
Yiya Yang,
"Anatomy of the design of an undo support facility",
Int. J. ManMachine Studies,
36,
pp. 8195.
1992,
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.
Donald E. Knuth,
"3:16  Bible Texts Illuminated",
AddisonWesley,
1991,
pp. 268.
M. O'Connor,
"Writing Successfully in Science",
E. & F.N. Spon,
???,
1991,
pp. 242.
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 cordlike 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 postsynaptic membrane of the receiving
dendrite.
Depending on the nature of the postsynaptic 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 nonzero.
There are two main questions here: can a given configuration of artificial
neurons exhibit a given inputoutput behaviour; and if so, how do we find the
weights.
A single neuron with N inputs can only implement a flat linear cut through
Nspace; 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 socalled 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 twolayer networks: one layer does
the Ands and the second (oneneuron) layer does the Ors, or vice versa.
Single neurons are easy to train, perceptrons are more difficult and twolayer
networks are very difficult.
An example is the multidiscriminator 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 1bit 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 minimumenergy 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.
"Adaptive Pattern Recognition and Neural Networks",
YohHan Pao,
Reading, Mass.,
AddisonWesley,
1989,
pp. 309.
Ben Shneiderman,
Greg Kearsley,
"Hypertext HandsOn!: An Introduction to a New Way of Organizing and Accessing Information",
AddisonWesley,
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",
AddisonWesley,
Reading, Mass.,
1987,
Mainly about nroff.
Sandra L. Emerson,
Karen Paulsell,
"troff Typesetting for UNIX Systems",
PrenticeHall,
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",
AddisonWesley,
Wokingham, England,
1987,
pp. 425.
Excellent introductory book to CS and algorithms.
E.W. Dijkstra,
"A belated proof of selfstabilization",
Distrib. Comput.,
1,
#??,
pp. 56.
1986,
Dominique Commiot,
"Minitel  En savoir plus",
in French: Minitel  Know more about it,
SESA / La nouvelle librairie,
1985,
pp. 60.
Konrad Zuse,
"Der Computer  Mein Lebenswerk",
in German: The Computer  My Life's Work,
SpringerVerlag,
Berlin,
1984,
pp. 218.
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, highwire, existing design
systems, silicon compilation, optimization, and general algorithms.
W.A. Wulf,
M. Shaw,
P.N. Hilfinger,
L. Flon,
"Fundamental Structures of Computer Science",
AddisonWesley,
Reading, Mass.,
1981,
pp. ???.
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.
W.A. Wickelgren,
"How to Solve Problems: Elements of a Theory of Problems and Problem Solving",
Freeman,
San Francisco,
1974,
E.W. Dijkstra,
"Selfstabilizing systems in spite of distributed control",
Commun. ACM,
17,
#??,
pp. 643644.
1974,
Kim Gostelow,
Vincent G. Cerf,
Gerald Estrin,
Saul Volansky,
"Proper termination of flowofcontrol in programs involving concurrent processes",
ACM Annual Conference, Vol II, pp. 742754,
ACM SIGPLAN Notices,
7,
#11,
Nov. 1972,
pp. 1527.
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 computationintensive, 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 SchulbuchVerlag,
München,
1972,
pp. 80.
Six amusing nontrivial 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.
N. de Bruijn,
"Lambdacalculus notation with nameless dummies: A tool for automatic formula manipulation",
Indag. Mat.,
34,
1972,
pp. 381392.
Thomas S. Kuhn,
"The Structure of Scientific Revolutions",
International Encyclopedia of Unified Science,
University of Chicago Press,
Chicago,
1970,
pp. 210.
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. 8398.
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 Turingmachinelike.
Remarkably, the explanation of the programming model and the example can
be understood without reference to the category theory part.
D.E. Knuth,
"A history of writing compilers",
Computers and Automation,
11,
#12,
pp. 814.
1962,
D.E. Knuth,
"History of writing compilers",
in Proc. ACM 17th National Conference,
ACM,
pp. 43126.
1962,
G. Polya,
"How to Solve It",
Doubleday,
Garden City, N.Y.,
1957,
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. 271281.
S.C. Kleene,
"Introduction to Metamathematics",
D. Van Nostrand Company,
New York,
1952,
