bluuebunny/crossref_metadata_2025 huggingface dataset:
An experiment in high level language microprogramming and verification
Authors: Patterson David A.
Published: July 2002

The STRUM system was created to apply software engineering techniques to microprogramming. It provides the tools that allow the microprogrammer to use high level language, structured programming, and formal program verification to create emulations for a horizontally microprogrammed computer. This system is evaluated in two parts: (1) High level microprogramming language design and its use in structured microprogramming; and (2) Verification of a large microprogram. Both parts of this evaluation include experimental results. Part I includes a comparison of an emulation created using traditional techniques to the same emulation created using the STRUM system. Part II describes the formal verification of a 1700 line program that was immediately subjected to extensive testing. This work provides new results on the efficiency of high level microprogramming languages, the effectiveness of peephole optimization for microcode and the practicality of formal microprogram verification.
Deletion in two-dimensional quad trees
Authors: Samet Hanan
Published: July 2002

An algorithm for deletion in two-dimensional quad trees that handles the problem in a manner analogous to deletion in binary search trees is presented. The algorithm is compared with a proposed method for deletion which reinserts all of the nodes in the subtrees of the deleted node. The objective of the new algorithm is to reduce the number of nodes that need to be reinserted. Analysis for complete quad trees shows that the number of nodes requiring reinsertion is reduced to as low as 2/9 of that required by the old algorithm. Simulation tests verify this result. Reduction of the number of insertions has a similar effect on the number of comparison operations. In addition, the total path length (and balance) of the resulting tree is observed to remain constant or increase slightly when the new algorithm for deletion is used, whereas use of the old algorithm results in a significant increase in the total path length for large trees.
The impact of distributions and disciplines on multiple processor systems
Authors: Sauer Charles H. , Chandy K. Mani
Published: July 2002

Simple queueing models are used to study the performance tradeoffs of multiple processor systems. Issues considered include the impact of CPU service disciplines and distributions, level of multiprogramming, multitasking, and job priorities.
Experiments with some algorithms that find central solutions for pattern classification
Authors: Slagle James
Published: July 2002

In two-class pattern recognition, it is a standard technique to have an algorithm finding hyperplanes which separates the two classes in a linearly separable training set. The traditional methods find a hyperplane which separates all points in one class from all points in the other, but such a hyperplane is not necessarily centered in the empty space between the two classes. Since a central hyperplane does not favor one class or the other, it should have a lower error rate in classifying new points and is therefore better than a noncentral hyperplane. Six algorithms for finding central hyperplanes are tested on three data sets. Although frequently used in practice, the modified relaxation algorithm is very poor. Three algorithms which are defined in the paper are found to be quite good.
Reasoning about arrays
Authors: Reynolds John C.
Published: July 2002

A variety of concepts, laws, and notations are presented which facilitate reasoning about arrays. The basic concepts include intervals and their partitions, functional restriction, images, pointwise extension of relations, ordering, single-point variation of functions, various equivalence relations for array values, and concatenation. The effectiveness of these ideas is illustrated by informal descriptions of algorithms for binary search and merging, and by a short formal proof.
A method for obtaining digital signatures and public-key cryptosystems
Authors: Rivest R. L. , Shamir A. , Adleman L.
Published: July 2002

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product,
n
, of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor,
n
.
The editing of picture segmentations using local analysis of graphs
Authors: Tanimoto Steven L. , Pavlidis Theodosios
Published: July 2002

A major problem in picture processing is the elimination of the large number of spurious regions that result from an initial segmentation by region growing techniques. Such regions have been eliminated either on the basis of semantic information or on the basis of size and contrast. A scheme is presented which performs eliminations on the basis of local properties of the region adjacency graph. The scheme is based on definitions of graph properties which are satisfied when a spurious region is present; then editing is equivalent to fast graph operations. A number of examples are shown.
Distributed processes
Authors: Hansen Per Brinch
Published: July 2002

A language concept for concurrent processes without common variables is introduced. These processes communicate and synchronize by means of procedure calls and guarded regions. This concept is proposed for real-time applications controlled by microcomputer networks with distributed storage. The paper gives several examples of distributed processes and shows that they include procedures, coroutines, classes, monitors, processes, semaphores, buffers, path expressions, and input/output as special cases.
An encoding method for multifield sorting and indexing
Authors: Blasgen Michael W. , Casey Richard G. , Eswaran Kapali P.
Published: July 2002

Sequences of character strings with an order relation imposed between sequences are considered. An encoding scheme is described which produces a single, order-preserving string from a sequence of strings. The original sequence can be recovered from the encoded string, and one sequence of strings precedes another if and only if the encoding of the first precedes the encoding of the second. The strings may be variable length, without a maximum length restriction, and no symbols need be reserved for control purposes. Hence any symbol may occur in any string. The scheme is useful for multifield sorting, multifield indexing, and other applications where ordering on more than one field is important.
Compressed tries
Authors: Maly Kurt
Published: July 2002

This paper presents a new data structure, called a compressed trie or C-trie, to be used in information retrieval systems. It has the same underlying m-ary tree structure as a trie, where m is a parameter of the trie, but whereas the fields of the nodes in a trie have to be large enough to hold a key or at least a pointer, the fields in a C-trie are only one bit long. In the analysis part of the paper it will be shown that for a collection of n keys the retrieval time, measured in terms of bit inspections of one key, is of the order log
m
n and the storage requirement of the order n·(m + log
2
n) bits. This improvement in storage requirements and retrieval time is achieved at the cost of decreasing the flexibility of the structure, and therefore updating costs are increased. First the C-trie is analyzed as a data structure, and then several methods of its use for relatively static databases are discussed.
Experiments in text file compression
Authors: Rubin Frank
Published: July 2002

A system for the compression of data files, viewed as strings of characters, is presented. The method is general, and applies equally well to English, to PL/I, or to digital data. The system consists of an encoder, an analysis program, and a decoder. Two algorithms for encoding a string differ slightly from earlier proposals. The analysis program attempts to find an optimal set of codes for representing substrings of the file. Four new algorithms for this operation are described and compared. Various parameters in the algorithms are optimized to obtain a high degree of compression for sample texts.
Finding circles by an array of accumulators
Authors: Kimme Carolyn , Ballard Dana , Sklansky Jack
Published: July 2002

We describe an efficient procedure for detecting approximate circles and approximately circular arcs of varying gray levels in an edge-enhanced digitized picture. This procedure is an extension and improvement of the circle-finding concept sketched by Duda and Hart [2] as an extension of the Hough straight-line finder [6].
Scan conversion algorithms for a cell organized raster display
Authors: Barrett R. C. , Jordan B. W.
Published: July 2002

Raster scan computer graphics with “real time” character generators have previously been limited to alphanumeric characters. A display has been described which extends the capabilities of this organization to include general graphics.

Two fundamentally different scan conversion algorithms which have been developed to support this display are presented. One is most suitable to noninteractive applications and the other to interactive applications. The algorithms were implemented in Fortran on the CDC6400 computer. Results obtained from the implementations show that the noninteractive algorithms can significantly reduce display file storage requirements at little cost in execution time over that of a conventional raster display. The interactive algorithm can improve response time and reduce storage requirements.
The intrinsically exponential complexity of the circularity problem for attribute grammars
Authors: Jazayeri Mehdi , Ogden William F. , Rounds William C.
Published: July 2002

Attribute grammars are an extension of context-free grammars devised by Knuth as a mechanism for including the semantics of a context-free language with the syntax of the language. The circularity problem for a grammar is to determine whether the semantics for all possible sentences (programs) in fact will be well defined. It is proved that this problem is, in general, computationally intractable. Specifically, it is shown that any deterministic algorithm which solves the problem must for infinitely many cases use an exponential amount of time. An improved version of Knuth's circularity testing algorithm is also given, which actually solves the problem within exponential time.
Structured multiprogramming
Authors: Hansen Per Brinch
Published: July 2002

This paper presents a proposal for structured representation of multiprogramming in a high level language. The notation used explicitly associates a data structure shared by concurrent processes with operations defined on it. This clarifies the meaning of programs and permits a large class of time-dependent errors to be caught at compile time. A combination of critical regions and event variables enables the programmer to control scheduling of resources among competing processes to any degree desired. These concepts are sufficiently safe to use not only within operating systems but also within user programs.
A software design and evaluation system
Authors: Graham Robert M. , Clancy Gerald J. , DeVaney David B.
Published: July 2002

A critical failure of current software system design and implementation methodology is that the performance of a proposed design is not evaluated before it is actually implemented. In this paper the reasons for this failure are explored, and a new methodology which overcomes many of the difficulties is proposed. A system which integrates performance evaluation with design and implementation is described. This system is based on a simple, high level language which is used to describe the evolving system at all stages of its development. The source language description is used as direct input to performance analysis and simulation routines. Using the performance information obtained from these routines as feedback, the problems which adversely affect performance are detected early enough so that they can be corrected without costly major reimplementation of the proposed system.
Optimum data base reorganization points
Authors: Shneiderman Ben
Published: July 2002

In certain data base organization schemes the cost per access may increase due to structural inefficiencies caused by update. By reorganizing the data base the cost per access may be reduced. However, the high cost of a reorganization prohibits frequent reorganizations. This paper examines strategies for selecting the optimum reorganization points.
The distribution of a program in primary and fast buffer storage
Authors: Gelenbe Erol
Published: July 2002

A virtual memory computer system with a fast buffer (cache) memory between primary memory and the central processing unit is considered. The optimal distribution of a program between the buffer and primary memory is studied using the program's lifetime function. Expressions for the distribution of a program which maximizes the useful fraction of the cost-time integral of primary and fast buffer storage are obtained for swapping and nonswapping buffer management policies.
Proof linking
Authors: Fong Philip W. L. , Cameron Robert D.
Published: July 2002

Although mobile code systems typically employ link-time code verifiers to protect host computers from potentially malicious code, implementation flaws in the verifiers may still leave the host system vulnerable to attack. Compounding the inherent complexity of the verification algorithms themselves, the need to support lazy, dynamic linking in mobile code systems typically leads to architectures that exhibit strong interdependencies between the loader, the verifier, and the linker. To simplify verifier construction and provide improved assurances of verifier integrity, we propose a modular architecture based on the concept of proof linking. This architecture encapsulates the verification process and removes dependencies between the loader, the verifier, and the linker. We also formally model the process of proof linking and establish properties to which correct implementations must conform. As an example, we instantiate our architecture for the problem of Java bytecode verification and assess the correctness of this instantiation. Finally, we briefly discuss alternative mobile code verification architectures enabled by the proof-linking concept.
An efficient machine-independent procedure for garbage collection in various list structures
Authors: Schorr H. , Waite W. M.
Published: July 2002

A method for returning registers to the free list is an essential part of any list processing system. In this paper, past solutions of the recovery problem are reviewed and compared. A new algorithm is presented which offers significant advantages of speed and storage utilization. The routine for implementing this algorithm can be written in the list language with which it is to be used, thus insuring a degree of machine independence. Finally, the application of the algorithm to a number of different list structures appearing in the literature is indicated.
Bounded context syntactic analysis
Authors: Floyd Robert W.
Published: July 2002

Certain phase structure grammars define languages in which the phrasehood and structure of a substring of a sentence may be determined by consideration of only a bounded context of the substring. It is possible to determine, for any specified bound on the number of contextual characters considered, whether a given grammar is such a
bounded context grammar
. Such grammars are free from syntactic ambiguity. Syntactic analysis of sentences in a bounded context language may be performed by a standard process and requires a number of operations proportional to the length of sentence analyzed.

Bounded context grammars form models for most languages used in computer programming, and many methods of syntactic analysis, including analysis by operator precedence, are special cases of bounded context analysis.
Experimental personalized array translator system
Authors: Hellerman H.
Published: July 2002

A system designed for intimate man-machine interaction in a general-purpose problem-solving environment is experimentally operational. The system utilizes an array-oriented symbolic source language containing powerful statement types. These include numeric, Boolean, relational and selection operators on operands which can be entire arrays. The system also permits simple specification of test and argument arrays in single statements.

The completely symbolic operating system includes display and entry of program and data. Sequence control is aided by an interrupt switch which allows the user to interact with the program during execution. In addition to normal stored program sequencing, the system provides trace options and the ability to enter any statement for immediate execution.

Present implementation of the system is with an interpretive translator on an IBM 1620 computer.
Some characteristics of sorting computing systems using random access storage devices
Authors: Hubbard George U.
Published: July 2002

The substantial differences in characteristics of random access storage and tape devices dictate that concepts and objectives of computer program design be considered from the viewpoint of the external file medium used. This is particularly true in the case of sorting. In a tape-oriented system, the major sorting problem is that of minimizing merge time despite the limited orders of merge possible. In contrast, sorting in a random access-oriented system encourages the selection of the optimum order of merge from many possible orders. The latter problem is discussed in this paper, along with criteria developed for determining the optimum order of merge according to the various properties of random access storage devices. Attention is also given to the problem of key sorting versus record sorting and the possibly serious disadvantage of key sorting on a random access system.
An extension of Fibonaccian search to several variables
Authors: Krolak P. , Cooper L.
Published: July 2002

A technique which uses Fibonaccion search concepts has been developed to solve optimization problems involving unimodal functions of several variables. The technique has not been proven to be optimal in the sense that the one-dimensional Fibonaccion search is. However, it is valuable for certain kinds of calculations.
An automatic continuation strategy for the solution of singularly perturbed nonlinear boundary value problems
Authors: Cash J. R. , Moore G. , Wright R. W.
Published: July 2002

In a recent paper, the present authors derived an automatic continuation algorithm for the solution of linear singular perturbation problems. The algorithm was incorporated into two general-purpose codes for solving boundary value problems, and it was shown to deal effectively with a large test set of linear problems. The present paper describes how the conintuation algorithm for linear problems can be extended to deal with the nonlinear case. The results of exstensive numerical testing on a set of nonlinear singular perturbation problems are given, and these clearly demonstrate the efficacy of continuation for solving such problems.
A computational theory of normative positions
Authors: Sergot Marek
Published: July 2002

The Kanger-Lindahl theory of normative positions attempts to use a combination of deontic logic (the logic of obligation and permission) and a logic of action/agency to give a formal account of obligations, duties, rights, and other complex normative concepts. This paper presents a generalization and further development of this theory, together with methods for its automation and application to practical examples. The resulting theory is intended to be applied in the representation and analysis of laws, regulations, and contracts, in the specification of aspects of computer systems, in multiagent systems, and as a contribution to the formal theory of organizations. Particular attention is paid to representations at varying levels of detail and the relationships that hold between them. The last part presents Norman-G, an automated support system intended to facilitate application of the theory to the analysis of practical problems, with a small example to illustrate its use.
Modeling statecharts and activitycharts as signal equations
Authors: Beauvais J.-R. , Rutten E. , Gautier T. , Houdebine R. , Le. Guernic P. , Tang Y.-M.
Published: July 2002

The languages for modeling reactive systems are of different styles, like the imperative, state-based ones and the declarative, data-flow ones. They are adapted to different application domains. This paper, through the example of the languages Statecharts and Signal, shows a way to give a model of an imperative specification (Statecharts) in a declarative, equational one (Signal). This model constitutes a formal model of the Statemate semantics of Statecharts, upon which formal analysis techniques can be applied. Being a transformation from an imperative to a declarative structure, it involves the definition of generic models for the explicit management of state (in the case of control as well as of data). In order to obtain a structural construction of the model, a hierarchical and modular organization is proposed, including proper management and propagation of control along the hierarchy. The results presented here cover the essential features of Statecharts as well as of another language of Statemate: Activitycharts. As a translation, it makes multiformalism specification possible, and provides support for the integrated operation of the languages. The motivation lies also in the perspective of gaining access to the various formal analysis and implementation tools of the synchronous technology, using the DC1 exchange format, as in the Sacres programming environment.
A prototype electronic encyclopedia
Authors: Weyer Stephen A. , Borning Alan H.
Published: July 2002

We describe a prototype electronic encyclopedia implemented on a powerful personal computer, in which user interface, media presentation, and knowledge representation techniques are applied to improving access to a knowledge resource. In itself, an electronic encyclopedia is an important information resource, but this work also illustrates the issues and approaches for many types of electronic information retrieval environments. In the prototype we make dynamic use of the structure and semantics of the text articles and index of an existing encyclopedia, while experimenting with other forms of representation, such as simulation and videodisc images. We present a long-term vision of an intelligent user-interface agent; summarize previous work related to futuristic encyclopedias, electronic books, decision support systems, and knowledge libraries; and outline current and potential research directions.
The CIRRUS banking network
Authors: Gifford David , Spector Alfred
Published: July 2002

The CIRRUS banking network makes coast-to-coast automatic banking transactions possible. The system will soon be able to handle international currency transactions and point-of-sale transactions in stores.
Charcoal sketching: returning control to the artist
Authors: Bleser Teresa W. , Sibert John L. , McGee J. Patrick
Published: July 2002

Background: Traditional paint programs can be criticized on the grounds that they provide fewer degrees of freedom than conventional artistic media. Mouse or tablet input devices usually provide only (x, y) spatial information. Thus most paint programs allow continuous control of the path of a stroke, but render it with a single “brush shape” of fixed size and orientation and use menus, either stationary or appearing, for such tasks as changing “brush” shapes. This produces two distinct discontinuities for the artist. First is a physical discontinuity: stopping the act of drawing and making a brush selection using a different physical device, or using the same device to point at a menu selection. A second discontinuity is the cognitive one involved with deciphering the menu contents and making a selection. Although the second may be minimized by using iconic menus, these interruptions of the drawing act make it difficult or impossible for the artist to maintain the kind of continuous control over his or her medium that is required.

A particular example of this level of control is the continuous and immediate control that an artist maintains when sketching with a piece of charcoal or a pencil. By manipulating the implement, the artist can change the shape of its contact point with the drawing surface. By changes in pressure exerted with the implement against the surface, it is possible to control both the darkness (value) and width (weight) of the line. All of these factors are controlled by the artist in real time and with continuous feedback.

Both Greene [2] and Strassman [4] have presented methods for capturing more of the artist's “gesture” in the rendered stroke. However, Greene's technique depends on a special-purpose input device and Strassman's does not work in real time. Hill [3] describes a two-handed paintbrush with the off hand controlling a valuator that varies the 'brush width. The technique described here represents another way to provide such control to the user of an interactive paint program. It uses off-the-shelf hardware, is easy to implement, and works in real time. As a single-handed technique, it takes advantage of the artist's skill with existing media.
Concurrent search structure algorithms
Authors: Shasha Dennis , Goodman Nathan
Published: July 2002

A dictionary is an abstract data type supporting the actions member, insert, and delete. A search structure is a data structure used to implement a dictionary. Examples include B trees, hash structures, and unordered lists. Concurrent algorithms on search structures can achieve more parallelism than standard concurrency control methods would suggest, by exploiting the fact that many different search structure states represent one dictionary state. We present a framework for verifying such algorithms and for inventing new ones. We give several examples, one of which exploits the structure of Banyan family interconnection networks. We also discuss the interaction between concurrency control and recovery as applied to search structures.
Design implications of a task-driven approach to unstructured cognitive tasks in office work
Authors: Harris Sidney E. , Brightman Harvey J.
Published: July 2002

Previous research in modeling office activities has been primarily oriented toward office work that is structured and organized. In this paper we report on efforts to develop a new methodology for needs assessment evaluation. We use the Critical Task Method to identify the “bottleneck cognitive tasks” of principals with an unstructured work profile. Data were collected on the computer-support needs of faculty researchers, and the findings indicate that a “knowledge-based” design offers the most promise for delivering effective support. In addition, the systems design suggests the integration of text, data, voice, and images.
Coons Award Lecture
Authors: Greenberg Donald P.
Published: July 2002

The 1987 recipient of the Steven A. Coons Award speaks out on the state of the art in computer graphics and what the future can bring the industry under the right influences.
Undebuggability and cognitive science
Authors: Cherniak Christopher
Published: July 2002

A resource-realistic perspective suggests some indispensable features for a computer program that approximates all human mentality. The mind's program would differ fundamentally more from familiar types of software. These features seem to exclude reasonably establishing that a program correctly and completely models the mind.
Data structures for quadtree approximation and compression
Authors: Samet Hanan
Published: July 2002

A number of data structures for representing images by quadtrees without pointers are discussed. The image is treated as a collection of leaf nodes. Each leaf node is represented by use of a locational code corresponding to a sequence of directional codes that locate the leaf along a path from the root of the tree. Somewhat related is the concept of a forest which is a representation that consists of a collection of maximal blocks. It is reviewed and refined to enable the representation of a quadtree as a sequence of approximations. In essence, all BLACK and WHITE nodes are said to be of type GB and GW, respectively. GRAY nodes are of type GB if at least two of their sons are of type GB; otherwise, they are of type GW. Sequences of approximations using various combinations of locational codes of GB and GW nodes are proposed and shown to be superior to approximation methods based on truncation of nodes below a certain level in the tree. These approximations have two important properties. First, they are progressive in the sense that as more of the image is transmitted, the receiving device can construct a better approximation (contrast with facsimile methods which transmit the image one line at a time). Second, they are proved to lead to compression in the sense that they never require more than MIN(B, W) nodes where B and W correspond to the number of BLACK and WHITE nodes in the original quadtree. Algorithms are given for constructing the approximation sequences as well as decoding them to rebuild the original quadtree.
Nonconstructive tools for proving polynomial-time decidability
Authors: Fellows Michael R. , Langston Michael A.
Published: July 2002

Recent advances in graph theory and graph algorithms dramatically alter the traditional view of concrete complexity theory, in which a decision problem is generally shown to be in P by producing an efficient algorithm to solve an optimization version of the problem. Nonconstructive tools are now available for classifying problems as decidable in polynomial time by guaranteeing only theexistenceof polynomial-timedecisionalgorithms. In this paper these new methods are employed to prove membership in P for a number of problems whose complexities are not otherwise known. Powerful consequences of these techniques are pointed out and their utility is illustrated. A type of partially ordered set that supports this general approach is defined and explored.
Research in music and artificial intelligence
Authors: Roads Curtis
Published: July 2002

Although the boundaries of artificial intelligence (AI) remain elusive, computers can now perform musical tasks that were formerly associated exclusively with naturally intelligent musicians. After a historical note, this paper sermonizes on the need for AI techniques in four areas of musical research: composition, performance, music theory, and digital sound processing. The next part surveys recent work involving AI and music. The discussion concentrates on applications in the four areas of research just mentioned. The final part examines how AI techniques of planning and learning could be used to expand the knowledge base and enrich the behavior of musically intelligent systems.
Pilots of the future: human or computer?
Authors: Chambers Alan B. , Nagel David C.
Published: July 2002

As more and more automation is incorporated in aircraft, the essential question becomes one of autonomy: Should the automated system serve as the human pilot's assistant, or vice versa?
An efficient algorithm for image segmentation, Markov random fields and related problems
Authors: Hochbaum Dorit S.
Published: July 2002

Problems of statistical inference involve the adjustment of sample observations so they fit some a priori rank requirements, or order constraints. In such problems, the objective is to minimize thedeviation costfunction that depends on the distance between the observed value and the modify value. In Markov random field problems, there is also a pairwise relationship between the objects. The objective in Markov random field problem is to minimize the sum of the deviation cost function and a penalty function that grows with the distance between the values of related pairs---separation function.We discuss Markov random fields problems in the context of a representative application---theimage segmentationproblem. In this problem, the goal is to modify color shades assigned to pixels of an image so that the penalty function consisting of one term due to the deviation from the initial color shade and a second term that penalizes differences in assigned values to neighboring pixels is minimized. We present here an algorithm that solves the problem in polynomial time when the deviation function is convex and separation function is linear; and in strongly polynomial time when the deviation cost function is linear, quadratic or piecewise linear convex with few pieces (where “few” means a number exponential in a polynomial function of the number of variables and constraints). The complexity of the algorithm for a problem onnpixels or variables,madjacency relations or constraints, and range of variable values (colors)U, isO(T(n,m) +nlogU) whereT(n,m) is the complexity of solving the minimum s, t cut problem on a graph withnnodes andmarcs. Furthermore, other algorithms are shown to solve the problem with convex deviation and convex separation in running timeO(mnlognlognU) and the problem with nonconvex deviation and convex separation in running timeO(T(nU, mU). The nonconvex separation problem is NP-hard even for fixed value ofU.For the family of problems with convex deviation functions and linear separation function, the algorithm described here runs in polynomial time which is demonstrated to be fastest possible.
Formalizing the safety of Java, the Java virtual machine, and Java card
Authors: Hartel Pieter H. , Moreau Luc
Published: July 2002

We review the existing literature on Java safety, emphasizing formal approaches, and the impact of Java safety on small footprint devices such as smartcards. The conclusion is that although a lot of good work has been done, a more concerted effort is needed to build a coherent set of machine-readable formal models of the whole of Java and its implementation. This is a formidable task but we believe it is essential to build trust in Java safety, and thence to achieve ITSEC level 6 or Common Criteria level 7 certification for Java programs.
Predicting how ontologies for the semantic web will evolve
Authors: Kim Henry
Published: July 2002

The first phase in the evolution of the semantic Web may be the development of decentralized, adaptive ontologies for software specification.
A nested transaction model for multilevel secure database management systems
Authors: Bertino Elisa , Catania Barbara , Ferrari Elena
Published: July 2002

This article presents an approach to concurrency control for transactions in a Multilevel Secure Database Management System (MLS/DBMS). The major problem is that concurrency control mechanisms used in traditional DBMSs are not adequate in a MLS/DBMS, since they may be exploited to establish covert channels. The approach presented in this article, which uses single-version data items, is based on the use of nested transactions, application-level recovery, and notification-based locking protocols. All these features allow us to develop a concurrency control mechanism that is free of timing channels and avoids many of the shortcomings of the concurrency control mechanisms so far developed for conventional (i.e., flat) transactions, such as transaction starvation and resource wastage.
Algorithm 815
Authors: Festa Paola , Pardalos Panos M. , Resende Mauricio G. C.
Published: July 2002

We propose FORTRAN subroutines for approximately solving the feedback vertex and arc set problems on directed graphs using a Greedy Randomized Adaptive Search Procedure (GRASP). Implementation and usage of the package is outlined and computational experiments are reported illustrating solution quality as a function of running time.
The economical method for generating random samples from discrete distributions
Authors: Deak I.
Published: July 2002

The idea of the economical method is applied for generating samples from any discrete distribution. In the resulting procedure, the expected number of uniformly distributed random numbers is less than in the alias method (practically 1). A refinement gives a version where in limit just one uniformly distributed number is required at the expense of some storage space.
The Alpine file system
Authors: Brown M. R. , Kolling K. N. , Taft E. A.
Published: July 2002

Alpine is a file system that supports atomic transactions and is designed to operate as a service on a computer network. Alpine's primary purpose is to store files that represent databases. An important secondary goal is to store ordinary files representing documents, program modules, and the like.

Unlike other file servers described in the literature, Alpine uses a log-based technique to implement atomic file update. Another unusual aspect of Alpine is that it performs all communication via a general-purpose remote procedure call facility. Both of these decisions have worked out well. This paper describes Alpine's design and implementation, and evaluates the system in light of our experience to date.

Alpine is written in Cedar, a strongly typed modular programming language that includes garbage-collected storage. We report on using the Cedar language and programming environment to develop Alpine.
Error detecting decimal digits
Authors: Putter Paul , Wagner Neal R.
Published: July 2002

Decimal-oriented error detection schemes are explored in the context of one particular company project.
High level knowledge sources in usable speech recognition systems
Authors: Young S. L. , Hauptmann A. G. , Ward W. H. , Smith E. T. , Werner P.
Published: July 2002

The authors detail an integrated system which combines natural language processing with speech understanding in the context of a problem solving dialogue. The MINDS system uses a variety of pragmatic knowledge sources to dynamically generate expectations of what a user is likely to say.
Life before the chips: simulating digital video interactive technology
Authors: Dixon Douglas
Published: July 2002

Advances in computers, such as DVI technology, are driven by new hardware functionality—more magic in the silicon. But before the chips came the ideas, and years of visual and interactive technical simulations to evaluate product designs and build the support necessary to develop them.
ER model clustering as an aid for user communication and documentation in database design
Authors: Teorey Toby J. , Wei Guangping , Bolton Deborah L. , Koenig John A.
Published: July 2002

Entity-relationship clustering promotes the simplicity that is vital for fast end-user comprehension, as well as the complexity at a more detailed level to satisfy the database designer's need for extended semantic expression in the conceptual model.
The effect of a priori views on the social implications of computing: the case of office automation
Authors: Hirschheim R. A.
Published: July 2002

Office automation impact has received considerable attention in the literature recently. Unfortunately, that which has appeared is diverse and contradictory. The relevant literature is reviewed, summarized, and placed in a framework containing three positions on office automation impact: optimism, pessimism, and relativism. The basic assumptions and empirical support for each position are noted and analyzed. It is proposed that these positions are based on a number of a priori views which guide the reporting and beliefs about technological impact.
Self-assessment procedure XX
Authors: Rosenberg J. , Ananda A. L. , Srinivasan B.
Published: July 2002

A self-assessment procedure on operating systems
Distributed bisimulations
Authors: Castellani Ilaria , Hennessy Matthew
Published: July 2002

A new equivalence between concurrent processes is proposed. It generalizes the well-known bisimulation equivalence to take into account the distributed nature of processes. The result is a noninterleaving semantic theory; concurrent processes are differentiated from processes that are non-deterministic but sequential. The new equivalence, together with its observational version, is investigated for a subset of the language CCS, and various algebraic characterizations are obtained.
Entity-life modeling and structured analysis in real-time software design—a comparison
Authors: Sanden Bo
Published: July 2002

While structure analysis is sometimes used as a first step towards a real-time software design with concurrent tasks, a more appropriate task structure can often be based directly on concurrent patterns in the problem environment.
Query processing techniques in the summary-table-by-example database query language
Authors: Özsoyoğlu Gultekin , Matos Victor , Özsoyoğlu Meral
Published: July 2002

Summary-Table-by-Example (STBE) is a graphical language suitable for statistical database applications. STBE queries have a hierarchical subquery structure and manipulate summary tables and relations with set-valued attributes.

The hierarchical arrangement of STBE queries naturally implies a tuple-by-tuple subquery evaluation strategy (similar to the nested loops join implementation technique) which may not be the best query processing strategy. In this paper we discuss the query processing techniques used in STBE. We first convert an STBE query into an “extended” relational algebra (ERA) expression. Two transformations are introduced to remove the hierarchical arrangement of subqueries so that query optimization is possible. To solve the “empty partition” problem of aggregate function evaluation, directional join (one-sided outer-join) is utilized. We give the algebraic properties of the ERA operators to obtain an “improved” ERA expression. Finally we briefly discuss the generation of alternative implementations of a given ERA expression.

STBE is implemented in a prototype statistical database management system. We discuss the STBE-related features of the implemented system.
Automatically generating visual syntax-directed editors
Authors: Arefi Farah , Hughes Charles E. , Workman David A.
Published: July 2002

Since inexpensive computers possessing sophisticated graphics were introduced in the late 1970s, program development research has focused on syntax-directed editors that are based on the grammars of their underlying languages. The system presented here automatically generates object-oriented, syntax-directed editors for visual languages, which are described by a family of editing operations.
Partially shared views: a scheme for communicating among groups that use different type hierarchies
Authors: Lee Jintae , Malone Thomas W.
Published: July 2002

Many computer systems are based on various types of messages, forms, or other objects. When users of such systems need to communicate with people who use different object types, some kind of translation is necessary. In this paper, we explore the space of general solutions to this translation problem and propose a scheme that synthesizes these solutions. After first illustrating the problem in the Object Lens system, we identify two partly conflicting objectives that any translation scheme should satisfy: preservation of meaning and autonomous evolution of group languages. Then we partition the space of possible solutions to this problem in terms of the set theoretic relations between group languages and a common language. This leads to five primary solution classes and we illustrate and evaluate each one. Finally, we describe a composite scheme, called Partially Shared Views, that combines many of the best features of the other schemes. A key insight of the analysis is that partially shared type hierarchies allow “foreign” object types to be automatically translated into their nearest common “ancestor” types. The partial interoperability attained in this way makes possible flexible standards from which people can benefit from whatever agreements they do have without having to agree on everything. Even though our examples deal primarily with extensions to the Object Lens system, the analysis also suggests how other kinds of systems, such as EDI applications, might exploit specialization hierarchies of object types to simplify the translation problem.
A transient hypergraph-based model for data access
Authors: Watters Carolyn , Shepherd Michael A.
Published: July 2002

Two major methods of accessing data in current database systems are querying and browsing. The more traditional query method returns an answer set that may consist of data values (DBMS), items containing the answer (full text), or items referring the user to items containing the answer (bibliographic). Browsing within a database, as best exemplified by hypertext systems, consists of viewing a database item and linking to related items on the basis of some attribute or attribute value.

A model of data access has been developed that supports both query and browse access methods. The model is based on hypergraph representation of data instances. The hyperedges and nodes are manipulated through a set of operators to compose new nodes and to instantiate new links dynamically, resulting in transient hypergraphs. These transient hypergraphs are virtual structures created in response to user queries, and lasting only as long as the query session. The model provides a framework for general data access that accommodates user-directed browsing and querying, as well as traditional models of information and data retrieval, such as the Boolean, vector space, and probabilistic models. Finally, the relational database model is shown to provide a reasonable platform for the implementation of this transient hypergraph-based model of data access.
New techniques for best-match retrieval
Authors: Shasha Dennis , Wang Tsong-Li
Published: July 2002

A scheme to answer best-match queries from a file containing a collection of objects is described. A best-match query is to find the objects in the file that are closest (according to some (dis)similarity measure) to a given target.

Previous work [5, 331] suggests that one can reduce the number of comparisons required to achieve the desired results using the triangle inequality, starting with a data structure for the file that reflects some precomputed intrafile distances. We generalize the technique to allow the optimum use of any given set of precomputed intrafile distances. Some empirical results are presented which illustrate the effectiveness of our scheme, and its performance relative to previous algorithms.