In [Paige89], it was shown how to simulate a set machine in real-time on a RAM that provides cursor or even only pointer access to data. The underlying assumption was that the establishment of efficient data structures would be provided by some 'client' program. In the current paper, we fill in the gap by presenting a linear-time high level reading method that translates external input in string form into data structures that facilitate such real-time simulation. The algorithm builds the data structures for a much richer type system than what appeared in [Paige94], and is powerful enough to support our reading algorithm itself in an efficient way. Consequently, it equips a high level set-theoretic language with I/O, without the loss of computational transparency.This work alleviates the burden of creating low-level data structures manually, and builds the internal pointer-based inputs required by most pointer algorithms [Ben-Amram95] from the external string representation.

There are two principal methods for turning regular expressions into NFA's — one due to McNaughton and Yamada and another due to Thompson. Unfortunately, both have drawbacks. Given a regular expression R of length r and with s occurrences of alphabet symbols, Chang and Paige (1992) and Brüggemann-Klein (1993) gave Θ(m + r) time and O(r) space algorithms to produce a Θ(m) space representation of McNaughton and Yamada's NFA with s + 1 states and m transitions. The problem with this NFA is that m = Θ(s2) in the worst case. Thompson's method takes Θ(r) time and space to construct a Θ(r) space NFA with Θ(r) states and Θ(r) transitions. The problem with this NFA is that r can be arbitrarily larger than s. We overcome drawbacks of both methods with a Θ(r) time Θ(s) space algorithm to construct an O(s) space representation of McNaughton and Yamada's NFA. Given any set V of NFA states, our representation can be used to compute the set U of states one transition away from the states in V in optimal time O(¦V¦ + ¦U¦). McNaughton and Yamada's NFA requires Θ(¦V¦ × ¦U¦) time in the worst case. Using Thompson's NFA, the equivalent calculation requires Θ(r) time in the worst case. Comparative benchmarks show that an implementation of our method outperforms implementations of competing methods with respect to time for NFA construction, NFA accepting testing, and NFA-to-DFA conversion by subset construction. Throughout this paper program transformations are used to design algorithms and derive programs. A transformation of special importance is a form of finite differencing used previously by Douglas Smith to improve the efficiency of functional programs.

The paper reports on the development of a 2D geometric constraint solver. The solver is a major component of a new generation of cad systems based on a high-level geometry representation. The solver uses a graph-reduction directed algebraic approach, and achieves interactive speed. The paper describes the architecture of the solver and its basic capabilities. Then, it discusses in detail how to extend the scope of the solver, with particular emphasis on the theoretical and human factors involved in finding a solution, in an exponentially large search space, so that the solution is appropriate to the application, and so that the way of finding it is intuitive for an untrained user.

A transformational methodology is described for simultaneously designing algorithms and developing programs. The methodology makes use of three transformational tools — dominated convergence, finite differencing, and real-time simulation of a set machine on a RAM. We ilustrate the methodology to design a new O(mn + n2)-time algorithm for deciding when n-state, m-transition processes are ready similar, which is a substantial improvement on the ⊖(mn6) algorithm presented in Bloom (1989). The methodology is also used to derive a program whose performance, we believe, is competitive with the most efficient hand-crafted implementation of our algorithm. Ready simulation is the finest fully abstract notion of process equivalence in the CCS setting.

It is generally assumed that hashing is essential to solve many language processing problems efficiently; e.g. symbol table formation and maintenance, grammar manipulation, basic block optimization, and global optimization. This paper questions this assumption, and initiates development of an efficient alternative compiler methodology without hashing or sorting. The methodology rests on efficient solutions to the basic problem of detecting duplicate values in a multiset, which we call multiset discrimination. Paige and Tarjan (1987) gave an efficient solution to multiset discrimination for detecting duplicate elements occurring in a multiset of varying length strings. The technique was used to develop an improved algorithm for lexicographic sorting, whose importance stems largely from its use in solving a variety of isomorphism problems (Aho et al., 1974). The current paper and a related paper (Paige, 1994) show that full lexicographic sorting is not needed to solve these isomorphism problems, because they can be solved more efficiently using straightforward extensions to the simpler multiset discrimination technique. By reformulating language processing problems in terms of multiset discrimination, we also show how almost every subtask of compilation can be solved without hashing in worst case running time no worse (and frequently better) than the best previous expected time solution (under the assumption that one hash operation takes unit expected time). Because of their simplicity, our solutions may be of practical as well as theoretical interest. The various applications presented culminate with a new algorithm to solve iterated strength reduction folded with useless code elimination that runs in worst case asymptotic time and auxiliary space Θ(¦L¦ + ¦L'¦), where ¦L¦ and ¦L'¦ represent the lengths of the initial and optimized programs, respectively. The previous best solution due to Cocke and Kennedy (1977) takes Ω(¦L¦3¦L'¦) has operations in the worst case.

This paper reports experimental results that support the feasibility of a new transformational approach developed by the authors for implementing complex algorithms correctly and efficiently. The class of algorithms amenable to our methods includes nonnumerical graph algorithms. Experiments were performed to measure how this approach affects productivity (in terms of the number of source lines in the implementation divided by manual programming time) and running times. Comparative benchmarks showed that productivity can be increased over a conventional ad hoc approach by factors ranging from 5.1 to 9.9 Preliminary results also showed that the running time of C code produced by this new approach can be as fast as 1.5 times that of tightly coded high quality Fortran.

Pattern matching in trees is fundamental to a variety of programming language systems. However, progress has been slow in satisfying a pressing need for general-purpose pattern-matching algorithms that are efficient in both time and space. We offer asymptotic improvements in both time and space to Chase's bottom-up algorithm for pattern preprocessing. A preliminary implementation of our algorithm runs ten times faster than Chase's (1987) implementation on the hardest problem instances. Our preprocessing algorithm has the advantage of being on-line with respect to pattern additions and deletions. It also adapts to favorable input instances, and on Hoffmann and O'Donnell's (1982) class of simple patterns, it performs better than their special-purpose algorithm tailored to this class. We show how to modify our algorithm using a new decomposition method to obtain a space/time tradeoff. Finally, we trade a log factor in time for a linear space bottom-up pattern-matching algorithm that handles a wide subclass of Hoffmann and O'Donnell's (1982) simple patterns.

It is generally assumed that hashing is essential to many algorithms related to efficient compilation; e.g., symbol table formation and maintenance, grammar manipulation, basic block optimization, and global optimization.This paper questions this assumption, and initiates development of an efficient alternative compiler methodology without hashing or sorting.Underlying this methodology are several generic algorithmic tools, among which special importance is given to Multiset Discrimination, which partitions a multiset into blocks of duplicate elements.We show how multiset discrimination, together with other tools, can be tailored to rid compilation of hashing without loss in asymptotic performance.Because of the simplicity of these tools, our results maybe of practical as well as theoretical interest.The various applications presented culminate with a new algorithm to solve iterated strength reduction folded with useless code elimination that runs in worst case asymptotic time and auxiliary space linear in the maximum text length of the initial and optimized programs.1. Introduction.with linear search time and a hash table.They also pro-An important practical and theoretical question in Computer Science is whether there are algorithms whose worst case performance can match the expected performance of solutions that utilize hashing.In the context of this broader question, we initiate an investigation of efficient compilation without hashing and, consequently, raise some doubts about the prevailing view that hashing (e.g., universal hashing [5]) is essential to the various 2. The research of this author was partiatly

An important research goal in software engineering and programming languages is the development of principles underlying the specification of computable problems, the translation of these problems into efficient and correct programs, and the performance analysis of these programs. This paper uncovers some of these principles, which are used to design a problem specification language L1 restricted to problems that can be compiled automatically into programs whose worst case asymptotic time and space complexities are linear in the input/output space. Any problem expressible in L1 can be compiled into a linear cost program. A compiler for L1 has been implemented in the RAPTS transformational programming system.

We present improved partition refinement algorithms for three problems: lexicographic sorting, relational coarsest partition, and double lexical ordering. Our double lexical ordering algorithm uses a new, efficient method for unmerging two sorted sets.

Ten years ago Cheatham and Wegbreit [4] proposed a transformational program development methodology based on notions of top-down stepwise program refinement first expressed by Dijkstra [10] and Wirth [45]. A schema describing the process of this methodology is given in fig. 1. To develop a program by transformation, we first specify the program in as high a level of abstraction and as great a degree of clarity as our programming language admits. This high level problem statement program P is proved correct semimechanically according to some standard approach (see Flovd and Hoare [15, 21]), Next, using an interactive system equipped with a library of encoded transformations, each of which maps a correct program into another equivalent program, we select and apply transformations one at a time to successive versions of the program until we obtain a concrete, low level, effecient implementation version P'. The goals of transformational programming are to reduce programming labor, improve program reliability, and upgrade program performance. In order for labor to be reduced, the effort required to obtain P, prove it correct, and derive P' by transformation should be less than the effort required to code P from scratch, and also to debug it. Program reliability will be improved if P can be certified correct, and if each transformation preserves program meaning. Finally, program performance will be upgraded if transformations are directed towards increased efficiency.

Finite differencing is a program optimization method that generalizes strength reduction, and provides an efficient implementation for a host of program transformations including "iterator inversion."Finite differencing is formally specified in terms of more basic transformations shown to preserve program semantics.Estimates of the speedup that the technique yields are given.A full illustrative example of algorithm derivation is presented.