COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.REQUIRE "ABSTRA.CMD[BIB,CSR]" SOURCE FILE
C00003 00003	.once center <<general instructions>>
C00005 00004	%3STAN-CS-78-781  SET REPRESENTATION AND SET INTERSECTION
C00009 00005
C00011 ENDMK
C⊗;
.REQUIRE "ABSTRA.CMD[BIB,CSR]" SOURCE FILE
.every heading (December Reports,,{Page})
.at "∞" ⊂"%4α∞%*"⊃
.next page
.once center <<general instructions>>
%3MOST RECENT CS REPORTS - DECEMBER 1978%1

@Listed below are abstracts of the most recent reports published by the Computer
Science Department of Stanford University.

@TO REQUEST REPORTS:##Check the appropriate places on the enclosed order form,
and return the entire order form page (including mailing label) by
December 4, 1978.
In many cases we can print only a limited number of copies, and requests will
be filled on a first come, first serve basis.  In the code (FREE) is printed
on your mailing label, you will not be charged for hardcopy.  This exemption
from payment is limited primarily to libraries.  (The costs shown include all
applicable sales taxes.  PLEASE SEND NO MONEY NOW, WAIT UNTIL YOU GET AN INVOICE.)

@ALTERNATIVELY:  Copies of most Stanford CS Reports may be obtained by writing
(about 2 months after MOST RECENT CS REPORTS listing) to NATIONAL TECHNICAL
INFORMATION SERVICE, 5285 Port Royal Road, Springfield, Virginia 22161.  Stanford
Ph.D. theses are available from UNIVERSITY MICROFILMS, 300 North Zeeb Road,
Ann Arbor, Michigan 48106.
.begin nofill
%4-------------------------------------------------------------------------------------%1
%3STAN-CS-78-781  SET REPRESENTATION AND SET INTERSECTION
%3Author:%1  Luis Trabb Pardo
.end
@%3Abstract:%1@This work discusses the representation and manipulation of sets
based on two different concepts:  tries, and hashing functions.

@The sets considered here are assumed to be static:  once created, there will
be no further insertions or deletions.  For both trie- and hash-based strategies,
a series of representation is introduced which together with the availability
of preprocessing reduces the average sizes of the sets to nearly optimal values,
yet retains the inherently good retrieval characteristics.

@The intersection procedure for trie-based representations is based on the
traversal in parallel of the tries representing the sets to be intersected, and
it behaves like a series of binary searches when the sets to be intersected are
of very different sizes.  Hashed intersection runs very fast.  The average time
is proportional to the size of the smallest set to be intersected and is
independent of the number of sets (except for the intersection set itself which
has to be checked for every set).
.break
.begin nofill
No. of pages:  85
Cost:  $ 4.10
%4-------------------------------------------------------------------------------------%1
%3STAN-CS-78-782  PARSING FLOWCHARTS AND SERIES-PARALLEL GRAPHS
%3Author:%1  Jacobo Valdes ↔(Thesis)
.end
@%3Abstract:%1@The main results presented in this work are an algorithm for the
recognition of General Series Parallel (GSP) digraphs and an approach to the
structural analysis of the control flow graphs of programs.

@The GSP recognition algorithm determines in O(%2n+m%1) steps whether an acyclic
digraph with %2n%1 vertices and %2m%1 edges is GSP, and if it is, describes its
structure in terms of two simple operations on digraphs.  The algorithm is based
on the relationship between GSP digraphs and the more standard class of TTSP
multidigraphs.

@Our approach to the analysis of flow graphs uses the triconnected components
algorithm to find single-entry, single-exit regions.  Under certain
conditions -- that we identify -- this method will produce structural information
suitable for the global flow analysis of control flow graphs in time proportional
to the numer of vertices and edges of the graph being analyzed.
.break
.begin nofill
No. of pages:  233
Cost:  Available in microfiche only.
%4-------------------------------------------------------------------------------------%1