bluuebunny/crossref_metadata_2025 huggingface dataset:
A methodology and algorithms for the design of hard real-time multitasking ASICs
Authors: Potkonjak Miodrag , Wolf Wayne
Published: July 2002

Traditional high-level synthesis concentrates on the implementation of a single task (e.g. filter, linear controller, A/D converter). However, many applications—multifunctional embedded controllers intelligent wireless end-points, and DSP and multimedia servers—are defined as sets of several computational tasks. This paper describes new techniques for the synthesis of ASIC implementations that realize multiple computational processes under hard real-time constraints. Our synthesis methodology establishes connections between two important comengineering domains: operating systems and behavioral synthesis. Our hierarchical approach starts from an incompletely-specified preliminary solution and uses, interchangeably, operating system and behavioral synthesis techniques to derive increasingly more detailed and accurate design solutions. We have experimented with both optimal and heuristic algorithms to implement this methodology. The optimal algorithm uses several heuristics to speed up the average run time of an exhaustive branch-and-bound search. Force-directed optimization is the core of the heuristic synthesis method. Analysis of the proposed algorithms and the experiments shows that matching the number of bits and type of operational in taskes assigned to the same application-specific processor was the most important factor in obtaining area-efficient designs.
Security of random data perturbation methods
Authors: Muralidhar Krishnamurty , Sarathy Rathindra
Published: July 2002

Statistical databases often use random data perturbation (RDP) methods to protect against disclosure of confidential numerical attributes. One of the key requirements of RDP methods is that they provide the appropriate level of security against snoopers who attempt to obtain information on confidential attributes through statistical inference. In this study, we evaluate the security provided by three methods of perturbation. The results of this study allow the database administrator to select the most effective RDP method that assures adequate protection against disclosure of confidential information.
Automating parallel simulation using parallel time streams
Authors: Yau Victor
Published: July 2002

This paper describes a package for parallel steady-state stochastic simulation that was designed to overcome problems caused by long simulation times experienced in our ongoing research in performance evaluation of high-speed and integrated-services communication networks, while maintaining basic statistical rigors of proper analysis of simulation output data. The package, named AKAROA, accepts ordinary (nonparallel) simulation programs, and alll further stages of stochastic simulation should be transparent for users. The package employs a new method of sequential estimation for the Multiple-Replications-in-Parallel scenario. All basic functions, including the transformation of originally nonparallel simulators into ones suitable for parallel execution, control of the precision of estimates, and stopping of parallel simulation processes when the required precision of the overall steady-state estimates is achieved, are automated. The package can be used on multiprocessor systems and/or heterogeneous computer networks, involving an arbitrary number of processors. The design issues, architecture, and implementation of AKAROA, as well as the results of its preliminary performance studies are presented
Behavioral equivalence in the polymorphic pi-calculus
Authors: Pierce Benjamin C. , Sangiorgi Davide
Published: July 2002

We investigateparametric polymorphismin message-based concurrent programming, focusing on behavioral equivalences in a typed process calculus analogous to the polymorphic lambda-calculus of Girard and Reynolds.

Polymorphism constrains the power of observers by preventing them from directly manipulating data values whose types are abstract, leading to notions of equivalence much coarser than the standard untyped ones. We study the nature of these constraints through simple examples of concurrent abstract data types and develop basic theoretical machinery for establishing bisimilarity of polymorphic processes.

We also observe some surprising interactions between polymorphism and aliasing, drawing examples from both the polymorphic pi-calculus and ML.
Algorithm 464: eigenvalues of a real, symmetric, tridiagonal matrix [F2]
Authors: Reinsch Christian H.
Published: July 2002

This algorithm uses a rational variant of the QR transformation with explicit shift for the computation of all of the eigenvalues of a real, symmetric, and tridiagonal matrix. Details are described in [1]. Procedures
tred
1 or
tred
3 published in [2] may be used to reduce any real, symmetric matrix to tridiagonal form. Turn the matrix end-for-end if necessary to bring very large entries to the bottom right-hand corner.
Talking to UNIX in English
Authors: Wilensky Robert , Arens Yigal , Chin David
Published: July 2002

UC is a natural language help facility which advises users in using the UNIX operating system. Users can query UC about how to do things, command names and formats, online definitions of UNIX or general operating systems terminology, and debugging problems in using commands. UC is comprised of the following components: a language analyzer and generator, a context and memory model, an experimental common-sense planner, highly extensible knowledge bases on both the UNIX domain and the English language, a goal analysis component, and a system for acquisition of new knowledge through instruction in English. The language interface of UC is based on a “phrasal analysis” approach which integrates semantic, grammatical and other types of information. In addition, it includes capabilities for ellipsis resolution and reference disambiguation.
Anomalies in parallel branch-and-bound algorithms
Authors: Lai Ten-Hwang , Sahni Sartaj
Published: July 2002

We consider the effects of parallelizing branch-and-bound algorithms by expanding several live nodes simultaneously. It is shown that it is quite possible for a parallel branch-and-bound algorithm using n
2
processors to take more time than one using n
1
processors, even though n
1
<
n
2
.
Furthermore, it is also possible to achieve speed-ups that are in excess of the ratio n
2
/
n
1
.
Experimental results with the 0
/
1-Knapsack and Traveling Salesman problems are also presented.
A comparison of two network-based file servers
Authors: Mitchell James G. , Dion Jeremy
Published: July 2002

This paper compares two working network-based file servers, the Xerox Distributed File System (XDFS) implemented at the Xerox Palo Alto Research Center, and the Cambridge File Server (CFS) implemented at the Cambridge University Computer Laboratory. Both servers support concurrent random access to files using atomic transactions, both are connected to local area networks, and both have been in service long enough to enable us to draw lessons from them for future file servers.

We compare the servers in terms of design goals, implementation issues, performance, and their relative successes and failures, and discuss what we would do differently next time.
A correctness proof of a topology information maintenance protocol for a distributed computer network
Authors: Tajibnapis William D.
Published: July 2002

In order for the nodes of a distributed computer network to communicate, each node must have information about the network's topology. Since nodes and links sometimes crash, a scheme is needed to update this information. One of the major constraints on such a topology information scheme is that it may not involve a central controller. The Topology Information Protocol that was implemented on the MERIT Computer Network is presented and explained; this protocol is quite general and could be implemented on any computer network. It is based on Baran's “Hot Potato Heuristic Routing Doctrine.” A correctness proof of this Topology Information Protocol is also presented.
A strategic planning methodology for the computing effort in higher education
Authors: Wetherbe James C. , Dock V. Thomas
Published: July 2002

The findings of a study designed to address the pressing problems associated with the strategic planning of the computing effort in higher education are presented here. A planning methodology was developed and tested through implementation at a university. Two years after the methodology was implemented, the effectiveness of the planning methodology was assessed in terms of the improvement of the delivery of computing services to the major institutional roles of instruction, research, and administration. Two control institutions were employed to contrast the improvements at the test institution. The results of the research indicate the planning methodology significantly enhanced the delivery of computing services.
The status of women and minorities in academic computer science
Authors: Montanelli Richard G. , Mamrak Sandra A.
Published: July 2002

The results of a survey concerning women and minority students and faculty in computer science during the years 1971 to 1975 are presented. Analysis of the data indicated that effective affirmative action programs for recruitment into graduate degree programs are needed to enlarge the number of women and minorities qualified for later employment in computer science. Also, possible discrimination in employment of women and minority graduate students was revealed.
On shrinking binary picture patterns
Authors: Levialdi S.
Published: July 2002

A parallel processing algorithm for shrinking binary patterns to obtain single isolated elements, one for each pattern, is presented. This procedure may be used for counting patterns on a matrix, and a hardware implementation of the algorithm using large scale integrated tecnology is envisioned. The principal features of this method are the very small window employed (two-by-two elements), the parallel nature of the process, and the possibility of shrinking any pattern, regardless of the complexity of its configuration. Problems regarding merging and disconnection of patterns during the process as well as the determination of the maximum number of steps necessary to obtain a single isolated element from a pattern, are reviewed and discussed. An analogy with a neural network description, in terms of McCulloch-pitts “neurons” is presented.
The use of grammatical inference for designing programming languages
Authors: Crespi-Reghizzi S. , Melkanoff M. A. , Lichten L.
Published: July 2002

Both in designing a new programming language and in extending an existing language, the designer is faced with the problem of deriving a “natural” grammar for the language. We are proposing an interactive approach to the grammar design problem wherein the designer presents a sample of sentences and structures as input to a grammatical inference algorithm. The algorithm then constructs a grammar which is a reasonable generalization of the examples submitted by the designer. The implemention is presently restricted to a subclass of operator precedence grammars, but a second algorithm is outlined which applies to a larger class of context-free grammars.
On the use of self-similar processes in network simulation
Authors: López-Ardao José C. , López-García Cándido , Suárez-González Andrés , Fernández-Veiga Manuel , Rodríguez-Rubio Raúl
Published: July 2002

Several recent traffic measurement studies have convincingly shown the presence of self-similarity in modern high-speed networks, involving a very important revolution in the stochastic modeling of traffic. Thus the use of self-similar processes has opened new problems and research fields in network performance analysis, mainly in simulation studies, where the efficient synthetic generation of sample paths (traces) corresponding to self-similar traffic is one of the main topics. In this article, we justify the selection of interarrival time instead of counting processes for modeling arrivals. Also, we discuss the advantages and drawbacks of the most important self-similar processes when applied to traffic modeling in simulation studies, proposing the use of models based in F-ARIMA, mainly due to their flexibility to capture both long- and short-range correlations. However, F-ARIMA processes have been little used in simulation studies, mainly because the synthetic generation methods available in the literature are very inefficient compared with those for FGN. In order to solve this problem, we propose a new method that can generate high-quality traces corresponding to a F-ARIMA(p, d, q) process. A comparison with existing methods shows that the new method is significantly more efficient, and even slightly better than the best method for FGN.
Syntax-directed interpretation of classes of pictures
Authors: Narasimhan R.
Published: July 2002

A descriptive scheme for classes of pictures based on labeling techniques using parallel processing algorithms was proposed by the author some years ago. Since then much work has been done in applying this to bubble chamber pictures. The parallel processing simulator, originally written for an IBM 7094 system, has now been rewritten for a CDC 3600 system. This paper describes briefly the structure of syntactic descriptive models by considering their specific application to bubble chamber pictures. How the description generated in this phase can be embedded in a larger “conversation” program is explained by means of a certain specific example that has been worked out. A partial generative grammar for “handwritten” English letters is given, as are also a few computer-generated outputs using this grammar and the parallel processing simulator mentioned earlier.
Eliminating monotonous mathematics with FORMAC
Authors: Tobey Robert G.
Published: July 2002

The FORMAC (FORmula MAnipulation Compiler) programming system provides a powerful tool for performing mathematical analysis. It is an extension of FORTRAN IV which permits the use of the computer to perform the tedious algebraic computations that arise in many different fields. Among the areas in which it has been successfully used are: differentiation of complicated expressions; expansion of truncated power series, solution of simultaneous equations with literal coefficients, nonlinear maximum likelihood estimation, tensor analysis, and generation of the coefficients of equations in Keplerian motion. These types of analysis—which arose in the solution of specific practical problems in physics, engineering, astronomy, statistics and astronautics—are discussed in the paper.

In addition to its usage for specific problem solutions, FORMAC can also be used to automate the analysis phase in certain production programming. Several such applications are presented.
A semi-automatic storage allocation system at loading time
Authors: Heising William P. , Larner Ray A.
Published: July 2002

The method of storage allocation described herein, although new in a few respects, does not represent any sharp break from the past. Rather it is another step of development suggested by experience accumulated over several years with the 704,709 and 7090 FORTRAN systems. The storage assignment method proposed is, in principle, extremely simple and is not specific to FORTRAN or the 7090. Although the method depends only on rather general language aspects, the concrete detail will be illustrated in terms of the aforementioned systems or proposed extensions.
Separating access control policy, enforcement, and functionality in extensible systems
Authors: Grimm Robert , Bershad Brian N.
Published: July 2002

Extensible systems, such as Java or the SPIN extensible operating system, allow for units of code, or extensions, to be added to a running system in almost arbitrary fashion. Extensions closely interact through low-latency but type-safe interfaces to form a tightly integrated system. As extensions can come from arbitrary sources, not all of whom can be trusted to conform to an organization's security policy, such structuring raises the question of how security constraints are enforced in an extensible system. In this paper, we present an access control mechanism for extensible systems to address this problem. Our access control mechanism decomposes access control into a policy-neutral enforcement manager and a security policy manager, and it is transparent to extensions in the absence of security violations. It structures the system into protection domains, enforces protection domains through access control checks, and performs auditing of system operations. The access control mechanism works by inspecting extensions for their types and operations to determine which abstractions require protection and by redirecting procedure or method invocations to inject access control operations into the system. We describe the design of this access control mechanism, present an implementation within the SPIN extensible operating systems, and provide a qualitative as well as quantitative evaluation of the mechanism.
The character, value, and management of personal paper archives
Authors: Whittaker Steve , Hirschberg Julia
Published: July 2002

We explored general issues concerning personal information management by investigating the characteristics of office workers' paper-based information, in an industrial research environment. we examined the reasons people collect paper, types of data they collect, problems encountered in handling paper, and strategies used for processing it. We tested three specific hypotheses in the course of an office move. The greater availability of public digital data along with changes in people's jobs or interests should lead to wholescale discarding of paper data, while preparing for the move. Instead we found workers kept large, highly valued papar archives. We also expected that the major part of people's personal archives would be unique documents. However, only 49% of people's archives were unique documents, the remainder being copies of publicly available data and unread information, and we explore reasons for this. We examined the effects of paper-processing strategies on archive structure. We discovered different paper-processing strategies (filingandpiling)that were relatively independent of job type. We predicated that filers' attempted to evaluate and catergorize incoming documents would produce smaller archives that were accessed frequently. Contrary to our predictions, filers amassed more information, and accessed it less frequently than pilers. We argue that filers may engage inpremature filing: to clear their workspace, they archives information that later turns out to be of low value. Given the effort involved in organzing data, they are also loath to discard filed information, even when its value is uncertain. We discuss the implications of this research for digital personal information management.
The complexity of propositional linear temporal logics
Authors: Sistla A. P. , Clarke E. M.
Published: July 2002

The complexity of satisfiability and determination of truth in a particular finite structure are considered for different propositional linear temporal logics. It is shown that these problems are NP-complete for the logic with F and are PSPACE-complete for the logics with F, X, with U, with U, S, X operators and for the extended logic with regular operators given by Wolper.
Query-based sampling of text databases
Authors: Callan Jamie , Connell Margaret
Published: July 2002

The proliferation of searchable text databases on corporate networks and the Internet causes a database selection problem for many people. Algorithms such as gGLOSS and CORI can automatically select which text databases to search for a given information need, but only if given a set of resource descriptions that accurately represent the contents of each database. The existing techniques for a acquiring resource descriptions have significant limitations when used in wide-area networks controlled by many parties. This paper presents
query-based sampling
, a new technicque for acquiring accurate resource descriptions. Query-based sampling does not require the cooperation of resource providers, nor does it require that resource providers use a particular search engine or representation technique. An extensive set of experimental results demonstrates that accurate resource descriptions are crated, that computation and communication costs are reasonable, and that the resource descriptions do in fact enable accurate automatic dtabase selection.
Efficient list-approximation techniques for floorplan area minimization
Authors: Hu Xiaobo Sharon , Chen Danny Z. , Sambandam Rajeshkumar
Published: July 2002

As the sizes of many IC design problems become increasingly larger,
approximation has become a valuable approach for arriving at satisfactory results without incurring exorbitant computational cost. In this paper, we present several approximation techniques for solving
floorplan area minimization
problems. These new techniques enable us to reduce both the time and space complexities of the previously best known approximation algorithms by more than a factor of
n
and
n
2
for rectangular and L-shaped subfloorplans, respectively (where
n
is the number of given implementions). The improvements in the time and space complexities of such approximation techniques is critical to their applicability in floorplan area minimization algorithms. The techniques are quite general, and may be applicable to other classes of approximation problems.
3D RGB image compression for interactive applications
Authors: Bajaj Chandrajit , Ihm Insung , Park Sanghun
Published: July 2002

This paper presents a new 3D RGB image compression scheme designed for interactive real-time applications. In designing our compression method, we have compromised between two important goals: high compression ratio and fast random access ability, and have tried to minimize the overhead caused during run-time reconstruction. Our compression technique is suitable for applications wherein data are accessed in a somewhat unpredictable fashion, and real-time performance of decompression is necessary. The experimental results on three different kinds of 3D images from medical imaging, image-based rendering, and solid texture mapping suggest that the compression method can be used effectively in developing real-time applications that must handle large volume data, made of color samples taken in three- or higher-dimensional space.
Semantics of query languages for network databases
Authors: Subieta Kazimierz
Published: July 2002

Semantics determines the meaning of language constructs; hence it says much more than syntax does about implementing the language. The main purpose of this paper is a formal presentation of the meaning of basic language constructs employed in many database languages (sublanguages). Therefore, stylized query languages SSL (Sample Selection Language) and J (Joins) are introduced, wherein most of the typical entries present in other query languages are collected. The semantics of SSL and J are defined by means of the denotational method and explained informally. In SSL and J, four types of expressions are introduced: a selector (denotes a set of addresses), a term (denotes a set of values), a formula (denotes a truth value), and a join (denotes a set of n-tuples of addresses or values). In many cases alternative semantics are given and discussed. In order to obtain more general properties of the proposed languages, a new database access model is introduced, intended to be a tool for the description of the logical access paths to data. In particular, the access paths of the network and relational models can be described. SSL and J expressions may be addressed to both data structures. In the case of the relational model, expressions of J are similar to SQL or QUEL statements. Thus J may be considered a generalization of relational query languages for the network model. Finally, a programming language, based on SSL and J, is outlined, and the issues of SSL and J implementation are considered.
A theory of reliability in database systems
Authors: Hadzilacos Vassos
Published: July 2002

Reliable concurrent processing of transactions in a database system is examined. Since serializability, the conventional concurrency control correctness criterion, is not adequate in the presence of common failures, another theory of correctness is proposed, involving the concepts ofcommit serializability, recoverability,andresiliency.
The Cedar file system
Authors: Gifford David K. , Needham Roger M. , Schroeder Michael D.
Published: July 2002

The Cedar File System (CFS) is a workstation file system that provides access to both a workstation's local disk and to remote file servers via a single hierarchical name space. CFS supports a group of cooperating programmers by allowing them to both manage local naming environments and to share consistent versions of collections of software.
Spherical averages and applications to spherical splines and interpolation
Authors: Buss Samuel R. , Fillmore Jay P.
Published: July 2002

This article introduces a method for computing weighted averages on spheres based on least squares minimization that respects spherical distance. We prove existence and uniqueness properties of the weighted averages, and give fast iterative algorithms with linear and quadratic convergence rates. Our methods are appropriate to problems involving averages of spherical data in meteorological, geophysical, and astronomical applications. One simple application is a method for smooth averaging of quaternions, which generalizes Shoemake's spherical linear interpolation.The weighted averages methods allow a novel method of defining Bézier and spline curves on spheres, which provides direct generalization of Bézier and B-spline curves to spherical spline curves. We present a fast algorithm for spline interpolation on spheres. Our spherical splines allow the use of arbitrary knot positions; potential applications of spherical splines include smooth quaternion curves for applications in graphics, animation, robotics, and motion planning.
Searching in high-dimensional spaces
Authors: Böhm Christian , Berchtold Stefan , Keim Daniel A.
Published: July 2002

During the last decade, multimedia databases have become increasingly important in many application areas such as medicine, CAD, geography, and molecular biology. An important research issue in the field of multimedia databases is the content-based retrieval of similar multimedia objects such as images, text, and videos. However, in contrast to searching data in a relational database, a content-based retrieval requires the search of similar objects as a basic functionality of the database system. Most of the approaches addressing similarity search use a so-called feature transformation that transforms important properties of the multimedia objects into high-dimensional points (feature vectors). Thus, the similarity search is transformed into a search of points in the feature space that are close to a given query point in the high-dimensional feature space. Query processing in high-dimensional spaces has therefore been a very active research area over the last few years. A number of new index structures and algorithms have been proposed. It has been shown that the new index structures considerably improve the performance in querying large multimedia databases. Based on recent tutorials [Berchtold and Keim 1998], in this survey we provide an overview of the current state of the art in querying multimedia databases, describing the index structures and algorithms for an efficient query processing in high-dimensional spaces. We identify the problems of processing queries in high-dimensional space, and we provide an overview of the proposed approaches to overcome these problems.
Using model dataflow graphs to reduce the storage requirements of constraints
Authors: Vander Zanden Bradley T. , Halterman Richard
Published: July 2002

Dataflow constraints allow programmers to easily specify relationships among application objects in a natural, declarative manner. Most constraint solvers represent these dataflow relationships as directed edges in a dataflow graph. Unfortunately, dataflow graphs require a great deal of storage. Consequently, an application with a large number of constraints can get pushed into virtual memory, and performance degrades in interactive applications. Our solution is based on the observation that objects derived from the same class use the same constraints, and thus have the same dataflow graphs. We represent the common dataflow patterns in a model dataflow graph that is stored with the class. Instance objects may derive explicit dependencies from this graph when the dependencies are needed. Model dependencies provide a useful new mechanism for improving the storage efficiency of dataflow constraint systems, especially when a large number of constrained objects must be managed.
An algebra for composing access control policies
Authors: Bonatti Piero , De Capitani di Vimercati Sabrina , Samarati Pierangela
Published: July 2002

Despite considerable advancements in the area of access control and authorization languages, current approaches to enforcing access control are all based on monolithic and complete specifications. This assumption is too restrictive when access control restrictions to be enforced come from the combination of different policy specifications, each possibly under the control of independent authorities, and where the specifics of some component policies may not even be known apriori. Turning individual specifications into a coherent policy to be fed into the access control system requires a nontrivial combination and translation process. This article addresses the problem of combining authorization specifications that may be independently stated, possibly in different languages and according to different policies. We propose an algebra of security policies together with its formal semantics and illustrate how to formulate complex policies in the algebra and reason about them. A translation of policy expressions into equivalent logic programs is illustrated, which provides the basis for the implementation of the algebra. The algebra's expressiveness is analyzed through a comparison with first-order logic.
Minimizing function-free recursive inference rules
Authors: Naughton Jeffrey F.
Published: July 2002

Recursive inference rules arise in recursive definitions in logic programming systems and in database systems with recursive query languages. LetDbe a recursive definition of a relationt.Dis consideredminimalif for any predicatepin a recursive rule inD,pmust appear in a recursive rule in any definition oft. It is shown that testing for minimality is, in general, undecidable. However, an efficient algorithm for a useful class of recursive rules is presented, and it is used to transform a recursive definition to a minimal recursive definition. Evaluating the minimized definition avoids redundant computation without the overhead of caching intermediate results and run-time checking for duplicate goals.
Cache coherence protocols: evaluation using a multiprocessor simulation model
Authors: Archibald James , Baer Jean-Loup
Published: July 2002

Using simulation, we examine the efficiency of several distributed, hardware-based solutions to the cache coherence problem in shared-bus multiprocessors. For each of the approaches, the associated protocol is outlined. The simulation model is described, and results from that model are presented. The magnitude of the potential performance difference between the various approaches indicates that the choice of coherence solution is very important in the design of an efficient shared-bus multiprocessor, since it may limit the number of processors in the system.
Cactis: a self-adaptive, concurrent implementation of an object-oriented database management system
Authors: Hudson Scott E. , King Roger
Published: July 2002

Cactis is an object-oriented, multiuser DBMS developed at the University of Colorado. The system supports functionally-defined data and uses techniques based on attributed graphs to optimize the maintenance of functionally-defined data. The implementation is self-adaptive in that the physical organization and the update algorithms dynamically change in order to reduce disk access. The system is also concurrent. At any given time there are some number of computations that must be performed to bring the database up to date; these computations are scheduled independently and are performed when the expected cost to do so is minimal. The DBMS runs in the Unix/C Sun workstation environment. Cactis is designed to support applications that require rich data modeling capabilities and the ability to specify functionally-defined data, but that also demand good performance. Specifically, Cactis is intended for use in the support of such applications as VLSI and PCB design, and software environments.
Analysis of a composite performance reliability measure for fault-tolerant systems
Authors: Donatiello Lorenzo , Iyer Balakrishna R.
Published: July 2002

Today's concomitant needs for higher computing power and reliability has increased the relevance of multiple-processor fault-tolerant systems. Multiple functional units improve the raw performance (throughput, response time, etc.) of the system, and, as units fail, the system may continue to function albeit with degraded performance. Such systems and other fault-tolerant systems are not adequately characterized by separate performance and reliability measures. A composite measure for the performance and reliability of a fault-tolerant system observed over a finite mission time is analyzed. A Markov chain model is used for system state-space representation, and transient analysis is performed to obtain closed-form solutions for the density and moments of the composite measure. Only failures that cannot be repaired until the end of the mission are modeled. The time spent in a specific system configuration is assumed to be large enough to permit the use of a hierarchical model and static measures to quantify the performance of the system in individual configurations. For a multiple-processor system, where performance measures are usually associated with and aggregated over many jobs, this is tantamount to assuming that the time to process a job is much smaller than the time between failures. An extension of the results to general acyclic Markov chain models is included.
A transaction-based approach to relational database specification
Authors: Abiteboul Serge , Vianu Victor
Published: July 2002

An operational approach to database specification is proposed and investigated. Valid database states are described as the states resulting from the application of admissible transactions, specified by atransactional schema. The approach is similar in spirit to the modeling of behavior by methods and encapsulation in object-oriented systems. The transactions considered are line programs consisting of insertions, deletions, and modifications, using simple selection conditions. The results concern basic properties of transactional schemas, as well as the connection with traditional constraint schemas. In particular, the expressive power of transactional schemas is characterized. Although it is shown that transaction-based specification and constraint-based specification are incomparable, constraints of practical interest that have corresponding transactional schemas are identified. The preservation of constraints by transactions is also studied.
The conjecture of Fliess on commutative context-free languages
Authors: Kortelainen Juha
Published: July 2002

The conjecture of Fliess concerning commutative context-free languages is disproved using a counterexample.
An AI-based approach to machine translation in Indian languages
Authors: Raman Subramanian , Alwar Narayanan
Published: July 2002

Primarily illustrated as an approach to translate the Indian languages, a focus on AI techniques for building semantic representational structures of sentences is presented.
Steady-state simulation of queueing processes: survey of problems and solutions
Authors: Pawlikowski Krzysztof
Published: July 2002

For years computer-based stochastic simulation has been a commonly used tool in the performance evaluation of various systems. Unfortunately, the results of simulation studies quite often have little credibility, since they are presented without regard to their random nature and the need for proper statistical analysis of simulation output data.

This paper discusses the main factors that can affect the accuracy of stochastic simulations designed to give insight into the steady-state behavior of queuing processes. The problems of correctly starting and stopping such simulation experiments to obtain the required statistical accuracy of the results are addressed. In this survey of possible solutions, the emphasis is put on possible applications in the sequential analysis of output data, which adaptively decides about continuing a simulation experiment until the required accuracy of results is reached. A suitable solution for deciding upon the starting point of a steady-state analysis and two techniques for obtaining the final simulation results to a required level of accuracy are presented, together with pseudocode implementations.
The politics of standards and the EC
Authors: Frenkel Karen A.
Published: July 2002

European legislation and power struggles in the standards arena are sparking fear of technical barriers to trade and prompting the American standards community to reevaluate its infrastructure. The National Institute of Standards and Technology may step up its role in order to negotiate at a governmental level with the EC.
Finding boundaries of the domain of definition for functions along a one-dimensional ray
Authors: Shacham Orit , Schacham Mordechai
Published: July 2002

A program for finding boundaries of function domains along a one-dimensional ray has been developed. The program decomposes the function into subexpressions which are recursively tested for intervals where they are undefined, negative, or fractional, or points where they equal zero. The intervals in which the subexpressions are undefined are then united to create the boundaries of the domain of definition of the whole function. The advantages of the use of such a program in solution of systems of nonlinear algebraic equations and nonlinear optimization are demonstrated.
From Washington: EC directives aim for market harmony
Authors: Crawford Diane
Published: July 2002

The 1992 unification plans for the 12-nation European Community (EC) have surely been among the most dissected blueprints of the year. Politicians ponder trade agreements, economists refigure potential revenues, and media attention is unrelenting. Absorbing it all are those U.S. high tech industries hoping to make a lasting impression on what the economists, politicians and media all predict will be a $4 trillion market of over 300 million consumers.

Harmony has become the slogan adopted for the project. The EC Commission has spent the past five years identifying and implementing a program of close to 300 directives and regulations that would allow for the free movement of consumer products within the community. The goal of these directives, in addition to promoting European commerce and fair business competition, is to eliminate possible physical, technical or fiscal trade barriers. The result, they hope, is one harmonious marketplace.

Watching every note of this orchestration has been the U.S. Department of Commerce (DoC). Working with an internal program that includes the participation of senior officials from the International Trade Administration, the DoC has examined over 185 of the adopted or proposed directives issued by the EC Commission. Moreover, it consulted with trade associations and industry representatives to explore how these directives relate to current U.S. business practices and determine how they might affect future EC business dealings.

The DoC has published the results of its analyses in a three-volume series that examines directives for a rainbow of products and businesses. The recently released EC 1992: A Commerce Department Analysis of European Directives, Volume 3 features the Department's final roundup of EC Directives—primarily those stipulating technical requirements, nine of which pertain to computers and telecommunications.

Much attention has focused on how the high tech industries, particularly computers, software, telecommunications, and information technology, will be affected by EC standards, certification and testing issues. (See Communications, April 1990 and July 1990). According to Myles Denny-Brown, an international economist and coordinator for EC 92 activities for information technology industries at the DoC, the high tech industry regards EC market potential with cautious optimism. “I believe (industry) feels there is the possibility for some real liberalization there,” he says. “But there is also the possibility of some restrictiveness.”

Denny-Brown points out that standards and procurement issues are particularly important to build a competitive environment that would allow market growth to really take off the way it should. (see sidebar)
A correction of the termination conditions of the Henschen-Naqvi technique
Authors: Briggs David A.
Published: July 2002

Henschen and Naqvi described a technique for translating queries on recursively defined relations of a Datalog database into iterative programs that invoke a query processor for conventional select-project-join queries of the relational algebra. Although the technique has been cited as one of the most efficient available, it will in some cases fail to produce all answers defined by the usual semantics for such databases. The technique is reviewed, a recursive query is exhibited where it fails, the cause of failure is noted, and a correction is described. A graphical representation of the computation based on a formal representation of rule expansions is employed.
The representation of multistage interconnection networks in queuing models of parallel systems
Authors: Harrison Peter G.
Published: July 2002

A major component of a parallel machine is its interconnection network (IN), which provides concurrent communication between the processing elements. It is common to use a multistage interconnection network (MIN) that is constructed using crossbar switches and introduces contention not only for destination addresses but also for internal links. Both types of contention are increased when nonlocal communication across a MIN becomes concentrated on a certain destination address, the
hot-spot
. This paper considers analytical models of asynchronous, circuit-switched INs in which partial paths are held during path building, beginning with a single crossbar and extending recursively to MINs. Since a path must be held between source and destination processors before data can be transmitted, switching networks are passive resources and queuing networks that include them do not therefore have product-form solutions. Using decomposition techniques, the flow-equivalent server (FES) that represents a bank of devices transmitting through a switching network is determined, under mild approximating assumptions. In the case of a full crossbar, the FES can be solved directly and the result can be applied recursively to model the MIN. Two cases are considered: one in which there is uniform routing and the other where there is a hot-spot at one of the output pins. Validation with respect to simulation for MINs with up to six stages (64-way switching) indicated a high degree of accuracy in the models.
LANGUAGE AND SPACE
Authors: Levinson Stephen C.
Published: July 2002

▪ Abstract  This review describes some recent, unexpected findings concerning variation in spatial language across cultures, and places them in the context of the general anthropology of space on the one hand, and theories of spatial cognition in the cognitive sciences on the other. There has been much concern with the symbolism of space in anthropological writings, but little on concepts of space in practical activities. This neglect of everyday spatial notions may be due to unwitting ethnocentrism, the assumption in Western thinking generally that notions of space are universally of a single kind. Recent work shows that systems of spatial reckoning and description can in fact be quite divergent across cultures, linguistic differences correlating with distinct cognitive tendencies. This unexpected cultural variation raises interesting questions concerning the relation between cultural and linguistic concepts and the biological foundations of cognition. It argues for more sophisticated models relating culture and cognition than we currently have available.
The Anthropology of Colonialism: Culture, History, and the Emergence of Western Governmentality
Authors: Pels Peter
Published: July 2002

The study of colonialism erases the boundaries between anthropology and history or literary studies, and between the postcolonial present and the colonial past. From the standpoint of anthropology, it is also reflexive, addressing the colonial use and formation of ethnography and its supporting practices of travel. Since the 1960s, the study of colonialism has increasingly presented a view of colonialism as struggle and negotiation, analyzing how the dichotomous representations that Westerners use for colonial rule are the outcome of much more murky and complex practical interactions. By thus treating Western governmentality as emergent and particular, it is rewriting our histories of the present.
Histories of Feminist Ethnography
Authors: Visweswaran Kamala
Published: July 2002

This review essay illustrates how changes in the conception of gender define the historical production of feminist ethnography in four distinct periods. In the first period (1880–1920), biological sex was seen to determine social roles, and gender was not seen as separable from sex, though it was beginning to emerge as an analytical category. The second period (1920–1960) marks the separation of sex from gender as sex was increasingly seen as indeterminative of gender roles. In the third period (1960–1980), the distinction between sex and gender was elaborated into the notion of a sex/gender system—the idea that different societies organized brute biological facts into particular gender regimes. By the contemporary period (1980–1996), critiques of “gender essentialism” (the reification of “woman” as a biological or universal category) suggest that the analytical separation between sex and gender is miscast because “sex” is itself a social category.
Mirrors and Windows: Sociocultural Studies of Human-Animal Relationships
Authors: Mullin Molly H.
Published: July 2002

▪ Abstract  Humans' relationships with animals, increasingly the subject of controversy, have long been of interest to those whose primary aim has been the better understanding of humans' relationships with other humans. Since this topic was last reviewed here, human-animal relationships have undergone considerable reexamination, reflecting key trends in the history of social analysis, including concerns with connections between anthropology and colonialism and with the construction of race, class, and gender identities. There have been many attempts to integrate structuralist or symbolic approaches with those focused on environmental, political, and economic dimensions. Human-animal relationships are now much more likely to be considered in dynamic terms, and consequently, there has been much interdisciplinary exchange between anthropologists and historians. Some research directly engages moral and political concerns about animals, but it is likely that sociocultural research on human-animal relationships will continue to be as much, if not more, about humans.