bluuebunny/crossref_metadata_2025 huggingface dataset:
Chores: enhanced run-time support for shared-memory parallel computing
Authors: Eager Derek L. , Jahorjan John
Published: July 2002

Parallel computing is increasingly important in the solution of large-scale numerical problems. The difficulty of efficiently hand-coding parallelism, and the limitations of parallelizing compilers, have nonetheless restricted its use by scientific programmers.

In this paper we propose a new paradigm,chores, for the run-time support of parallel computing on shared-memory multiprocessors. We consider specifically uniform memory access shared-memory environments, although the chore paradigm should also be appropriate for use within the clusters of a large-scale nonuniform memory access machine.

We argue that chore systems attain both the high efficiency of compiler approaches for the common case of data parallelism, and the flexibility and performance of user-level thread approaches for functional parallelism. These benefits are achieved within a single, simple conceptual model that almost entirely relieves the programmer and compiler from concerns of granularity, scheduling, and enforcement of synchronization constraints. Measurements of a prototype implementation demonstrate that the chore model can be supported more efficiently than can traditional approaches to either data or functional parallelism alone.
The elusive atomic register
Authors: Singh Ambuj K. , Anderson James H. , Gouda Mohamed G.
Published: July 2002

We present a construction of a single-writer, multiple-reader atomic register from single-writer, single-reader atomic registers. The complexity of our construction is asymptotically optimal;

O(M
2
+ MN)

shared single-writer, single-reader safe bits are required to construct a single-writer, M-reader, N-bit atomic register.
Formal specification and design of a message router
Authors: Creveuil Christian , Roman Gruia-Catalin
Published: July 2002

Formal derivation refers to a family of design techniques that entail the development of programs which are guaranteed to be correct by construction. Only limited industrial use of such techniques (e.g., UNITY-style specification refinement) has been reported in the literature, and there is a great need for methodological developments aimed at facilitating their application to complex problems. This article examines the formal specification and design of a message router in an attempt to identify those methodological elements that are likely to contribute to successful industrial uses of program derivation. Although the message router cannot be characterized as being industrial grade, it is a sophisticated problem that poses significant specification and design challenges—its apparent simplicity is rather deceiving. The main body of the article consists of a complete formal specification of the router and a series of successive refinements that eventually lead to an immediate construction of a correct UNITY program. Each refinement is accompanied by its design rationale and is explained in a manner accessible to a broad audience. We use this example to make the case that program derivation provides a good basis for introducing rigor in the design strategy, regardless of the degrees of formality one is willing to consider.
Design and evaluation of algorithms for image retrieval by spatial similarity
Authors: Gudivada Venkat N. , Raghavan Vijay V.
Published: July 2002

Similarity-based retrieval of images is an important task in many image database applications. A major class of users' requests requires retrieving those images in the database that are spatially similar to the query image. We propose an algorithm for computing the spatial similarity between two symbolic images. A symbolic image is a logical representation of the original image where the image objects are uniquely labeled with symbolic names. Spatial relationships in a symbolic image are represented as edges in a weighted graph referred to as spatial-orientation graph. Spatial similarity is then quantified in terms of the number of, as well as the extent to which, the edges of the spatial-orientation graph of the database image conform to the corresponding edges of the spatial-orientation graph of the query image.

The proposed algorithm is robust in the sense that it can deal with translation, scale, and rotational variances in images. The algorithm has quadratic time complexity in terms of the total number of objects in both the database and query images. We also introduce the idea of quantifying a system's retrieval quality by having an expert specify the expected rank ordering with respect to each query for a set of test queries. This enables us to assess the quality of algorithms comprehensively for retrieval in image databases. The characteristics of the proposed algorithm are compared with those of the previously available algorithms using a testbed of images. The comparison demonstrated that our algorithm is not only more efficient but also provides a rank ordering of images that consistently matches with the expert's expected rank ordering.
Attribute grammar paradigms—a high-level methodology in language implementation
Authors: Paakki Jukka
Published: July 2002

Attribute grammars are a formalism for specifying programming languages. They have been applied to a great number of systems automatically producing language implementations from their specifications. The systems and their specification languages can be evaluated and classified according to their level of application support, linguistic characteristics, and degree of automation.

A survey of attribute grammar-based specification languages is given. The modern advanced specification languages extend the core attribute grammar model with concepts and primitives from established programming paradigms. The main ideas behind the developed attribute grammar paradigms are discussed, and representative specification languages are presented with a common example grammar. The presentation is founded on mapping elements of attribute grammars to their counterparts in programming languages. This methodology of integrating two problem-solving disciplines together is explored with a classification of the paradigms into structured, modular, object-oriented, logic, and functional attribute grammars. The taxonomy is complemented by introducing approaches based on an implicit parallel or incremental attribute evaluation paradigm.
A visual retrieval environment for hypermedia information systems
Authors: Lucarella Dario , Zanzi Antonella
Published: July 2002

We present a graph-based object model that may be used as a uniform framework for direct manipulation of multimedia information. After an introduction motivating the need for abstraction and structuring mechanisms in hypermedia systems, we introduce the data model and the notion of perspective, a form of data abstraction that acts as a user interface to the system, providing control over the visibility of the objects and their properties. A perspective is defined to include an intension and an extension. The intension is defined in terms of a pattern, a subgraph of the schema graph, and the extension is the set of pattern-matching instances. Perspectives, as well as database schema and instances, are graph structures that can be manipulated in various ways. The resulting uniform approach is well suited to a visual interface. A visual interface for complex information systems provides high semantic power, thus exploiting the semantic expressibility of the underlying data model, while maintaining ease of interaction with the system. In this way, we reach the goal of decreasing cognitive load on the user, with the additional advantage of always maintaining the same interaction style. We present a visual retrieval environment that effectively combines filtering, browsing, and navigation to provide an integrated view of the retrieval problem. Design and implementation issues are outlined for MORE (Multimedia Object Retrieval Environment), a prototype system relying on the proposed model. The focus is on the main user interface functionalities, and actual interaction sessions are presented including schema creation, information loading, and information retrieval.
A visual interface for a database with version management
Authors: Davison Jay W. , Zdonik Stanley B.
Published: July 2002

This paper describes a graphical interface to an experimental database system which incorporates a built-in version control mechanism that maintains a history of the database development and changes. The system is an extension of ISIS [6], Interface for a Semantic Information System, a workstation-based, graphical database programming tool developed at Brown University. ISIS supports a graphical interface to a modified subset of the Semantic Data Model (SDM) [7]. The ISIS extension introduces a transaction mechanism that interacts with the version control facilities.

A series of version control support tools have been added to ISIS to provide a notion of history to user-created databases. The user can form new versions of three types of ISIS objects: a class definition object (a type), the set of instances of a class (the content), and an entity. A version-viewing mechanism is provided to allow for the comparison of various object versions. Database operations are grouped together in atomic units to form transactions, which are stored as entities in the database. A sample session demonstrates the capabilities of version and transaction control during the creation and manipulation of database objects.
Knowledge compilation and theory approximation
Authors: Selman Bart , Kautz Henry
Published: July 2002

Computational efficiency is a central concern in the design of knowledge representation systems. In order to obtain efficient systems, it has been suggested that one should limit the form of the statements in the knowledge base or use an incomplete inference mechanism. The former approach is often too restrictive for practical applications, whereas the latter leads to uncertainty about exactly what can and cannot be inferred from the knowledge base. We present a third alternative, in which knowledge given in a general representation language is translated (compiled) into a tractable form—allowing for efficient subsequent query answering.

We show how propositional logical theories can be compiled into Horn theories that approximate the original information. The approximations bound the original theory from below and above in terms of logical strength. The procedures are extended to other tractable languages (for example, binary clauses) and to the first-order case. Finally, we demonstrate the generality of our approach by compiling concept descriptions in a general frame-based language into a tractable form.
Declustering of key-based partitioned signature files
Authors: Ciaccia Paolo , Tiberio Paolo , Zezula Pavel
Published: July 2002

Access methods based on signature files can largely benefit from possibilities offered by parallel environments. To this end, an effective
declustering
strategy that would distribute signatures over a set of parallel independent disks has to be combined with a synergic
clustering
which is employed to avoid searching the whole signature file while executing a query. This article proposes two parallel signature file organizations, Hamming Filter (
HF
) and Hamming
+
Filter (

H
+
F

), whose common declustering strategy is based on
error correcting codes
, and where clustering is achieved by organizing signatures into fixed-size buckets, each containing signatures sharing the same
key
value.
HF
allocates signatures on disks in a static way and works well if a correct relationship holds between the parameters of the code and the size of the file.

H
+
F

is a generalization of
HF
suitable to manage highly dynamic files. It uses a dynamic declustering, obtained through a
sequence
of codes, and organizes a smooth migration of signatures between disks so that high performance levels are retained regardless of current file size. Theoretical analysis characterizes the best-case, expected, and worst-case behaviors of these organizations. Analytical results are verified by experiments on prototype systems.
Self-indexing inverted files for fast text retrieval
Authors: Moffat Alistair , Zobel Justin
Published: July 2002

Query-processing costs on large text databases are dominated by the need to retrieve and scan the inverted list of each query term. Retrieval time for inverted lists can be greatly reduced by the use of compression, but this adds to the CPU time required. Here we show that the CPU component of query response time for conjunctive Boolean queries and for informal ranked queries can be similarly reduced, at little cost in terms of storage, by the inclusion of an internal index in each compressed inverted list. This method has been applied in a retrieval system for a collection of nearly two million short documents. Our experimental results show that the self-indexing strategy adds less than 20% to the size of the compressed inverted file, which itself occupies less than 10% of the indexed text, yet can reduce processing time for Boolean queries of 5-10 terms to under one fifth of the previous cost. Similarly, ranked queries of 40-50 terms can be evaluated in as little as 25% of the previous time, with little or no loss of retrieval effectiveness.
Hard-core theorems for complexity classes
Authors: Even Shimon , Selmen Alan L. , Yacobi Yacov
Published: July 2002

Nancy Lynch proved that if a decision problem
A
is not solvable in polynomial time, then there exists an infinite recursive subset
X
of its domain on which the decision is almost everywhere complex. In this paper, general theorems of this kind that can be applied to several well-known automata-based complexity classes, including a common class of randomized algorithms, are proved.
The cosmic cube
Authors: Seitz Charles L.
Published: July 2002

Sixty-four small computers are connected by a network of point-to-point communication channels in the plan of a binary 6-cube. This “Cosmic Cube” computer is a hardware simulation of a future VLSI implementation that will consist of single-chip nodes. The machine offers high degrees of concurrency in applications and suggests that future machines with thousands of nodes are both feasible and attractive.
ProbView
Authors: Lakshmanan Laks V. S. , Leone Nicola , Ross Robert , Subrahmanian V. S.
Published: July 2002

Probability theory is mathematically the best understood paradigm for modeling and manipulating uncertain information. Probabilities of complex events can be computed from those of basic events on which they depend, using any of a number of strategies. Which strategy is appropriate depends very much on the known interdependencies among the events involved. Previous work on probabilistic databases has assumed a
fixed
and
restrictive
combination strategy (e.g., assuming all events are pairwise independent). In this article, we characterize, using postulates, whole classes of strategies for conjunction, disjunction, and negation, meaningful from the viewpoint of probability theory. (1) We propose a probabilistic relational data model and a
generic
probabilistic relational algebra that neatly captures
various strategies
satisfying the postulates, within a
single unified framework.
(2) We show that as long as the chosen strategies can be computed in polynomial time, queries in the positive fragment of the probabilistic relational algebra have essentially the same data complexity as classical relational algebra. (3) We establish various containments and equivalences between algebraic expressions, similar in spirit to those in classical algebra. (4) We develop algorithms for maintaining materialized probabilistic views. (5) Based on these ideas, we have developed a prototype probabilistic database system called ProbView on top of Dbase V.0. We validate our complexity results with experiments and show that rewriting certain types of queries to other equivalent forms often yields substantial savings.
A new general derandomization method
Authors: Andreev Alexander E. , Clementi Andrea E. F. , Rolim José D. P.
Published: July 2002

We show that
quick hitting set generators
can replace
quick pseudorandom generators
to derandomize any probabilistic
two-sided error
algorithms. Up to now
quick hitting set generators
have been known as the general and uniform derandomization method for probabilistic
one-sided error
algorithms, while
quick pseudorandom generators
as the generators as the general and uniform method to derandomize probabilistic
two-sided error
algorithms.

Our method is based on a deterministic algorithm that, given a Boolean circuit
C
and given access to a hitting set generator, constructs a
discrepancy set
for
C
. The main novelty is that the discrepancy set depends on
C
, so the new derandomization method is not uniform (i.e., not
oblivious
).

The algorithm works in time exponential in
k(p(n))
where
k
(*) is the
price
of the hitting set generator and
p
(*) is a polynomial function in the size of
C
. We thus prove that if a logarithmic price quick hitting set generator exists then BPP = P.
Hypertext versus Boolean access to biomedical information
Authors: Wildemuth Barbara M. , Friedman Charles P. , Downs Stephen M.
Published: July 2002

This study compared of two modes of access to a biomedical database, in terms of their effectiveness and efficiency in supporting clinical problem solving and in terms of user preferences. Boolean access, which allowed subjects to frame their queries as combinations of keywords, was compared to hypertext access, which allowed subjects to navigate from one database node to another. The accessible biomedical data were identical across system versions. Performance data were collected from two cohorts of first-year medical students, each student randomly assigned to either the Boolean or the hypertext system. Additional attitudinal data were collected from the second cohort. At each of two research sessions (one just before and one just after their bacteriology course), subjects worked eight clinical case problems, first using only their personal knowledge and, subsequently, with aid from the database. Database retrievals enabled students to answer questions they could not answer based on personal knowledge alone. This effect was greater when personal knowledge of bacteriology was lower. There were not statistically significant differences between the two forms of access, in terms of problem-solving effectiveness or efficiency. Students preferred Boolean access over hypertext access.
Functional partitioning improvements over structural partitioning for packaging constraints and synthesis
Authors: Vahid Frank , Le Thuy Dm , Hsu Yu-Chin
Published: July 2002

Incorporating functional partitioning into a synthesis methodology leads to several important advantages. In functional partitioning, we first partition a functional specification into smaller subspecifications and then synthesize structure for each, in contrast to the current approach of first synthesizing structure for the entire specification and then partitioning that structure. One advantage is the improvement in I/O performance and package count, when partitioning among hardware blocks with size and I/O constraints, such as FPGAs or blocks within an ASIC. A second advantage is reduction in synthesis runtimes. We describe these important advantages, concluding that further research on functional partitioning can lead to inproved results from synthesis environments.
MULTISAFE—a modular multiprocessing approach to secure database management
Authors: Trueblood Robert P. , Hartson H. Rex , Martin Johannes J.
Published: July 2002

This paper describes the configuration and intermodule communication of a MULTImodule system for supporting Secure Authorization with Full Enforcement (MULTISAFE) for database management. A modular architecture is described which provides secure, controlled access to shared data in a multiuser environment, with low performance penalties, even for complex protection policies. The primary mechanisms are structured and verifiable. The entire approach is immediately extendible to distributed protection of distributed data. The system includes a user and applications module (UAM), a data storage and retrieval module (SRM), and a protection and security module (PSM). The control of intermodule communication is based on a data abstraction approach, initially described in terms of function invocations. An implementation within a formal message system is then described. The discussion of function invocations begins with the single terminal case and extends to the multiterminal case. Some physical implementation aspects are also discussed, and some examples of message sequences are given.
GlOSS
Authors: Gravano Luis , García-Molina Héctor , Tomasic Anthony
Published: July 2002

The dramatic growth of the Internet has created a new problem for users: location of the relevant sources of documents. This article presents a framework for (and experimentally analyzes a solution to) this problem, which we call the
text-source discovery problem
. Our approach consists of two phases. First, each text source exports its contents to a centralized service. Second, users present queries to the service, which returns an ordered list of promising text sources. This article describes
GlOSS
, Glossary of Servers Server, with two versions:
bGlOSS
, which provides a Boolean query retrieval model, and
vGlOSS
, which provides a vector-space retrieval model. We also present
hGlOSS
, which provides a decentralized version of the system. We extensively describe the methodology for measuring the retrieval effectiveness of these systems and provide experimental evidence, based on actual data, that all three systems are highly effective in determining promising text sources for a given query.
Differential files
Authors: Severance Dennis G. , Lohman Guy M.
Published: July 2002

The representation of a collection of data in terms of its differences from some preestablished point of reference is a basic storage compaction technique which finds wide applicability. This paper describes a differential database representation which is shown to be an efficient method for storing large and volatile databases. The technique confines database modifications to a relatively small area of physical storage and as a result offers two significant operational advantages. First, because the “reference point” for the database is inherently static, it can be simply and efficiently stored. Second, since all modifications to the database are physically localized, the process of backup and the process of recovery are relatively fast and inexpensive.
Some high level language constructs for data of type relation
Authors: Schmidt Joachim W.
Published: July 2002

For the extension of high level languages by data types of mode relation, three language constructs are proposed and discussed: a repetition statement controlled by relations, predicates as a generalization of Boolean expressions, and a constructor for relations using predicates. The language constructs are developed step by step starting with a set of elementary operations on relations. They are designed to fit into PASCAL without introducing too many additional concepts.
A Permutation Network
Authors: Waksman Abraham
Published: July 2002

In this paper the construction of a switching network capable of
n
!-permutation of its
n
input terminals to its
n
output terminals is described. The building blocks for this network are binary cells capable of permuting their two input terminals to their two output terminals.

The number of cells used by the network is 〈
n
· log
2
n
-
n
+ 1〉 = Σ

n

k
=1

〈log
2
k
〉. It could be argued that for such a network this number of cells is a lower bound, by noting that binary decision trees in the network can resolve individual terminal assignments only and not the partitioning of the permutation set itself which requires only 〈log
2
n
!〉 = 〈Σ

n

k
=1

log
2
k
〉 binary decisions.

An algorithm is also given for the setting of the binary cells in the network according to any specified permutation.
PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric
Authors: Morrison Donald R.
Published: July 2002

PATRICIA is an algorithm which provides a flexible means of storing, indexing, and retrieving information in a large file, which is economical of index space and of reindexing time. It does not require rearrangement of text or index as new material is added. It requires a minimum restriction of format of text and of keys; it is extremely flexible in the variety of keys it will respond to. It retrieves information in response to keys furnished by the user with a quantity of computation which has a bound which depends linearly on the length of keys and the number of their proper occurrences and is otherwise independent of the size of the library. It has been implemented in several variations as FORTRAN programs for the CDC-3600, utilizing disk file storage of text. It has been applied to several large information-retrieval problems and will be applied to others.
Optimization of Memory Hierarchies in Multiprogrammed Systems
Authors: Ramamoorthy C. V. , Chandy K. M.
Published: July 2002

The optimization of memory hierarchy involves the selection of types and sizes of memory devices such that the average access time to an information block is a minimum for a particular cost constraint. It is assumed that the frequency of usage of the information is known a priori. In this paper the optimization theory for a single task or program is reviewed and it is extended to a general case in multiprogramming when a number of tasks are executed concurrently. Another important extension treats the case when memories are available only in indivisible modules. Comparisons with conventional methods of solution as well as computational experience on the multiprogrammed and modular cases are given.
The independence of miss ratio on page size
Authors: Fagin Ronald , Easton Malcolm C.
Published: July 2002

A theoretical justification is given to the empirical observation that in some computing systems with a paged, 2-level storage hierarchy, long-term miss ratio is roughly independent of page size. Let
MISS
be the expected working-set miss ratio in the independent reference model, with expected working set size
CAP
pages. Now form blocks, by combining the
B
pages with the highest probabilities of reference into one block, the
B
pages with the next-highest probabilities of reference into a second block, and so on. Let
MISS
*
be the expected working-set miss ratio when all data are moved in blocks and when the expected working set size is again
CAP
pages, that is,
CAP
/
B
=
C
blocks. It is proved that |
MISS
—
MISS
*
| < (2/
C
) + (33/
C
2
). Thus, if the expected working-set size (in blocks) is sufficiently large, then the miss ratios in the blocked and unblocked cases are approximately equal. This result is used to argue the approximate independence of miss ratio on page size in more realistic models of page references.
The Grid File
Authors: Nievergelt J. , Hinterberger Hans , Sevcik Kenneth C.
Published: July 2002

Traditional file structures that provide multikey access to records, for example, inverted files, are extensions of file structures originally designed for single-key access. They manifest various deficiencies in particular for multikey access to highly dynamic files. We study the dynamic aspects of file structures that treat all keys symmetrically, that is, file structures which avoid the distinction between primary and secondary keys. We start from a bitmap approach and treat the problem of file design as one of data compression of a large sparse matrix. This leads to the notions of a
grid partition
of the search space and of a
grid directory
, which are the keys to a dynamic file structure called the
grid file
. This file system adapts gracefully to its contents under insertions and deletions, and thus achieves an upper bound of two disk accesses for single record retrieval; it also handles range queries and partially specified queries efficiently. We discuss in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.
Minimizing stall time in single and parallel disk systems
Authors: Albers Susanne , Garg Naveen , Leonardi Stefano
Published: July 2002

We study integrated prefetching and caching problems following the work of Cao et al. [1995] and Kimbrel and Karlin [1996]. Cao et al. and Kimbrel and Karlin gave approximation algorithms for minimizing the total elapsed time in single and parallel disk settings. The total elapsed time is the sum of the processor stall times and the length of the request sequence to be served.

We show that an optimum prefetching/caching schedule for a single disk problem can be computed in polynomial time, thereby settling an open question by Kimbrel and Karlin. For the parallel disk problem, we give an approximation algorithm for minimizing stall time. The solution uses a few extra memory blocks in cache. Stall time is an important and harder to approximate measure for this problem. All of our algorithms are based on a new approach which involves formulating the prefetching/caching problems as linear programs.
Further survey of punched card codes
Authors: Ross H. McG.
Published: July 2002

The valuable “Survey of Punched Card Codes” prepared by Smith and Williams (
Comm. ACM 3
, Dec. 1960, 638) unfortunately omits the card codes of European equipment, other than IBM. These are presented in the table on page 181. This information has been extracted from a Ferranti publication, “Collected Information on Punched Card Codes” (List CS 266) and has been set out in much the same way as the table by Smith and Williams.
Fast finite-difference solution of biharmonic problems
Authors: Greenspan D. , Schultz D.
Published: July 2002

Setting the Reynolds number equal to zero, in a method for solving the Navier-Stokes equations numerically, results in a fast numerical method for biharmonic problems. The equation is treated as a system of two second order equations and a simple smoothing process is essential for convergence. An application is made to a crack-type problem.
Minimax nonlinear approximation by approximation on subsets
Authors: Dunham C. B.
Published: July 2002

A possible algorithm for minimax approximation on an infinite set
X
consists in choosing a sequence of finite point sets {

X
k

} which fill out
X
and taking a limit of minimax approximations on

X
k

as
k
→ ∞. Such a procedure is considered by Rice [4, pp. 12-15]. In the case of linear approximation such a procedure has been shown to converge [1, pp. 84-88]. It has been claimed by Watson [5] that the procedure works for approxition by nonlinear families.
The conversion of limited-entry decision tables to optimal and near-optimal flowcharts
Authors: Verhelst M.
Published: July 2002

Two new algorithms for deriving optimal and near-optimal flowcharts from limited entry decision tables are presented. Both take into account rule frequencies and the time needed to test conditions. One of the algorithms, called the optimum-finding algorithm, leads to a flowchart which truly minimizes execution time for a decision table in which simple rules are already contracted to complex rules. The other one, called the optimum-approaching algorithm, requires many fewer calculations but does not necessarily produce the optimum flowchart. The algorithms are first derived for treating decision tables not containing an ELSE-rule, but the optimum-approaching algorithm is shown to be equally valid for tables including such a rule.

Both algorithms are compared with existing ones and are applied to a somewhat large decision table derived from a real case. From this comparison two conclusions are drawn. (1) The optimum-approaching algorithm will usually lead to better results than comparable existing ones and will not require more, but usually less, computation time. (2) In general, the greater computation effort needed for applying the optimum-finding algorithm will not be justified by the small reduction in execution time obtained.
Comments on Moorer's music and computer composition
Authors: Smoliar Stephen W.
Published: July 2002

J.A. Moorer's “Music and Computer Composition” [1] was a distressing communication. While I realize that musical expertise is probably beyond the realm of the editorial staff, I must object to both the naiveté and faulty reasoning on the musical side of this article. In a nutshell, Moorer presents us with many paragraphs of philosophical meanderings to back up a few results which are, by his own admission, inadequate. From this he concludes, “It is also hoped that this experiment may help dispel doubts that musical composition is ‘sacred’ and unreachable by mechanical methods.” From any serious musical point of view, such a conclusion is almost vacuous.
An algorithm for the approximate solution of Wiener-Hopf integral equations
Authors: Stenger Frank
Published: July 2002

An explicit approximate solution ƒ

(
h
)

α

is given for the equation ƒ(
t
) = ∫
∞
0
k
(
t
-
τ
)ƒ(
τ
)
dτ
+
g
(
t
),
t
> 0, (*) where
k, g
∈
L
1
(- ∞, ∞) ∩
L
2
(-∞, ∞), and where it is assumed that the classical Wiener-Hopf technique may be applied to (*) to yield a solution ƒ ∈
L
1
(0, ∞) ∩
L
2
(0, ∞) for every such given
g
. It is furthermore assumed that the Fourier transforms
K
and
G
+
of
k
and
g
respectively are known explicitly, where
K
(
x
) = ∫
∞
-∞
exp (
ixt
)
k
(
t
)
dt
,
G
+
(
x
) = ∫
∞
0
exp (
ixt
)
g
(
t
)
dt
. The approximate solution ƒ

(
h
)

α

of (*) depends on two positive parameters,
h
and
α
.

If
K
(
z
) and
G
+
(
z
) are analytic functions of
z
=
x
+
iy
in the region {
x
+
iy
: |
y
| ≤
d
}, and if
K
is real on (-∞, ∞), then | ƒ(
t
) - ƒ

(
h
)

α

(
t
) | ≤
c
1
exp (-
πd
/
h
) +
c
2
exp (-
πd
/
α
) where
c
1
and
c
2
are constants. As an example, we compute ƒ

(
h
)

α

(
t
),
t
= 0.2(0.2)1,
h
=
π
/10,
α
=
π
/50, for the case of
k
(
t
) = exp(-|
t
|)/(2
π
),
g
(
t
) =
t
4
exp (-3
t
). The resulting solution is correct to five decimals.
An algorithm for optimized Boolean evaluation in information management systems
Authors: Finn Gerard D.
Published: July 2002

In cases where simple data validation techniques are inadequate and optimization policies relatively complex (e.g., in health and medical systems), a Boolean optimization algorithm can be used to report errors accurately and unambiguously. The algorithm is presented in the context of a data-validating software module that uses an
LR(1)-
parser. The algorithm's precision makes it of potential use for the retrieval of records that nearly satisfy a query.
Improved interpretation of UNIX-like file names embedded in data
Authors: Jones Douglas W.
Published: July 2002

When the data processed by a program span several files, the common practice of including file names as data in some of the files leads to difficulties in moving or sharing that data. In systems using tree structured directories, this problem can be solved by making a syntactic distinction between absolute and relative file names.
Remark on algorithm 746
Authors: Liepelt Michael , Schittkowski Klaus
Published: July 2002

The software system PCOMP uses automatic differentiation to calculate derivatives of functions that are defined by the user in a modeling language similar to Fortran. This symbolical representation is converted into an intermediate code, which can be interpreted to calculate function and derivative values at run-time within machine accuracy. Furthermore, it is possible to generate Fortran code for function and gradient evaluation, which has to be compiled and linked separately. The first version of PCOMP was introduced in Dobmann et al. [1995]. In this article, we describe a series of extensions and additional features that have been implemented in the meantime.
Letters to the editor: A protection model and its implementation in a dataflow system
Authors: Bic Lubomir
Published: July 2002

A protection model is presented for a general purpose computing system based on tags attached as
seals
and
signatures
to values exchanged among processes. A tag attached to a value as a seal does not prevent that value from being propagated to any place within the system; rather, it guarantees that the value and any information derived from it cannot leave the system unless a matching tag is presented. A tag attached to a value as a signature is used by a process to verify the origin of the received data. Solutions to problems from the areas of interprocess communication and proprietary services are given.
Unionization of professionals in data processing
Authors: Sterling Theodor D.
Published: July 2002

The needs of management, unions, employees, and computer professionals combined with existing practices of Labor Relations Boards and the various divisions in the Departments of Labor have combined to create a unique array of social conflicts. At the root are management's interest in keeping many skills in data processing and computing out of bargaining units and the union's interest in including as many of these skills as possible. There is also conflict between past strategies guiding labor relations and the structure and function of professional work in modern organizations. Two recent developments are analyzed: (1) The FAA's success in keeping airports operational with the help of computer-controlled air flow procedures; (2) Management's successful bids to exclude professional engineers working in data processing jobs from bargaining units. At the same time, the National Labor and Mediation Boards have rejected attempts to define data processing jobs including highly skilled systems analysts as a separate craft or class for representation purposes while granting such status to engineers in similar employment situations. If this principle of exclusion from unions of licensed and certified professionals who are doing DP work is established in North America, it may lead to increased labor unrest in many highly automated and data processing industries.
Psychology of calculator languages
Authors: Mayer Richard E. , Bayman Piraye
Published: July 2002

This paper presents a framework for describing users' knowledge of how a simple four-function calculator operates. Differences among novices and experts in their conceptions of “what goes on inside the calculator” for various sequences of button presses are summarized. Individual differences include different views on when an expression is evaluated, different procedures for evaluating a chain of arithmetic, and different rules for evaluating unusual sequences of key presses.
On the emulation of flowcharts by decision tables
Authors: Lew Art
Published: July 2002

Any flowchart can be emulated by a decision table, whose complexity depends on that of the flowchart. It may be necessary, however, to introduce a new control variable with associated tests and sets or to permit changes in execution sequences provided action-test independence holds. Two measures of decision table complexity are discussed and interrelated. Finally, conditions and procedures for reducing complexity are presented.
Software
Authors: Gold Charles L. , Goodman Seymour E. , Walker Benjamin G.
Published: July 2002

The control of computer technology exports, for both hardware and software, is being actively debated in government and industry circles. At the request of the U.S. Department of Defense, the Computer Network Critical Technology Expert Group (CNCTEG) was established with the support of the Electronics Industries Association and the Computer Business Equipment Manufacturers Association. The task of the CNCTEG was to assess critical technologies associated with computer networks, and to make recommendations regarding the control of the export of such technologies. The formulation of a reasonable export control policy for software has remained a particularly difficult matter that has frustrated both the U.S. government and industry. This article presents the CNCTEG's initial recommendations for the export control of software.

This material is presented in the belief that open, active discussion among members of the information processing community will be helpful in advancing the development of a sound national policy regarding the export of software products and know-how.
Algorithm = logic + control
Authors: Kowalski Robert
Published: July 2002

The notion that computation = controlled deduction was first proposed by Pay Hayes [19] and more recently by Bibel [2] and Vaughn-Pratt [31]. A similar thesis that database systems should be regarded as consisting of a relational component, which defines the logic of the data, and a control component, which stores and retrieves it, has been successfully argued by Codd [10]. Hewitt's argument [20] for the programming language PLANNER, though generally regarded as an argument against logic, can also be regarded as an argument for the thesis that algorithms be regarded as consisting of both logic and control components. In this paper we shall explore some of the useful consequences of that thesis.
Transient-free working-set statistics
Authors: Easton M. C. , Bennett B. T.
Published: July 2002

Transient-free average working-set size and transient-free missing-page rate for a finite sample of a reference string are defined. Use of these statistics is appropriate if the contents of the working set at the start of the recorded string are unknown. If a certain stationarity condition holds, these statistics provide unbiased estimates of expected working-set sizes, missing-page probabilities, and interreference distance probabilities. Two other pairs of estimators are shown to be biased. Expressions for the transient-free statistics are obtained in terms of interval statistics. Several methods of computation are discussed, the usefulness of each depending on length of the sample, number of distinct references, and the amount of main storage available to the computer performing the calculations. In particular, methods are described for handling long strings containing many distinct page names.
An algorithm using symbolic techniques for the Bel-Petrov classification of gravitational fields
Authors: Harris R. A. , Zund J. D.
Published: July 2002

In this note, an algorithm is presented for the symbolic calculation of certain algebraic invariants of the Weyl tensor which permits the determination of the Bel-Petrov types of a gravitational field. This algorithm, although more specialized than that of D'Inverno and Russell-Clark, requires neither the use of a special coordinate system nor the spin coefficient formalism. The algorithm has been implemented in FORMAC and is designed to complete the classification scheme proposed by Petrov in his book. An appendix contains examples illustrating the use of the algorithm.
Simulations of dynamic sequential search algorithms
Authors: Tenenbaum Aaron
Published: July 2002

In [3], R.L. Rivest presents a set of methods for dynamically reordering a sequential list containing
N
records in order to increase search efficiency. The method

A
i

(for
i
between 1 and
N
) performs the following operation each time that a record
R
has been successfully retrieved: Move
R
forward
i
positions in the list, or to the front of the list if it was in a position less than
i
. The method
A
1
is called the transposition method, and the method
A

N
-1

is called the move-to-front method.
Toward a discipline of real-time programming
Authors: Wirth Niklaus
Published: July 2002

Programming is divided into three major categories with increasing complexity of reasoning in program validation: sequential programming, multiprogramming, and real-time programming. By adhering to a strict programming discipline and by using a suitable high-level language molded after this discipline, the complexity of reasoning about concurrency and execution time constraints may be drastically reduced. This may be the only practical way to make real-time systems analytically verifiable and ultimately reliable. A possible discipline is outlined and expressed in terms of the language Modula.
Considerations for future programming language standards activities
Authors: Lee John A. N.
Published: July 2002

This paper reviews the current state of programming language standards activities with respect to the anomalies which exist between the various published and proposed standards for Fortran, Cobol, PL/I, and Basic. Proposals are made for the inclusion of formalisms within future standards and the extension of the standards to include additional items such as error conditions and documentation.
A buddy system variation for disk storage allocation
Authors: Burton Warren
Published: July 2002

A generalization of the buddy system for storage allocation is described. The set of permitted block sizes {

SIZE
i

}

n

i
=0

must satisfy the condition

SIZE
i

=
SIZE

i
-1

+
SIZE

i
-
k
(
i
)

where
k
may be any meaningful integral-valued function. This makes it possible to force logical storage blocks to coincide with physical storage blocks, such as tracks and cylinders.
New upper bounds for selection
Authors: Yap Chee K.
Published: July 2002

The worst-case, minimum number of comparisons complexity V
i
(n) of the i-th selection problem is considered. A new upper bound for V
i
(n) improves the bound given by the standard Hadian-Sobel algorithm by a generalization of the Kirkpatrick-Hadian-Sobel algorithm, and extends Kirkpatrick's method to a much wider range of application. This generalization compares favorably with a recent algorithm by Hyafil.
Connections between accuracy and stability properties of linear multistep formulas
Authors: Liniger Werner
Published: July 2002

This paper is concerned with stability and accuracy of families of linear
k
-step formulas depending on parameters, with particular emphasis on the numerical solution of stiff ordinary differential equations. An upper bound,
p
=
k
, is derived for the order of accuracy of
A
∞
-stable formulas. Three criteria are given for
A
0
-stability. It is shown that (1) for
p
=
k, k
arbitrary,
A
∞
-stability implies certain necessary conditions for
A
0
-stability and for strict stability (meaning that the extraneous roots of
ρ
(
ζ
) satisfy |
ζ
| < 1); (2) for
p
=
k
= 2, 3, 4, and 5,
A
∞
-stability (for
k
= 5 together with another constraint) implies strict stability; and (3) for certain one-parameter classes of formulas with
p
=
k
= 3, 4, and/or 5,
A
∞
-stability implies
A
0
-stability.
Matrix reduction—an efficient method
Authors: Johnston H. C. , Hoare C. A. R.
Published: July 2002

The paper describes an efficient method for reduction of the binary matrices which arise in some school time-tabling problems. It is a development of that described by John Lions. It has been generalized and adapted to fit into the complete timetabling process; to use a more compact data representation and more efficient processing techniques; to take fuller advantage of possible available previous knowledge about the matrix. And it is designed as a structured program, which can readily be coded by the reader in the high level or low level programming language of his choice. Practical tests of the method have shown it to be a good basis for a realistic timetabling algorithm.
Algorithm 491: Basic cycle generation [H]
Authors: Gibbs Norman E.
Published: July 2002

The PL/I procedure
BASIC_GENERATOR
is an implementation of Paton's algorithm [1] for finding a set of basic (fundamental) cycles of a finite undirected graph from its vertex adjacency matrix.