Higher-Order and Symbolic Computation, 18(1/2)
EditorialOlivier 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 quintic. 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. References 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. |