Haskell code is developed for two ways to list the strings of the language defined by a regular expression: directly by set operations and indirectly by converting to and simulating an equivalent automaton. The exercise illustrates techniques for dealing with infinite ordered domains and leads to an effective standard form for nondeterministic finite automata.

We describe a precompression algorithm that effectively represents any long common strings that appear in a file. The algorithm interacts well with standard compression algorithms that represent shorter strings that are near in the input text. Our experiments show that some real data sets do indeed contain many long common strings. We extend the fingerprint mechanisms of our algorithm to a program that identifies long common strings in an input file. This program gives interesting insights into the structure of real data files that contain long common strings.

Power series and stream processing were made for each other. Stream algorithms for power series are short, sweet, and compositional. Their neatness shines through in Haskell, thanks to pattern-matching, lazy lists, and operator overloading. In a short compass one can build working code from ground zero (scalar operations) up to exact calculation of generating functions and solutions of differential equations.

Quicksort can be made to go quadratic by constructing input on-the-fly in response to the sequence of items compared. The technique is illustrated by a specific adversary for the standard C qsort function. The general method works against any implementation of quicksort – even a randomizing one – that satisfies certain very mild and realistic assumptions. Copyright © 1999 John Wiley & Sons, Ltd.

Abstract We recount the history of a new qsortfunction for a C library. Our function is clearer, faster and more robust than existing sorts. It chooses partitioning elements by a new sampling scheme; it partitions by a novel solution to Dijkstra's Dutch National Flag problem; and it swaps efficiently. Its behavior was assessed with timing and debugging testbeds, and with a program to certify performance. The design techniques apply in domains beyond sorting.

Abstract The original UNIX system was designed to be small and intelligible, achieving power by generality rather than by a profusion of features. In this spirit we have designed and implemented IX, a multilevel‐secure variant of the Bell Labs research system. IX aims at sound, practical security, suitable for private‐and public‐sector uses other than critical national‐security applications. The major security features are: private paths for safe cooperation among privileged processes, structured management of privilege, and security labels to classify information for purposes of privacy and integrity. The labels of flies and processes are checked at every system call that involves data flow and are adjusted dynamically to assure that labels on outputs reflect labels on inputs.

A concise, incremental algorithm for raster approximations to ellipses in standard position produces approximations that are good to the last pixel even near octant boundaries or the thin ends of highly eccentric ellipses. The resulting approximations commute with reflection about the diagonal and are mathematically specifiable without reference to details of the algorithm.

Abstract Data streams are an ideal vehicle for handling power series. Stream implementations can be read off directly from simple recursive equations that define operations such as multiplication, substitution, exponentiation and reversion of series. The bookkeeping that bedevils these algorithms when they are expressed in traditional languages is completely hidden when they are expressed in stream terms. Communicating processes are the key to the simplicity of the algorithms. Working versions are presented in newsqueak, the language of Pike's ‘squint’ system; their effectiveness depends critically on the stream protocol.

The problem of drawing an approximate circle on an integer x -y grid has a unique best solution in practical cases.If the center is (0, 0) and the square of the radius (r 2) is integral, then each grid line that intersects the circle contains near each intersection a unique grid point that simultaneously minimizes (1) the residual x 2 + y2 _ r 2, (2) Euclidean distance to the circle, and (3) displacement along the grid line from the intersection.Thus the set of such minimizing points is the "best" approximation to the circle in several natural senses.Criteria (1)-{3) collectively, but not severally, define unique approximate circles when half-integer center coordinates and integer squared diameters (4r ~) are admitted.In other cases the criteria may disagree.Simple, efficient, all-integer algorithms for drawing circles and arcs with approximately known endpoints follow from the analysis.Diophantine problems arise in connection with the occasional appearance of sharp (90 °) corners in the resulting approximations.

The numbers of occupancy states of linear or circular arenas for dynamic storage allocation of immovable blocks of arbitrary size are expressed simply in terms of Fibonacci numbers, as are the numbers of equivalence classes of states induced by reflective and rotational symmetries.

The word list used by the UNIX spelling checker, SPELL, was developed from many sources over several years. As the spelling checker may be used on minicomputers, it is important to make the list as compact as possible. Stripping prefixes and suffixes reduces the list below one third of its original size, hashing discards 60 percent of the bits that remain, and data compression halves it once again. This paper tells how the spelling checker works, how the words were chosen, how the spelling checker was used to improve itself, and how the (reduced) list of 30000 English words was squeezed into 26000 16-bit machine words.

Closed formulas provide tight bounds for $G(n)$, the total number of 1’s in the binary representations of integers less than n. This function satisfies an extremal recurrence, which gives the maximum cost of a process that creates a set of n objects by repeatedly merging pairs of smaller sets, starting from n singletons, incurring a cost equal to the size of the smaller set at each merger: \[ G(n) = \max\limits_{1 \leqq i \leqq n /2} [i + G(i) + G(n - i)], \] where $G(1) = 0$. The set of pairs $(i,n - i)$ at which the maximum is attained has an interesting structure.