Higher-Order and Symbolic Computation, 18(1/2)
Olivier Danvy, Fritz Henglein, Harry Mairson, and Alberto Pettorossi
This issue of HOSC is the second of two issues (Danvy et al., 2003)
dedicated to the memory of Bob Paige (1947-1999). The content of the
two issues, together with a few more contributions, will be collected
in a forthcoming book. The present issue opens with an obituary
written by Harry Mairson and reminiscences from two colleagues, Alan
Siegel and Martin Davis. The technical articles in this second issue
were contributed and formally reviewed.
In "Transformational Derivation of an Improved Alias Analysis
Algorithm," Deepak Goyal uses various techniques developed by Bob
Paige, dominated convergence and finite differencing, to derive a new
algorithm for the may-alias analysis and to establish its time
complexity. The new algorithm takes cubic time in the size of the
input and compares favorably to the previous best one, which was
In "Least Reflexive Points of Relations," Jules Desharnais and
Bernhard Möller consider a generalization of the problem of
finding conditions under which a function on a partially ordered set
has a least fixed point, and consider relations on complete lattices.
The authors present two main results about the existence of the least
fixed point, and a theorem of Cai and Paige for computing it.
In "Relativizations for the Logic-Automata Connection," Nils Klarlund
describes an efficient translation from logic M2L(str), a monadic
logic of strings, into a variant of WS1S, i.e., weak second-order
theory of one successor. The main issue is an efficient handling of
the first-order and (weak) second-order quantifiers. The algorithmic
treatment requires a detailed study of the corresponding
relativizations of formulas.
In "Derivation of Efficient Logic Programs by Specialization and
Reduction of Nondeterminism," Alberto Pettorossi, Maurizio Proietti,
and Sophie Renault propose an extension of both partial
evaluation/deduction and conjunctive partial deduction to specialize
non-deterministic programs. To this end, they consider definite logic
programs and a new set of transformation rules on top of the usual
fold/unfold/define rules used for partial evaluation.
We conclude this second issue with Bob's last NSF proposal. His last
two PhD students, Deepak Goyal and Zhe Yang, have graduated from New
York University; after a post-doctoral year at two major research
institutions, Goyal and Zhe now respectively work in a startup company
and in a major industrial research laboratory.
Danvy, O., F. Henglein, H. Mairson, and A. Pettorossi (eds.): 2003,
`Special Issue in Memory of Bob Paige (Part I)', Vol. 16, numbers 1
and 2 of Higher-Order and Symbolic Computation.