bluuebunny/crossref_metadata_2025 huggingface dataset:
Toward parallel mathematical software for elliptic partial differential equations
Authors: Ribbens Calvin J. , Watson Layne T. , Desa Colin
Published: July 2002

Three approaches to parallelizing important components of the mathematical software package ELLPACK are considered: an explicit approach using compiler directives available only on the target machine, an automatic approach using an optimizing and parallelizing precompiler, and a two-level approach based on extensive use of a set of low level computational kernels. The focus is on shared memory architectures. Each approach to parallelization is described in detail, along with a discussion of the effort involved. Performance on a test problem, using up to sixteen processors of a Sequent Symmetry S81, is reported and discussed. Implications for the parallelization of a broad class of mathematical software are drawn.
A taxonomy for secure object-oriented databases
Authors: Olivier Martin S. , von Solms Sebastiaan H.
Published: July 2002

This paper proposes a taxonomy for secure object-oriented databases in order to clarify the issues in modeling and implementing such databases. It also indicates some implications of the various choices one may make when designing such a database.

Most secure database models have been designed for relational databases. The object-oriented database model is more complex than the relational model. For these reasons, models for secure object-oriented databases are more complex than their relational counterparts. Furthermore, since views of the object-oriented model differ, each security model has to make some assumptions about the object-oriented model used for its particular database.

A number of models for secure object-oriented databases have been proposed. These models differ in many respects, because they focus on different aspects of the security problem, or because they make different assumptions about what constitutes a secure database or because they make different assumptions about the object-oriented model.

The taxonomy proposed in this paper may be used to compare the various models: Models that focus on specific issues may be positioned in the broader context with the aid of the taxonomy. The taxonomy also identifies the major aspects where security models may differ and indicates some alternatives available to the system designer for each such design choice. We show some implications of using specific alternatives.

Since differences between models for secure object-oriented databases are often subtle, a formal notation is necessary for a proper comparison. Such a formal notation also facilitates the formal derivation of restrictions that apply under specific conditions. The formal approach also gives a clear indication about the assumptions made by us—given as axioms—and the consequences of those assumptions (and of design choices made by the model designer)—given as theorems.
Digital libraries, value, and productivity
Authors: Wiederhold Gio
Published: July 2002

A digital library is popularly viewed an electronic version of a public library. But replacing paper by electronic storage leads to three major differences: storage in digital form, direct communication to obtain material, and copying from a master version. These differences in turn lead to a plethora of further differences, so that eventually the digital library no longer mimics the traditional library. Furthermore, a library is only element in the process of creating, storing, culling, accessing, selecting, and distributing information to customers. While the technical focus of digital library research is on the central functions of storage and access, major changes will occur in the interaction within the new systems.
Signature matching
Authors: Zaremski Amy Moormann , Wing Jeannette M.
Published: July 2002

Signature matching
is a method for organizing, navigating through, and retrieving from software libraries. We consider two kinds of software library components—functions and modules—and hence two kinds of matching—function matching and module matching. The signature of a function is simply its type; the signature of a module is a multiset of user-defined types and a multiset of function signatures. For both functions and modules, we consider not just
exact
match but also various flavors of
relaxed
match. We describe various applications of signature matching as a tool for using software libraries, inspired by the use of our implementation of a function signature matcher written in Standard ML.
Tail recursion elimination in deductive databases
Authors: Ross Kenneth A.
Published: July 2002

We consider an optimization technique for deductive and relational databases. The optimization technique is an extension of the magic templates rewriting, and it can improve the performance of query evaluation by not materializing the extension of intermediate views. Standard relational techniques, such as unfolding embedded view definitions, do not apply to recursively defined views, and so alternative techniques are necessary. We demonstrate the correctness of our rewriting. We define a class of “nonrepeating” view definitions, and show that for certain queries our rewriting performs at least as well as magic templates on nonrepeating views, and often much better. A syntactically recognizable property, called “weak right-linearity”, is proposed. Weak right-linearity is a sufficient condition for nonrepetition and is more general than right-linearity. Our technique gives the same benefits as right-linear evaluation of right-linear views, while applying to a significantly more general class of views.
Implementing sequentially consistent shared objects using broadcast and point-to-point communication
Authors: Fekete Alan , Kaashoek M. Frans , Lynch Nancy
Published: July 2002

This paper presents and proves correct a distributed algorithm that implements a sequentially consistent collection of shared read/update objects. This algorithm is a generalization of one used in the Orca shared object system. The algorithm caches objects in the local memory of processors according to application needs; each read operation accesses a single copy of the object, while each update accesses all copies. The algorithm uses broadcast communication when it sends messages to replicated copies of an object, and it uses point-to-point communication when a message is sent to a single copy, and when a reply is returned. Copies of all objects are kept consistent using a strategy based on sequence numbers for broadcasts.

The algorithm is presented in two layers. The lower layer uses the given broadcast and point-to-point communication services, plus sequence numbers, to provide a new communication service called acontext multicast channel. The higher layer uses a context multicast channel to manage the object replication in a consistent fashion. Both layers and their combination are described and verified formally, using the I/O automation model for asynchronous concurrent systems.
Description and performance analysis of signature file methods for office filing
Authors: Faloutsos Christos , Christodoulakis Stavros
Published: July 2002

Signature files have attracted a lot of interest as an access method for text and specifically for messages in the office environment. Messages are stored sequentially in the message file, whereas their hash-coded abstractions (signatures) are stored sequentially in the signature file. To answer a query, the signature file is examined first, and many nonqualifying messages are immediately rejected. In this paper we examine the problem of designing signature extraction methods and studying their performance. We describe two old methods, generalize another one, and propose a new method and its variation. We provide exact and approximate formulas for the dependency between the false drop probability and the signature size for all the methods, and we show that the proposed method (VBC) achieves approximately ten times smaller false drop probability than the old methods, whereas it is well suited for collections of documents with variable document sizes.
Estimation of lower bounds in scheduling algorithms for high-level synthesis
Authors: Tiruvuri Giri , Chung Moon
Published: July 2002

To produce efficient design, a high-level synthesis system should be able to analyze a variety of cost-performance tradeoffs. The system can use lower-bound performance estimated methods to identify and puune inferior designs without producint complete designs. We present a lower-bound performance estimate method that is not only faster than existing methods, but also produces better lower bounds. In most cases, the lower bound produced by our algorithm is tight.

Scheduling algorithms such as branch-and-bound need fast and effective lower-bound estimate methods, often for a large number of partially scheduled dataflow graphs, to reduce the search space. We extend our method to efficiently estimate completion time of partial schedules. This problem is not addressed by existing methods in the literature. Our lower-bound estimate is shown to by very effective in reducing the size of the search space when used in a branch-and-bound scheduling algorithm.

Our methods can handle multicycle operations, pipelined functional units, and chaining of operations. We also present an extension to handle conditional branches. A salient feature of the extended method is its applicability to speculative execution as well as C-select implementation of conditional branches.
Maximal objects and the semantics of universal relation databases
Authors: Maier David , Ullman Jeffrey D.
Published: July 2002

The universal relation concept is intended to provide the database user with a simplified model in which he can compose queries without regard to the underlying structure of the relations in the database. Frequently, the lossless join criterion provides the query interpreter with the clue needed to interpret the query as the user intended. However, some examples exist where interpretation by the lossless-join rule runs contrary to our intuition. To handle some of these cases, we propose a concept called
maximal objects
, which modifies the universal relation concept in exactly those situations where it appears to go awry—when the underlying relational structure has “cycles.” We offer examples of how the maximal object concept provides intuitively correct interpretations. We also consider how one might construct maximal objects mechanically from purely syntactic structural information—the relation schemes and functional dependencies—about the database.
Primality testing using elliptic curves
Authors: Goldwasser Shafi , Kilian Joe
Published: July 2002

We present a primality proving algorithm—a probablistic primality test that produces short certificates of primality on prime inputs. We prove that the test runs in expected polynomial time for all but a vanishingly small fraction of the primes. As a corollary, we obtain an algorithm for generating large certified primes with distribution statistically close to uniform. Under the conjecture that the gap between consecutive primes is bounded by some polynomial in their size, the test is shown to run in expected polynomial time for all primes, yielding a Las Vegas primality test.

Our test is based on a new methodology for applying group theory to the problem of prime certification, and the application of this methodology using groups generated by elliptic curves over finite fields.

We note that our methodology and methods have been subsequently used and improved upon, most notably in the primality proving algorithm of Adleman and Huang using hyperelliptic curves and in practical primality provers using elliptic curves.
Automatic Theorem Proving With Renamable and Semantic Resolution
Authors: Slagle James R.
Published: July 2002

The theory of J. A. Robinson's resolution principle, an inference rule for first-order predicate calculus, is unified and extended. A theorem-proving computer program based on the new theory is proposed and the proposed semantic resolution program is compared with hyper-resolution and set-of-support resolution programs. Renamable and semantic resolution are defined and shown to be identical. Given a model
M
, semantic resolution is the resolution of a latent clash in which each “electron” is at least sometimes false under
M
; the nucleus is at least sometimes true under
M
.

The completeness theorem for semantic resolution and all previous completeness theorems for resolution (including ordinary, hyper-, and set-of-support resolution) can be derived from a slightly more general form of the following theorem. If
U
is a finite, truth-functionally unsatisfiable set of nonempty clauses and if
M
is a ground model, then there exists an unresolved maximal semantic clash [
E
1
,
E
2
, · · ·,
E
q
,
C
] with nucleus
C
such that any set containing
C
and one or more of the electrons
E
1
,
E
2
, · · ·,
E
q
is an unresolved semantic clash in
U
.
Power optimization using divide-and-conquer techniques for minimization of the number of operations
Authors: Hong Inki , Potkonjak Miodrag , Karri Ramesh
Published: July 2002

We introduce an approach for power optimization using a set of compilation and architectural techniques. The key technical innovation is a novel divide-and-conquer compilation technique to minimize the number of operations for general computations. Our technique optimizes not only a significantly wider set of computations than the previously published techniques, but also outperforms (or performs at least as well as other techniques) on all examples. Along the architectural dimension, we investigate coordinated impact of compilation techniques on the number of processors which provide optimal trade-off between cost and power. We demonstrate that proper compilation techniques can significantly reduce power with bounded hardware cost. The effectiveness of all techniques and algorithms is documented on numerous real-life designs.
Algorithm 796
Authors: D'Amore Luisa , Laccetti Guiliano , Murli Almerico
Published: July 2002

A software package for the numerical inversion of a Laplace Transform function is described. Besides function values of
F
(
z
) for complex and real
z
, the user has only to provide the numerical value of the Laplace convergence abscissa σ
0
or, failing this, an upper bound to this quantity, and the accuracy he or she requires in the computed value of the inverse Transform. The method implemented is based on a Fourier series expansion of the inverse transform, and it is especially suitable when such inverse Laplace Transform is sectionally continuous.
An impact analysis method for safety-critical user interface design
Authors: Galliers Julia , Sutcliffe Alistair , Minocha Shailey
Published: July 2002

We describe a method of assessing the implications for human error on user interface design of safety-critical systems. In previous work we have proposed a taxonomy of influencing factors that contribute to error. In this article, components of the taxonomy are combined into a mathematical and causal model for error, represented as a Bayesian Belief Net (BBN). The
BBN quantifies error influences arising from user knowledge, ability, and the task environ-ment, combined with factors describing the complexity of user action and user interface quality. The BBN model predicts probabilities of different types of errorslips and mistakes for each component action of a task involving user-system interaction. We propose an Impact Analysis Method that involves running test scenarios against this causal model of error in order to determine user interactions that are prone to different types of error. Applying the proposed method will enable the designer to determine the combinations of influencing factors and their interactions that are most likely to influence human error. Finally we show how such scenario-based causal analysis can be useful as a means of focusing on relevant guidelines for safe user interface design. The proposed method is demonstrated through a case study of an operator performing a task using the control system for a laser spectrophotometer.We describe a method of assessing the implications for human error on user interface design of safety-critical systems. In previous work we have proposed a taxonomy of influencing factors that contribute to error. In this article, components of the taxonomy are combined into a mathematical and causal model for error, represented as a Bayesian Belief Net (BBN). The
BBN quantifies error influences arising from user knowledge, ability, and the task environ-ment, combined with factors describing the complexity of user action and user interface quality. The BBN model predicts probabilities of different types of errorslip for each component action of a task involving user-system interaction. We propose an Impact Analysis Method that involves running test scenarios against this causal model of error in order to determine user interactions that are prone to different types of error. Applying the proposed method will enable the designer to determine the combinations of influencing factors and their interactions that are most likely to influence human error. Finally we show how such scenario-based causal analysis can be useful as a means of focusing on relevant guidelines for safe user interface design. The proposed method is demonstrated through a case
study of an operator performing a task using the control system for a laser spectrophotometer.
A class of sorting algorithms based on Quicksort
Authors: Wainwright Roger L.
Published: July 2002

Bsort, a variation of Quicksort, combines the interchange technique used in Bubble sort with the Quicksort algorithm to improve the average behavior of Quicksort and eliminate the worst case situation of O(n
2
) comparisons for sorted or nearly sorted lists. Bsort works best for nearly sorted lists or nearly sorted in reverse.
A unified approach for hierarchical adaptive tesselation of surfaces
Authors: Velho Luiz , de Figueiredo Luiz Henrique , Gomes Jonas
Published: July 2002

This paper introduces a unified and general tesselation algorithm for parametric and implicit surfaces. The algorithm produces a hierarchial mesh that is adapted to the surface geometry and has a multiresolution and progressive structure. The representation can be exploited with advantages in several applications.
Multigrain shared memory
Authors: Yeung Donald , Kubiatowicz John , Agarwal Anant
Published: July 2002

Parallel workstations, each comprising tens of processors based on shared memory, promise cost-effective scalable multiprocessing. This article explores the coupling of such small- to medium-scale shared-memory multiprocessors through software over a local area network to synthesize larger shared-memory systems. We call these systems Distributed Shared-memory MultiProcessors (DSMPs). This article introduces the design of a shared-memory system that uses multiple granularities of sharing, called MGS, and presents a prototype implementation of MGS on the MIT Alewife multiprocessor. Multigrain shared memory enables the collaboration of hardware and software shared memory, thus synthesizing a single transparent shared-memory address space across a cluster of multiprocessors. The system leverages the efficient support for fine-grain cache-line sharing within multiprocessor nodes as often as possible, and resorts to coarse-grain page-level sharing across nodes only when absolutely necessary. Using our prototype implementation of MGS, an in-depth study of several shared-memory application is conducted to understand the behavior of DSMPs. Our study is the first to comprehensively explore the DSMP design space, and teh compare the performance of DSMPs against all-software and all-hardware DSMs on a signle experimental platform. Keeping the total number of processors fixed, we show that applications execute up to 85% faster on a DSMP as compared to an all-software DSM. We also show that all-hardware DSMs hold a significant performance advantage over DSMPs on challenging applications, between 159% and 1014%. However, program transformations to improve data locality for these applications allow DSMPs to almost match the performance of an all-hardware multiprocessor of the same size.
A knowledge-based method for inferring semantic concepts from visual models of system behavior
Authors: Mills Kevin L. , Gomaa Hassan
Published: July 2002

Software designers use visual models, such as data flow/control flow diagrams or object collaboration diagrams, to express system behavior in a form that can be understood easily by users and by pogrammers, and from which designers can generate a software architecture. The research described in this paper is motivated by a desire to provide an automated designer's assistant that can generate software architectures for concurrent systems directly from behavioral models expressed visually as flow diagrams. To achieve this goal, an automated designer's assistant must be capable of interpreting flow diagrams in semantic, rather than syntactic, terms. While semantic concepts can be attached manually to diagrams using labels, such as stereotypes in the Unified Model Language (UML), this paper considers the possibility of providing autmated assistance to infer appropriate tags for symbols on a flow diagram. The approach relies upon constructing an underlying metamodel that defines semantic concepts based upon (1) syntactic relationships among visual symbols and (2) inheritance relationships among semantic concepts. Given such a metamodel, a rule-based inference engine can, in many situations, infer the presence of semantic concepts on flow diagram, and can tag symbols accordingly. Futher, an object-oriented query system can compare semantic tags on digram instances for conformance with their definition in the metamodel. To illustrate the approach, the paper describes a metamodel for data flow/control flow diagrams used in the context of a specific software modeling method, Concurrent Object-Based Real-time Analysis (COBRA). The metamodel is implemented using an expert-system shell, CLIPS V6.0, which integrates an object-oriented language with a rule-based inference engine.

The paper applies the implemented metamodel to design software for an automobile cruise-control system and provides an evaluation of the approach based upon results from four case studies. For the case studies, the implemented metamodel recognized, automatically and correctly, the existence of 86% of all COBRA semantic concepts within the flow diagrams. Varying degrees of human assistance were used to correctly identify the remaining semantic concepts within the diagrams: in two percent of the cases the implemented metamodel reached tentative classifications that a designer was asked to confirm or override; in four percent of the cases a designer was asked to provide additional information before a concept was classified; in the remaining eight percent of the cases the designer was asked to identify the concept.
HCI in the global knowledge-based economy
Authors: Vicente Kim J.
Published: July 2002

Increasingly, people are being required to perform open-ended intellectual tasks that require discretionary decision making. These demands require a relatively unique approach to the design of computer-based support tools. A review of the characteristics associated with the global knowledge-based economy strongly suggests that there will be an increasing need for workers, managers, and organizations to adapt to change and novelty. This is equivalent to a call for designing computer tools that foster continuous learning. There are reasons to believe that the need to support adaptation and continuous learning will only increase. Thus, in the new millennium HCI should be concerned with explicitly designing for worker adaptation. The cognitive work analysis framework is briefly described as a potential programmatic approach to this practical design challenge.
Performing remote operations efficiently on a local computer network
Authors: Spector Alfred Z.
Published: July 2002

A communication model is described that can serve as a basis for a highly efficient communication subsystem for local networks. The model contains a taxonomy of communication instructions that can be implemented efficiently and can be a good basis for interprocessor communication. These communication instructions, called remote references, cause an operation to be performed by a remote process and, optionally, cause a value to be returned. This paper also presents implementation considerations for a communication system based upon the model and describes an experimental communication subsystem that provides one class of remote references. These remote references take about 150 microseconds or 50 average instruction times to perform on Xerox Alto computers connected by a 2.94 megabit Ethernet.
Beyond programming languages
Authors: Winograd Terry
Published: July 2002

As computer technology matures, our growing ability to create large systems is leading to basic changes in the nature of programming. Current programming language concepts will not be adequate for building and maintaining systems of the complexity called for by the tasks we attempt. Just as high level languages enabled the programmer to escape from the intricacies of a machine's order code, higher level programming systems can provide the means to understand and manipulate complex systems and components. In order to develop such systems, we need to shift our attention away from the detailed specification of algorithms, towards the description of the properties of the packages and objects with which we build. This paper analyzes some of the shortcomings of programming languages as they now exist, and lays out some possible directions for future research.
Optimal shift strategy for a block-transfer CCD memory
Authors: Sites Richard L.
Published: July 2002

For the purposes of this paper, a block-transfer CCD memory is composed of serial shift registers whose shift rate can vary, but which have a definite minimum shift rate (the refresh rate) and a definite maximum shift rate. The bits in the shift registers are numbered 0 to
N
- 1, and blocks of
N
bits are always transferred, always starting at bit 0. What is the best shift strategy so that a block transfer request occurring at a random time will have to wait the minimal amount of time before bit 0 can be reached? The minimum shift rate requirement does not allow one to simply “park” at bit 0 and wait for a transfer request. The optimal strategy involves shifting as slowly as possible until bit 0 is passed, then shifting as quickly as possible until a critical boundary is reached, shortly before bit 0 comes around again. This is called the “hurry up and wait” strategy and is well known outside the computer field. The block-transfer CCD memory can also be viewed as a paging drum with a variable (bounded) rotation speed.
Algorithm 490: The Dilogarithm function of a real argument [S22]
Authors: Ginsberg Edward S. , Zaborowski Dorothy
Published: July 2002

The dilogarithm function [1-3], defined by
Li
2
(
x
) = - ∫

x

0
(1/
z
) ln (1 -
z
)
dz
, (1) occurs in several different applications in physics and engineering, ranging from quantum electrodynamics, to network analysis, to the thermodynamics of ideal ferromagnets, to the structure of polymers. A new function subroutine is developed which computes the dilogarithm function of a real argument to an accuracy of a few parts in 10
15
. This program was designed to be included in the usual package of library subprograms relied upon by most users. It employs an alternative computational approach to a previously published algorithm [4].
Efficient implementation of a variable projection algorithm for nonlinear least squares problems
Authors: Krogh Fred T.
Published: July 2002

Nonlinear least squares problems frequently arise for which the variables to be solved for can be separated into a linear and a nonlinear part. A variable projection algorithm has been developed recently which is designed to take advantage of the structure of a problem whose variables separate in this way. This paper gives a slightly more efficient and slightly more general version of this algorithm than has appeared earlier.
Wengert's numerical method for partial derivatives, orbit determination and quasilinearization
Authors: Bellman R. E. , Kagiwada H. , Kalaba R. E.
Published: July 2002

In a recent article in the
Communications of the ACM
, R. Wengert suggested a technique for machine evaluation of the partial derivatives of a function given in analytical form. In solving nonlinear boundary-value problems using quasilinearization many partial derivatives must be formed analytically and then evaluated numerically. Wengert's method appears very attractive from the programming viewpoint and permits the treatment of large systems of differential equations which might not otherwise be undertaken.
Survey of formula manipulation
Authors: Sammet Jean E.
Published: July 2002

The field of formula manipulation is surveyed, with particular attention to the specific capabilities of differentiation, integration and the supporting capabilities of simplification, displays and input/output editing, and precision arithmetic. General systems—both batch and online—are described. Finally, some programs to solve specific applications are discussed.
Accelerating shared virtual memory via general-purpose network interface support
Authors: Bilas Angelos , Jiang Dongming , Singh Jaswinder Pal
Published: July 2002

Clusters of symmetric multiprocessors (SMPs) are important platforms for high-performance computing. With the success of hardware cache-coherent distributed shared memory (DSM), a lot of effort has also been made to support the coherent shared-address-space programming model in software on clusters. Much research has been done in fast communication on clusters and in protocols for supporting software shared memory across them. However, the performance of software virtual memory (SVM) is still far from that achieved on hardware DSM systems. The goal of this paper is to improve the performance of SVM on system area network clusters by considering communication and protocol layer interactions. We first examine what are the important communication system bottlenecks that stand in the way of improving parallel performance of SVM clusters; in particular, which parameters of the communication architecture are most important to improve further relative to processor speed, which ones are already adequate on modern systems for most applications, and how will this change with technology in the future. We find that the most important communication subsystem cost to improve is the overhead of generating and delivery interrupts for asynchronous protocol processing. Then we proceed to show, that by providing simple and general support for asynchronous message handling in a commodity network interface (NI) and by altering SVM protocols appropriately, protocol activity can be decoupled from asynchronous message handling, and the need for interrupts or polling can be eliminated. The NI mechanisms needed are generic, not SVM-dependent. We prototype the mechanisms and such asynchronous home-basedLRCprotocol, calledGeNIMA(GEneral-purpose Network Interface support for shared Memory Abstractions), on a cluster of SMPs with a programmable NI. We find that the performance improvements are substantial, bringing performance on a small-scale SMP cluster much closer to that of hardware-coherent shared memory for many applications, and we show the value of each of the mechanisms in different applications.
Data allocation in distributed database systems
Authors: Apers Peter M. G.
Published: July 2002

The problem of allocating the data of a database to the sites of a communication network is investigated. This problem deviates from the well-known file allocation problem in several aspects. First, the objects to be allocated are not known a priori; second, these objects are accessed by schedules that contain transmissions between objects to produce the result. A model that makes it possible to compare the cost of allocations is presented; the cost can be computed for different cost functions and for processing schedules produced by arbitrary query processing algorithms.

For minimizing the total transmission cost, a method is proposed to determine the fragments to be allocated from the relations in the conceptual schema and the queries and updates executed by the users.

For the same cost function, the complexity of the data allocation problem is investigated. Methods for obtaining optimal and heuristic solutions under various ways of computing the cost of an allocation are presented and compared.

Two different approaches to the allocation management problem are presented and their merits are discussed.
Efficient generation of shared RSA keys
Authors: Boneh Dan , Franklin Matthew
Published: July 2002

We describe efficient techniques for a number of parties to jointly generate an RSA key. At the end of the protocol an RSA modulus
N
=
pq
is publicly known. None of the parties know the factorization of
N
. In addition a public encryption exponent is publicly known and each party holds a share of the private exponent that enables threshold decryption. Our protocols are efficient in computation and communication. All results are presented in the
honest but curious
scenario (passive adversary).
The future of e-learning communities
Authors: Bruckman Amy
Published: July 2002

The learning potential of Internet technology can come from the most familiar sources---peers and elders.
Sequent calculi for propositional nonmonotonic logics
Authors: Bonatti Piero Andrea , Olivetti Nicola
Published: July 2002

A uniform proof-theoretic reconstruction of the major nonmonotonic logics is introduced. It consists of analytic sequent calculi where the details of nonmonotonic assumption making are modelled by an axiomatic rejection method. Another distinctive feature of the calculi is the use of provability constraints that make reasoning largely independent of any specific derivation strategy. The resulting account of nonmonotonic inference is simple and flexible enough to be a promising playground for investigating and comparing proof strategies, and for describing the behavior of automated reasoning systems. We provide some preliminary evidence for this claim by introducing optimized calculi, and by simulating an existing tableaux-based method for circumscription. The calculi for skeptical reasoning support concise proofs that may depend on a strict subset of the given theory. This is a difficult task, given the nonmonotonic behavior of the logics.
Integrating security in a large distributed system
Authors: Satyanarayanan M.
Published: July 2002

Andrew is a distributed computing environment that is a synthesis of the personal computing and timesharing paradigms. When mature, it is expected to encompass over 5,000 workstations spanning the Carnegie Mellon University campus. This paper examines the security issues that arise in such an environment and describes the mechanisms that have been developed to address them. These mechanisms include the logical and physical separation of servers and clients, support for secure communication at the remote procedure call level, a distributed authentication service, a file-protection scheme that combines access lists with UNIX mode bits, and the use of encryption as a basic building block. The paper also discusses the assumptions underlying security in Andrew and analyzes the vulnerability of the system. Usage experience reveals that resource control, particularly of workstation CPU cycles, is more important than originally anticipated and that the mechanisms available to address this issue are rudimentary.
Object specialization
Authors: Sciore Edward
Published: July 2002

Specialization hierarchies typically are treated as type-level constructs and are used to define various inheritance mechanisms. In this paper we consider specialization at the level of objects. We show that doing so creates a more flexible and powerful notion of inheritance by allowing objects to define their own inheritance path. Object specialization can also be used to model certain forms of versioning, implement data abstraction, and provide a “classless” prototype-based language interface to the user.
Accessing bit fields in FORTRAN-77
Authors: Hayes Manny
Published: July 2002

By incorporating bit-manipulation routines into Fortran-77, it is now possible to manipulate bits or partial word operands without having to write assembly-coded subroutines. Because the routines are now acceptable to Fortran-77 compilers, the accessing code is now portable to other Fortran Machines.
A technique for two-dimensional pattern matching
Authors: Zhu Rui Feng , Takaoka Tadao
Published: July 2002

By reducing an array matching problem to a string matching problem in a natural way, it is shown that efficient string matching algorithms can be applied to arrays, assuming that a linear preprocessing is made on the text.
An experimental analysis of the performance of fourth generation tools on PCs
Authors: Matos Victor M. , Jalics Paul J.
Published: July 2002

The performance of several Fourth Generation Language (4GL) tools is analyzed empirically and compared with equivalent programs written in the third generation COBOL programming language. A set of performance benchmarks consisting of thirteen separate functions is presented which encompasses the areas of simulating the operators of the relational algebra, accessing records in the database, and updating the database. This serves as a baseline for comparing the various 4GL systems.
Three papers from the third international conference on information systems: introduction
Authors: Ginzberg Michael J.
Published: July 2002

The International Conference on Information Systems provides an annual forum for keeping abreast of the latest trends and developments in IS research. The conference is sponsored by the TIMS College on Information Systems and the Society for Information Management in cooperation with ACM SIGBDP.

The Third International Conference on Information Systems was held December 13-15, 1982, in Ann Arbor, Michigan, with Alan G. Merten as chairman. Two papers from that conference have been published in recent issues, one by Ahmed S. Zaki in February and one by Margrethe H. Olson in March. They were concerned with the impact of information systems on organizations and society. The following three papers discuss new methodological approaches to the development and use of information systems.

Abdel-Hamid and Madnick focus on the problem of estimating resource requirements and schedules for software development projects. They use System Dynamics, a tool for modeling systems consisting of multiple, interacting feedback loops, to explore this problem. Their results show that policies often built into the project management process can assure that projects will fail to meet their scheduled completion, regardless of the accuracy of resource requirement and project size estimates.

Hart Will explores the idea of a single, unified interface to provide auditors with the access they need in today's computer-based accounting environment. Instead of the proliferation of audit software seen so far, he suggests that a common language for accessing data, programs, and text can be developed. He describes the design of such a language and speculates about its likely impact.

Mason and Carey's paper is concerned with the area of information systems design. They present an Architecture-Based Methodology for prototyping interactive information systems, derived from an analogy to the architectural approach to designing buildings or other physical structures. They discuss both the special role of “architect” and the tools required to support this approach to system design, including one commercially available program product.
Schematic pseudocode for program constructs and its computer automation by SCHEMACODE
Authors: Robillard Pierre N.
Published: July 2002

To achieve program control flow representation that is relatively independent of any given programming language, schematic pseudocode (SPC) uses a perceptual notation system composed of schemata whose syntax rules are described by a grammar. Source code documentation is supported by operational comments, and translation into a target procedural language is fully automatic.
Spreadsheet calculations of probabilities from the F, t, χ
2
, and normal distribution
Authors: Landram Frank G. , Cook James R. , Johnston Marvin
Published: July 2002

By computing probabilities from the normalization of the F distribution (instead of by numerical integration methods), statistical capabilities in spreadsheet operations can be greatly expanded and enhanced.
Bounding delay on a multifarious token ring network
Authors: Gaitonde S. S. , Jacobson Doug , Pohm A. V.
Published: July 2002

Interest in integrating voice and data on local computer networks has been building in recent years. Subsequently, much research has been devoted to various techniques that are implementable on existing networks using current standards. This exposition discusses the design issues in implementing a document retrieval system on a token ring network.
Imprecise schema: a rationale for relations with embedded subrelations
Authors: Dreizen Howard M. , Chang Shi-Kuo
Published: July 2002

Exceptional conditions
are anomalous data which meet the intent of a schema but not the schema definition, represent a small proportion of the database extension, and may become known only after the schema is in use. Admission of exceptional conditions is argued to suggest a representation that locally stretches the schema definition by use of relations with embedded subrelations. Attempted normalization of these relations to 1NF does not yield the static schema typically associated with such transformations. A class of relations, termed Exceptional Condition Nested Form (ECNF), is defined which allows the necessary representation of exceptional conditions while containing sufficient restrictions to prevent arbitrary and chaotic inclusion of embedded subrelations. Queries on a subset of exceptional conditions, the
exceptional constraints
, are provided an interpretation via an algorithm that transforms ECNF relations into 1NF relations containing two types of null values. Extensions of relational algebraic operators, suitable for interactive query navigation, are defined for use with ECNF relations containing all forms of exceptional conditions.
Japan's view of EC '92
Authors: Ono Eiichi
Published: July 2002

Delivered at the Armed Forces Communication and Electronics Association's EC '92 Symposium in December 1989, this speech focuses on the European semiconductor industry-where Japan ranks as the second largest exporter-and technology transfer of dual-use products from Japan.
EC commission communication on establishing an information services market
Authors: European Commission CORPORATE
Published: July 2002

The following is an excerpt from the communciation sent by the European Commission to the Council of Ministers explaining the rationale for an internal information services market. It is followed by the Counicl's formal decision and budget allocation totalling $36 million.
Retrospective on DACNOS
Authors: Geihs Kurt , Hollberg Ulf
Published: July 2002

Heterogeneity of hardware and software is a fact in most distributed computing environments. The DACNOS prototype is a network operating system that enables resource sharing in such environments. It extends the local operating systems without interfering with existing programs. It provides comprehensive system level support for distributed applications.
Improper intersection of algebraic curves
Authors: Abhyankar Shreeram S. , Chandrasekar Srinivasan , Chandru Vijaya
Published: July 2002

Bezout's theorem gives an upper bound on the degree of the intersection of properly intersecting algebraic varieties. In spaces of dimension higher than two, however, intersections between many algebraic varieties such as curves are improper. Bezout's theorem cannot be directly used to bound the number of points at which these curves intersect. In this paper an algebrogeometric technique is developed for obtaining an upper bound on the number of intersection points of two irreducible algebraic curves in
k
-dimensional space. The theorems obtained are applied to the specific case of intersecting algebraic space curves in three-dimensional space, and a number of examples are analyzed in this regard. The implications of the derived results for computer-aided geometric design are discussed.
On the equivalence of an Egd to a set of Fd's
Authors: Graham Marc H. , Wang Ke
Published: July 2002

The question “Is a given join dependency equivalent to some set of multivalued dependencies?” led to the development of acyclicity theory [1]. The central question of this paper is: “Is a given equality-generating dependency equivalent to a set of functional dependencies?” An algorithm is presented that answers that question in polynomial time without using the chase process and, in the case of a “yes” answer, can be used to find (a cover of) the set of functional dependencies involved. This question is also related to the similar question about join dependencies and multivalued dependencies by proving a result about the hypergraph representation of an egd. It is interesting to note that a minimal representation of an egd must be β-acyclic for the egd to be equivalent to a set of fd's, in contrast to the jd/mvd case, in which only α-acyclicity is needed. The β-acyclicity of an egd not necessarily minimal is always sufficient for the egd to be equivalent to a set of fd's as shown. Finally, the algorithm is extended for a single egd to answer the question whether a set of egd's with the same right-hand-side column is equivalent to a set of fd's.
Inside risks: insecurity about security?
Authors: Neumann Peter G.
Published: July 2002

Background A few highly visible cases of computer system exploitations have raised general awareness of existing vulnerabilities and the considerable risks they entail.
Computer perspectives: the bandwidth famine
Authors: Wilkes Maurice V.
Published: July 2002

A number of years ago I visited a young and successful computer company and was given a tour of the facilities by one of the directors. We passed offices in which people were working at computer terminals; I was told they constituted the accounts department. A little further on we came to the software department; here people were also using terminals. “Now,” said my host, “I will show you the hardware department.” To my surprise, instead of the oscilloscopes and waveform analyzers that I had expected to find, I saw more computer terminals. This was a sign of the times.

Today, the designer of printed circuit boards such as those intended to be plugged into PCs, has a great variety of software tools from which to choose: programs for layout and routing; programs for checking that the design rules have been followed correctly; logic simulators for checking that the design is functionally correct; and more elaborate simulators for checking the timing. These tools make it possible to produce a working prototype without performing any experimental work on a laboratory bench.

In the dark ages of electronics, the debugging of circuits was carried out using experimental versions made by screwing the components down on a piece of wood and connecting them. The behavior of the circuit was checked using an oscilloscope. These experimental versions were known as breadboards, because someone had compared them to those boards on which bread was sliced. The wooden board has been obsolete for years, but the term has survived. A modern version of the breadboard (still used occasionally) is the wire-wrapped prototype. It is, however, costly in time and money and the effort spent on it does not advance the physical design of the final product. Moreover, in certain respects, particularly as regards electrical interference and cross talk, the wire-wrapped version may give misleading information.