E1AR0002@SMUVM1.BITNET (10/20/86)
Copies of the following reports may be requested from
Technical Reports
Computer Science Department
Washington State University
Pullman, WA 99164-1210
U.S.A.
Single copies are free of charge
%R CS-85-140 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T PROCESSOR UTILIZATION IN A LINEARLY CONNECTED PARALLEL PROCESSING SYSTEM
%A Michael R. Fellows
%A Michael A. Langston
%X We study the problem of assigning program fragments to a system of
processing elements in which low-level
operations are performed in parallel. Such a
system, made realistic by the rapid advances in VLSI technology, is said to
be linearly connected if each processing element can only communicate
directly with its two nearest neighbors. We show that the problem of
determining whether a perfect assignment exists is NP-complete, but can be
solved in linear time if the numbers of processing elements is fixed.
Furthermore, we demonstrate that the related problem of determining whether any
assignment exists which can be performed in a given number of machine cycles is
NP-complete. For this problem, whose objective corresponds to minimizing the
program fragment's execution time, we also investigate the behavior of
classes of near-optimal heuristic algorithms. We present evidence to
indicate that guaranteeing acceptable worst-case performance is a very
difficult problem as well.
%R CS-85-141 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T ENCODING GRAPHS IN GRAPHS
%A Michael R. Fellows
%X The subject of this dissertation is a theory of encodings of graphs
in graphs.
The following are some simple examples of problems to which the theory can be
applied.
.sp
(1) Suppose a record is to be maintained of the current state from among a set
of four possible states, between which any transition may occur. Suppose
further that each update of the record, a binary vector of length 3 is to be
accomplished by changing a single bit. (This problem is relevant to memory
media presently on the horizon.)
.sp
(2) Suppose a parallel algorithm or program has its target architecture a
synchronous network of four processors connected as
the complete graph
@K sub 4@ but is to be run on an architecture which has the connection topology
of the cube @Q sub 3@.
.sp
In both problems, what we require (speaking intuitively for the moment)
is an encoding of the complete graph @K sub 4@ in the cube
@Q sub 3@. Note that a solution to problem (1) is not possible by encoding
which assigns vectors 1:1 to states. A solution to problem (2) which is 1:1
incurs a relay cost'' of at least 2.
%R CS-85-142 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T A CATEGORY OF GRAPHS FOR MULTIPROCESSING
%A Michael R. Fellows
%X Two problems which arise in synchronous models of parallel processing with
local memory and incomplete processor communication topology are considered
from the standpoint of a category of encodings of graphs in graphs. The
problems are: (a) the simulation of one multiprocessor by another (b) the
scheduling of low-level parallel computations. The approach to the simulation
problem presented here generalizes the notion of graph embedding (based on
1:1 correspondence of processes and processors) by allowing many:1
correspondences. A comparison is made with analogous results for the
graph embedding model. It is shown that a trade-off is possible between
functional redundancy and expansion cost.
%R CS-86-143 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T A NOTE ON SUBDIVISIONS OF GRAPHS AND CYCLES MODULO K
%A Michael R. Fellows
%X Several authors
have considered the problem of determining
conditions on a graph @G@ which insure the existence of cycles of length
congruent to @d@ modulo @k@.
In this note we prove a bound on minimum degree
which insures that every subdivision of @G@ has a cycle of length
divisible by @k@.
%R CS-86-144 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T DATA STRUCTURES FOR RELUCTANT MEDIA
%A Michael R. Fellows
%X The problem of maintaining data structures
under restrictions on the number of
bit changes per update is studied. By analogy with the problems posed by
write-once memory media, bits are in the present problem written reluctantly.
The problem is similarly motivated by memory media on the horizon. If state
information is to be maintained, where the allowed state transitions are
described by a graph @G@,
then the problem is equivalent to a notion of
encoding the graph @G@ in a graph derived from a cube. If @q(n)@
denotes the least @q@
such that the complete graph @K sub n@ can be encoded in
@Q sub n@, then a major result can be stated @q(n) \sim n@.
The results are obtained mainly by studying Cayley graphs.
%R CS-86-145 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T STABLE DUPLICATE-KEY EXTRACTION WITH OPTIMAL TIME AND SPACE BOUNDS
%A Bing-Chao Huang
%A Michael A. Langston
%X We consider the problem of transforming a list @L@ of records
sorted on some key
into two sublists @L sub 1@ and @L sub 2@ where, for each distinct key in
@L@, @L sub 1@
contains the first record of L which possesses the key and
@L sub 2@ contains all
records of @L@
with duplicate keys. We also desire that our duplicate-key
extraction algorithm be stable (that is, records within each sublist must
obey the original order given by @L@). This operation has fundamental
applications in data base and related file processing environments whenever
a collection of distinct keys need only be considered. Moreover, stability
in extraction insures that @L@
can be efficiently restored at a later time
with a stable merge of @L sub 1@ and @L sub 2@. Any procedure for performing
duplicate-key extraction on a file of size @n@
must require at least @O(n)@ time
and @O(1)@ extra space, although the obvious algorithms for achieving either
bound alone violate the other. We design a stable algorithm, using
block-rearrangement techniques, and prove that it is optimal in the theoretical
sense that it achieves both lower bounds simultaneously. We also show that its
worst-case number of key comparisons and record exchanges sum to no more than
@6n@, suggesting that the algorithm has practical application as well.
%R CS-86-146 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T STIRLING GRAPHS AND THEIR PROPERTIES
%A Sajal K. Das
%A Narsingh Deo
%X We define a new family of adjacency matrices, called the Stirling matrices,
and study the corresponding family of simple connected graphs, called the
Stirling graphs. We explore various connectivity properties of these graphs
from the viewpoint of their potential for interconnection networks in
multiprocessing systems. Every Stirling graph of order three or more has a
Hamiltonian cycle as well as a complete binary tree in which all vertices
at each level are connected with a cycle. The diameter of the Stirling graph
of order @n@ is @lceil log su 2 (n+1) rceil -1@,
and the number of edges has an upper bound of
@0(n sup {1.59})@.
Stirling graphs compare favorably with leaf-ringed binary tree networks.
%R CS-86-147 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T COREL - A CONCEPTUAL RETRIEVAL SYSTEM
%A M. Kathryn Di Benigno
%A George R. Cross
%A Gary G. deBessonet
%X Corel is an experimental retrieval system that employs techniques of
artificial intelligence. Articles of the Civil Code of Louisiana have been
conceptually indexed using frame-based knowledge structures in hope of
improving accessibility over traditional key-word retrieval systems. A set
of macro packages has been developed to allow a domain expert to
implement a retrieval system based on this methodology.
%R CS-86-148 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T THE SECOND LABOR OF HERCULES: AN ESSAY ON SOFTWARE ENGINEERING
AND THE STRATEGIC DEFENSE INITIATIVE
%A David B. Benson
%X Building computer programs is called software engineering. Software
engineering is an engineering discipline which is in its infancy. Engineering
of all kinds builds on experience. Software engineering has little
experience. Software engineers cannot build large software which works the
first time, let alone the much more difficult task of engineering battle
software which works the first time.
.sp 1
The envisaged Strategic Defense Initiative ballistic missile defense would
require the largest battle software ever thought about. It must work the
first time.
.sp 1
The essay describes traditional engineering practice and software engineering
practice without technical terms. The meaning of trustworthy software is
defined and the state of the art in establishing trust in software is
described. The special aspects of military software are reviewed. All of
this is applied to the Strategic Defense Initiative software. A practical
means to establish confidence in battle software is described.
.sp 1
The essay is summarized in a recapitulation section. The conclusions of the
essay suggest actions which the U.S. government should take.
.sp 1
An extensive bibliography on software engineering and the Strategic Defense
Initiative is included.
%R CS-86-149 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T THE STRUCTURE OF CCLIPS
%A Mohammed Nasiruddin
%A George R. Cross
%A Cary G. deBessonet
%X The Civil Code Legal Information Processing System (CCLIPS) is a conceptual
retrieval system whose domain is the Louisiana Civil Code. Statutes are
coded in Atomically Normalized Form (ANF) and entered into a database. Legal
situations are entered by the user in ANF and relevant statutes are retrieved.
We discuss the current status of the system and some plans for further
development.
%R CS-86-150 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T PRACTICAL IN-PLACE MERGING
%A Bing-Chao Huang
%A Michael A. Langston
%X We present a novel, yet straightforward linear-time algorithm for merging
two sorted lists in a fixed amount of additional space. Constant of
proportionality estimates and empirical testing reveal that this procedure
is reasonably competitive with merge routines free to squander unbounded
additional memory, making it particularly attractive for applications such as
the external merge-sorting of very large files.
%R CS-86-151 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T COMMUNICATING COAUTOMATA
%A David B. Benson
%X Communicating coautomata live in powerdomains, which
we view as @k@-modules.
We begin by showing that incompletely specified nondeterministic state
machines (automata) are a particular form of @A@-module over a semigroup
@k@-algebra @A@, where @k@ is the commutative unital semiring
B = {0,1} with inclusive or'' as addition and and'' as
multiplication. Then we can equally well consider output machines (coautomata)
which, without input, change state and output some symbol. The coautomata
view provides a lovely way to think about communication between processes,''
a proper communication being required before each process'' can
continue. For simplicity we consider only the synchronous case.
.sp 1
The algebra all works quite nicely, providing a sound (re)-formulation of
many researcher's view of communicating processes'' in elegant mathematical
terms. At the end I pose so-called safety and liveness questions which
suitable topologies may aid in answering.
%R CS-86-152 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T FIXED POINTS IN FREE PROCESS ALGEBRAS WITH SILENT EVENTS, PART I
%A David B. Benson
%A Jerzy Tiuryn
%X Characterizing and finding fixed point solutions to equations
in free process algebras is accomplished by first considering
the structure of the free
process algebras and then applying a particular proof technique developed for
the purpose. The fixed point solutions for systems of equations for a class
of polynomials is important in applications, the linear left simple
polynomials, are characterized and explicitly given. The second part of this
paper will apply the proof methods to characterizing and giving solutions to
equations for other classes of polynomials over free process algebras.
%R CS-86-153 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T STRING ALGEBRAS AND COALGEBRAS, AUTOMATA AND COAUTOMATA
%A David B. Benson
%X The concatenation algebra of strings has a dual,
the coalgebra of decomposing
strings into prefixes and suffixes. The decomposition coalgebra has been
implicitly used in defining the run map of automata and related concepts.
This paper makes the role of decomposition explicit. Dual to automata which
read input strings are the coautomata which write output strings. The
coautomata require the decomposition coalgebra to define the run map with and
from the concatenation algebra.
.sp 1
We give a careful definition of the run maps for automata and coautomata,
proving that the run maps for nondeterministic incompletely-specified
outputless automata have (semiring) module structure while the run maps for
nondeterministic incompletely-specified inputless coautomata have (semiring)
comodule structure. The two proofs are not exact duals of one another.
%R CS-86-154 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T LESSA: AN ARRAY TO SOLVE A SET OF LINEAR EQUATIONS
%A Dilip Sarkar
%X A dedicated linear array of simple processors is proposed to solve a set of
linear equations. Data structure and algorithm also presented for the array
to solve a set of @n@ linear equations in @O(n sup 2+3.n )@ time on an
array of @n@
processors. The given algorithm is a parallelization of the Gaussian
elimination algorithm. The data input to the array is purely sequential. The
algorithm is optimal, within a constant, in its time and area requirements.
%R CS-86-155 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T BIN PACKING: ON OPTIMIZING THE NUMBER OF PIECES PACKED
%A Donald K. Friesen
%A Michael A. Langston
%X We consider bin-packing variations related to the well-studied problem of
maximizing the total number of pieces packed into a fixed set of bins. We show
that, when the objective is to minimize the total number of pieces packed
subject to the constraint that no unpacked piece will fit, no polynomial-time
relative approximation exists (unless, of course, @P=NP@). That is, we prove
that it is NP-hard to guarantee packing no more than a constant multiple of
the optimal number of pieces, for any constant. This appears to be the
first bin-packing problem for which this property has been demonstrated.
Furthermore, this result also holds for the allied packing variant which seeks
to minimize the maximum number of pieces packed in any single bin. We find
the situation to be markedly better for the problem of maximizing the minimum
number of pieces in any bin. If all bins possess the same capacity, we prove
that the familiar SPF rule is an absolute approximation algorithm with additive
constant 1, and can therefore be regarded as a best possible heuristic. For
the more general and difficult case in which bin capacities may differ, it
turns out that SPF fails to qualify as even a relative approximation
algorithm. However, we devise an implementation of the well-known FFD
heuristic, which we show to be a relative approximation
algorithm, yielding a
worst-case performance ratio of 1/2 with additive constant 0. Moreover,
we prove that (unless @P=NP@) no polynomial-time algorithm can guarantee a
higher ratio without sacrificing the additive constant.
%R CS-86-156 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T THE KNAPSACK PROBLEM WITH DISJOINT MULTIPLE CHOICE CONSTRAINTS
%A Vijay Aggarwal
%A Narsingh Deo
%A Dilip Sarkar
%X This paper considers the binary knapsack problem under disjoint
multiple-choice constraints. It proposes a two-stage algorithm based on
Lagrangean relaxation. The first stage in polynomial effort determines the
optimal Lagrange multiplier value, which is then used in a branch and bound
scheme to rank-order the choice-sets, and thus obtain an optimal
solution in a relatively low depth of search. The validity of the algorithm
is established, a numerical example is included, and advantages over other
schemes are outlined.
%R CS-86-157 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T MINIMUM LENGTH PREIMAGE OF DIGITAL ARCS
%A C. E. Kim
%X The lengths of the preimages of digital arcs are considered. In the case of
digital line segments we find the preimages of the maximum and minimum
length preimages and proposes an approximate average of the two as an estimator
of digital line segments. In the case of digital arcs in general, a linear
time algorithm is presented that computes the minimum length preimage, which
may be used as a first approximation length of digital arcs.
%R CS-86-158 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T CONGRUENT CONVEX DIGITAL REGIONS UNDER TRANSLATION
%A C. E. Kim
%A R. Krishnaswamy
%X The congruency of two convex digital regions under translation is
defined and its properties are discussed. An @O(m+n sup 3logn )@
time algorithm
is presented that determines whether or not two convex digital regions are
congruent under translation.
%R CS-86-159 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T PROBLEMS OF POSTING SENTRIES
%A R. Krishnaswamy
%A C. E. Kim
%X We consider the problem of posting a minimum
number of sentries to watch every
point on the boundary of convex polygons enclosed in a polygon. A linear time
algorithm is presented to obtain an optimal posting for a polygon in a
nonconvex polygon. It is shown that the problem for a nonconvex polygon in a
convex enclosure is NP-hard and so is the problem for a set of convex
polygons in a convex enclosure. An exhaustive algorithm to compute an optimal
posting for two convex polygons in a convex enclosure is also presented.
%R CS-86-160 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T ON FINDING OPTIMAL AND NEAR-OPTIMAL LINEAL SPANNING TREES
%A Michael R. Fellows
%A Donald K. Friesen
%A Michael A. Langston
%X The search for good lineal, or depth-first, spanning trees is an important
aspect in the implementation of a wide assortment of graph algorithms. We
consider the complexity of finding optimal lineal spanning trees under
various notions of optimality. In particular, we show that several natural
problems, such as constructing a shortest or a tallest lineal tree, are
NP-complete. We also address the issue of polynomial-time,
near-optimization strategies for these difficult problems, showing, among
other things, that efficient absolute approximation algorithms cannot exist
unless @P=NP@.
%R CS-86-161 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T THE NUMERICAL EVALUATION OF MULTIPLE INTEGRALS ON PARALLEL COMPUTERS
%A Alan Genz
%X The problem of efficient implementation of numerical integration algorithms
on parallel computers is considered. First, a general discussion of both
adaptive and nonadaptive algorithms, including possible differences in
implementation for vector machines, SIMD machines and MIMD machines is given.
The implementation of a globally adaptive algorithm on three different parallel
computers is discussed, and test results are reported.
%R CS-86-162 Computer Science Department
%I Washington State University
%C Pullman, WA 99164-1210
%T THE END OF INNOCENCE IN POLYNOMIAL-TIME COMPLEXITY
%A Michael R. Fellows
%A Michael A. Langston
%X The field of computational complexity for concrete, practical combinatorial
problems has developed in a remarkably smooth fashion. One can point to
several features of the theory of polynomial-time computability which make
it especially well-behaved, including:
.sp 1
1. the modelling of feasible computing by polynomial-time complexity
is well-supported by the fact that almost all known polynomial-time
algorithms for natural problems have running times bounded by of
low order
polynomials
.sp 1
2. problems are invariably known to be decidable in polynomial-time
by direct evidence in the form of efficient algorithms
.sp 1
3. while the theory is formulated in terms of decision problems,
almost all known algorithms proceed by actually constructing a solution to
the problem at hand.
.sp 1
Recent advances in graph theory and graph algorithms dramatically alter this
situation on all three counts. Powerful and easy-to-apply tools are now
available for classifying problems as decidable in polynomial time by
non-constructively proving only the existence of polynomial-time decision
algorithms. These tools neither specify the degree of the polynomial,
produce the decision algorithm, nor guarantee that such an algorithm is of
any use in constructing a solution. These developments present both
practitioners and theorists with novel challenges.