From: calendar@ALMADEN.IBM.COM (IBM Almaden Research Center Calendar)
Newsgroups: ba.seminars
Subject: IBM ARC seminars 08 - 12 SEP 92
Date: 4 Sep 92 21:33:01 GMT


                     IBM Almaden Research Center
                           650 Harry Road
                       San Jose, CA 95120-6099

                              CALENDAR

                         September 7-11, 1992


09/08 - NANOTRIBOLOGY STUDIES OF CARBON SURFACES BY FORCE MICROSCOPY
C. M. Mate, IBM, ARC, Interface Technology

Phys. Sci. Sem.    Tues., September 8    12:00 p.m.    Room:  J2-609

The frictional properties of different types of carbon
surfaces--graphite, diamond, hydrogenated amorphous carbon, and C60
buckminsterfullerene--have been studied in air at low loads (<1.5 mu m)
by friction force microscopy.  The frictional properties vary
dramatically from one type of carbon to another.  For example, the
coefficients of friction vary from 0.01 for graphite, 0.05 to 0.3 for
hydrogen-terminated diamond, 0.33 for hydrogenated amorphous carbon, to
0.8 for C60 buckminsterfullerence.  This talk is devoted to discussing
these differences in friction as well as the effect of topography on
friction.
Host:  C. Mathew Mate


09/09 - HIGHER-ORDER PARTIAL EVALUATION BASED ON POLYVARIANT
BINDING-TIME ANALYSIS
C. Consel, Oregon Graduate Institute, Dept. of Comp. Sci. and Eng.

Comp. Sci. Sem.    Wed., September 9    2:00 p.m.    Room:  B3-247

Partial evaluation is a program transformation technique based on
propagating constants, unfolding and specializing functions.

This talk describes our approach to binding-time based partial
evaluation of functional languages.  We illustrate this approach with
Schism:  our partial evaluation system for a dialect of Scheme, based on
a polyvariant binding-time analysis for higher-order functions and
partially static data.  Schism deals with untyped as well as typed
programs.  It includes a programming environment that consists of tools
aimed at monitoring the binding-time analysis and the specialization
phase.  A re-sugaring phase is also provided that produces a high-level
representation of residual programs.  Therefore, the proper
functionality of partial evaluation is fulfilled, that is, true
source-to-source program transformation.

This presentation is an overview of our approach and is illustrated with
concrete examples using Schism.
Host:  A. Aiken


09/11 - SOLVING INTERVAL CONSTRAINT PROBLEMS
P. Ladkin, IBM Almaden/Universitaet Bern

Comp. Sci. Sem.    Fri., September 11    1:30 p.m.    Room:  G2-301

Interval constraint problems are NP-complete, and generalize interval
graph problems from Operations Research.  They have been a focus of
research in AI stemming from work of Allen in 1983 on heuristic
scheduling in planning, and have applications ranging from scheduling to
DNA sequencing.  There is little published work on the characteristics
of solution algorithms, other than asymptotic estimates of behavior.  We
built a fast solution algorithm, using a mixture of pruning
(path-consistency computations) and search.

We performed large-scale experiments on randomly-generated problems, and
on guaranteed soluble problems with up to 500 variables and
approximately 10,000 constraints.

Our main result is that problems in which search has significance are
all to be found in the range 8 <= n.p <= 12, where n is the number of
variables, and p is the proportion of constraints that are not the
trivial constraint.

Continual pruning during search yields on average a sub-linear selection
of solution components.  On larger problems, pruning dominates, and
directly produces a solution without search in problems with over 300
variables.  We conclude that improving path-consistency computations is
more important than improving search.  It is an open problem to find
classes of large examples in which search dominates the computation
time.

This work is joint with Alexander Reinefeld.  Peter van Beek has
independently validated these results, and his suggestions have been
instrumental in designing experiments.
Host:  R. Fagin

-----------------------------------------------------------------------

For further information on individual talks, please contact the host
listed above.

Visitors, please arrive 15 minutes early.  IBM's Almaden Research
Center (ARC) is located adjacent to Santa Teresa County Park, between
Almaden Expressway and U.S. 101, about 10 miles south of Interstate
280.  From U.S. 101, exit at Bernal Road, and follow Bernal Road west
past Santa Teresa Blvd. into the hills (ignoring the left turn for
Santa Teresa Park).  Alternatively, follow Almaden Expressway to its
southern terminus, turn left onto Harry Road, then go right at the ARC
entrance (about a quarter of a mile later) and go up the hill.  For
more detailed directions, please phone the ARC receptionist at (408)
927-1080.

IBM Almaden Research Center electronically distributes both its
complete calendar of seminars and a subset of Computer Science
seminars only.  Send requests for inclusion in either electronic
mailing list to CALENDAR@ALMADEN.IBM.COM (CALENDAR at ALMADEN on
BITNET), specifying either the complete calendar or the Computer
Science subset.
Newsgroups: ba.seminars