bluuebunny/crossref_metadata_2025 huggingface dataset:
ON QUANTUM NATURE OF BLACK-HOLE SPACETIME: A POSSIBLE NEW SOURCE OF INTENSE RADIATION
Authors: AHLUWALIA D. V.
Published: July 2002

Atoms and the planets acquire their stability from the quantum mechanical incompatibility of the position and momentum measurements. This incompatibility is expressed by the fundamental commutator [x, px]=iℏ, or equivalently, via the Heisenberg's uncertainty principle Δx Δ px~ℏ. A further stability-related phenomenon where the quantum realm plays a dramatic role is the collapse of certain stars into white dwarfs and neutron stars. Here, an intervention of the Pauli exclusion principle, via the fermionic degenerate pressure, stops the gravitational collapse. However, by the neutron-star stage the standard quantum realm runs dry. One is left with the problematic collapse of a black hole. This essay is devoted to a concrete argument on why the black-hole spacetime itself should exhibit a quantum nature. The proposed quantum aspect of spacetime is shown to prevent the general-relativistic dictated problematic collapse. The quantum nature of black-hole spacetime is deciphered from a recent result on the universal equal-area spacing [Formula: see text] for black holes. In one interpretation of the emergent picture, an astrophysical black hole can fluctuate to [Formula: see text] time its classical size, and thus allow radiation and matter to escape to the outside observers. These fluctuations I conjecture provide a new source, perhaps beyond Hawking radiation, of intense radiation from astrophysical black holes and may be the primary source of observed radiation from those galactic cores what carry black hole(s). The presented interpretation may be used as a criterion to choose black holes from black hole candidates.
NUCLEAR MATTER PROPERTIES USING DIFFERENT SETS OF PARAMETERS IN THE GOGNY INTERACTION
Authors: RAMADAN Kh. A. , MANSOUR H. M. M.
Published: July 2002

In the present work we use the finite range density dependent effective Gogny interaction to study the equation of state of polarized nuclear matter. Six sets of the interaction parameters are used and a comparison is made with the calculations of Friedman and Pandharipande using a realistic interaction. One of the parameter sets (D1) gives similar results for the properties of polarized nuclear matter while the other parameter sets (D1S, D250, D260, D280 and D300) yield results which are reasonably comparable with the realistic interaction calculation of Friedman and Pandharipande
NEOCHONDROGENESIS FOR ARTICULAR BONE-CARTILAGE DEFECT: The use of free periosteal graft, porous metal mould and continuous passive motion in a rabbit model
Authors: Chiu K.Y. , Xie J. , Ngai W.K. , Cheah K.S.E. , Kuffner T. , Chow S.P.
Published: July 2002

Full thickness articular bone-cartilage defects were created in the acetabulae of 35 adult rabbits. A double-layered titanium mesh was used in each hip so as to substitute for the bone defect. Free periosteal grafting was then sutured over the mesh, and the hip was subjected to continuous passive motion for 1 week in each rabbit.

Under light microscopy, islands of chondroid tissues were shown to be present from 2 weeks onwards, and the dominant reparative tissue was hyaline-like cartilage after 6 months. The normal degree of metachromasia of the matrix by Safranin-0 staining was achieved in most but not all the specimens that were hyaline-like under the microscope. Analysis of the collagen types synthesised by the grafts revealed a combination of both type II and type I collagens. Immunohistochemical staining showed intense positive staining around the chondrocyte lacunae when stained with anti-type II collagen antibodies with the one-year group of rabbits.

Although metachromasia of the matrix and collagen typing suggested that fibrocartilage was formed in addition to the hyaline cartilage, the gross appearance and nature of reparative tissues formed were quite promising. Periosteal grafting over a metallic, non-biological surface that provided the shape of the osseous defect in a massive articular defect was therefore a possible alternative.
The Real Effects of Capital Inflows on Emerging Markets
Authors: Dekle Robert , Hsiao Cheng , Wang Siyan
Published: July 2002

We employ vector autoregression and cointegration estimation to examine the impact of net capital inflows on real exchange rates, output and real interest rates in several East Asian and Latin American economies during the 1990s. We find that increases in net capital inflows leads to appreciations of the real exchange rates in all the countries but have no impact on real output except for Thailand.
MULTI-AGENT MARKET MODELING OF FOREIGN EXCHANGE RATES
Authors: ZIMMERMANN GEORG , NEUNEIER RALPH , GROTHMANN RALPH
Published: July 2002

A market mechanism is basically driven by a superposition of decisions of many agents optimizing their profit. The macroeconomic price dynamic is a consequence of the cumulated excess demand/supply created on this micro level. The behavior analysis of a small number of agents is well understood through the game theory. In case of a large number of agents one may use the limiting case that an individual agent does not have an influence on the market, which allows the aggregation of agents by statistic methods. In contrast to this restriction, we can omit the assumption of an atomic market structure, if we model the market through a multi-agent approach.

The contribution of the mathematical theory of neural networks to the market price formation is mostly seen on the econometric side: neural networks allow the fitting of high dimensional nonlinear dynamic models. Furthermore, in our opinion, there is a close relationship between economics and the modeling ability of neural networks because a neuron can be interpreted as a simple model of decision making. With this in mind, a neural network models the interaction of many decisions and, hence, can be interpreted as the price formation mechanism of a market.
INELASTIC HARD SPHERES WITH RANDOM RESTITUTION COEFFICIENT: A NEW MODEL FOR HEATED GRANULAR FLUIDS
Authors: BARRAT ALAIN , TRIZAC EMMANUEL
Published: July 2002

We consider a vertically shaken granular system interacting elastically with the vibrating boundary, so that the energy injected vertically is transferred to the horizontal degrees of freedom through inter-particle collisions only. This leads to collisions which, once projected onto the horizontal plane, become essentially stochastic and may have an effective restitution coefficient larger than unity. We therefore introduce the model of inelastic hard spheres with random restitution coefficient α (larger or smaller than unity) to describe granular systems heated by vibrations. In the non-equilibrium steady state, we focus in particular on the single particle velocity distribution f(v) in the horizontal plane, and on its deviation from a Maxwellian. We use Molecular Dynamics simulations and Direct Simulation Monte Carlo (DSMC) to show that, depending on the distribution of α, different shapes of f(v) can be obtained, with very different high energy tails. Moreover, the fourth cumulant of the velocity distribution (which quantifies the deviations from Gaussian statistics) is obtained analytically from the Boltzmann equation and successfully tested against the simulations.
QUANTUM WELL LUMINESCENCE FROM METALLIC MONOLAYERS
Authors: HOFFMANN GERMAR , BERNDT RICHARD
Published: July 2002

The emission of visible light is observed from the metallic quantum well system Na on Cu(111) when electrons tunnel from the tip of a scanning tunnelling microscope to an unoccupied state of the sample. Spectral analysis of the emission along with tunnelling spectroscopy is used to show that the emission is comprised of two components. A sharp spectral feature is found to be due to an interband transition between quantum well states of the Na layer. The other component is similar to plasmon-mediated emission observed previously from clean metal surfaces. The results suggest that light emission is a unique local probe of the electronic structure of quantum well systems.
CO-EVOLUTION OF FINITE STATE MACHINES FOR OPTIMIZATION: PROMOTION OF DEVICES WHICH SEARCH GLOBALLY
Authors: FREY CLEMENS
Published: July 2002

In this work a co-evolutionary approach is used in conjunction with Genetic Programming operators in order to find certain transition rules for two-step discrete dynamical systems. This issue is similar to the well-known artificial-ant problem. We seek the dynamic system to produce a trajectory leading from given initial values to a maximum of a given spatial functional.

This problem is recast into the framework of input-output relations for controllers, and the optimization is performed on program trees describing input filters and finite state machines incorporated by these controllers simultaneously. In the context of Genetic Programming there is always a set of test cases which has to be maintained for the evaluation of program trees. These test cases are subject to evolution here, too, so we employ a so-called host-parasitoid model in order to evolve optimizing dynamical systems.

Reinterpreting these systems as algorithms for finding the maximum of a functional under constraints, we have derived a paradigm for the automatic generation of adapted optimization algorithms via optimal control. We provide numerical examples generated by the GP-system MathEvEco. These examples refer to key properties of the resulting strategies and they include statistical evidence showing that for this problem of system identification the co-evolutionary approach is superior to standard Genetic Programming.
Autoepistemic logic
Authors: Marek Wiktor , Truszczyński Mirosław
Published: July 2002

Autoepistemic logic is one of the principal modes of nonmonotonic reasoning. It unifies several other modes of nonmonotonic reasoning and has important application in logic programming. In the paper, a theory of autoepistemic logic is developed. This paper starts with a brief survey of some of the previously known results. Then, the nature of nonmonotonicity is studied by investigating how membership of autoepistemic statements in autoepistemic theories depends on the underlying objective theory. A notion similar to set-theoretic forcing is introduced. Expansions of autoepistemic theories are also investigated. Expansions serve as sets of consequences of an autoepistemic theory and they can also be used to define semantics for logic programs with negation. Theories that have expansions are characterized, and a normal form that allows the description of all expansions of a theory is introduced. Our results imply algorithms to determine whether a theory has a unique expansion. Sufficient conditions (stratification) that imply existence of a unique expansion are discussed. The definition of stratified theories is extended and (under some additional assumptions) efficient algorithms for testing whether a theory is stratified are proposed. The theorem characterizing expansions is applied to two classes of theories, K
1
-theories and ae-programs. In each case, simple hypergraph characterization of expansions of theories from each of these classes is given. Finally, connections with stable model semantics for logic programs with negation is discussed. In particular, it is proven that the problem of existence of stable models is NP-complete.—
Authors' Abstract
Disconnected operation in the Coda File System
Authors: Kistler James J. , Satyanarayanan M.
Published: July 2002

Disconnected operationis a mode of operation that enables a client to continue accessing critical data during temporary failures of a shared data repository. An important, though not exclusive, application of disconnected operation is in supporting portable computers. In this paper, we show that disconnected operation is feasible, efficient and usable by describing its design and implementation in the Coda File System. The central idea behind our work is thatcaching of data, now widely used for performance, can also be exploited to improveavailability.
Transitive closure algorithms based on graph traversal
Authors: Ioannidis Yannis , Ramakrishnan Raghu , Winger Linda
Published: July 2002

Several graph-based algorithms have been proposed in the literature to compute the transitive closure of a directed graph. We develop two new algorithms (Basic_TC and Gobal_DFTC) and compare the performance of their implementations in a disk-based environment with a well-known graph-based algorithm proposed by Schmitz. Our algorithms use depth-first search to traverse a graph and a technique called
marking
to avoid processing some of the arcs in the graph. They compute the closure by processing nodes in reverse topological order, building descendent sets by adding the descendent sets of children. While the details of these algorithms differ considerably, one important difference among them is the time at which descendent set additions are performed. Basic_TC, results in superior performance. The first reason is that early additions result in larger descendent set sizes on the average over the duration of the execution, thereby causing more I/O; very often this turns out to more than offset the gains of not having to fetch certain sets again to add them. The second reason is that information collected in the first pass can be used to apply several optimizations in the second pass. To the extent possible, we also adapt these algorithms to perform path computations. Again, our performance comparison confirms the trends seen in reachability queries. Taken in conjunction with another performance study our results indicate that all graph-based algorithms significantly outperform other types of algorithms such as Seminaive and Warren.
On binary constraint problems
Authors: Ladkin Peter B. , Maddux Roger D.
Published: July 2002

The concepts of binary constraint satisfaction problems can be naturally generalized to the relation algebras of Tarski. The concept of path-consistency plays a central role. Algorithms for path-consistency can be implemented on matrices of relations and on matrices of elements from a relation algebra. We give an example of a 4-by-4 matrix of infinite relations on which on iterative local path-consistency algorithm terminates. We give a class of examples over a fixed finite algebra on which all iterative local algorithms, whether parallel or sequential, must take quadratic time. Specific relation algebras arising from interval constraint problems are also studied: the Interval Algebra, the Point Algebra, and the Containment Algebra.
Algorithm 731: A moving-grid interface for systems of one-dimensional time-dependent partial differential equations
Authors: Blom J. G. , Zegeling P. A.
Published: July 2002

In the last decade, several numerical techniques have been developed to solve time-dependent partial differential equations (PDEs) in one dimension having solutions with steep gradients in space and in time. One of these techniques, a moving-grid method based on a Lagrangian description of the PDE and a smoothed-equidistribution principle to define the grid positions at each time level, has been coupled with a spatial discretization method that automatically discreizes the spatial part of the user-defined PDE following the method of lines approach. We supply two FORTRAN subroutines, CWRESU and CWRESX, which compute the residuals of the differential algebraic equations (DAE) system obtained from semidiscretizing, respectively, the PDE and the set of moving-grid equations. These routines are combined in an enveloping routine SKMRES, which delivers the residuals of the complete DAE system. To solve this stiff, nonlinear DAE system, a robust and efficient time-integrator must be applied, for example, a BDF method such as implemented in the DAE solvers SPRINT [Berzins and Furzeland 1985; 1986; Berzins et al. 1989] and DASSL [Brenan et al. 1989; Petzold 1983]. Some numerical examples are shown to illustrate the simple and effective use of this software interface.
NP trees and Carnap's modal logic
Authors: Gottlob Georg
Published: July 2002

In this paper we consider problems and complexity classes definable by interdependent queries to an oracle in NP. How the queries depend on each other is specified by a directed graph G. We first study the class of problems where G is a general dag and show that this class coincides with Δ
p
2
.

We then consider the class where G is a tree. Our main result states that this class is identical to P
NP
[O(log n)], the class of problems solvable in polynomial time with a logarithmic number of queries to an oracle in NP. This result has interesting applications in the fields of modal logic and artificial intelligence. In particular, we show that the following problems are all P
NP
[O(log n)] complete: validity-checking of formulas in Carnap's modal logic, checking whether a formula is almost surely valid over finite structures in modal logics K, T, and S4 (a problem recently considered by Halpern and Kapron [1992]), and checking whether a formula belongs to the stable set of beliefs generated by a propositional theory.

We generalize the case of dags to the case where G is a general (possibly cyclic) directed graph of NP-oracle queries and show that this class corresponds to Π
p
2
. We show that such graphs are easily expressible in autoepistemic logic. Finally, we generalize our complexity results to higher classes of the polynomial-time hierarchy.
Series-parallel functions and FPGA logic module design
Authors: Thakur Shashidhar , Wong D. F.
Published: July 2002

The need for a two-way interaction between logic synthesis and FPGA logic module design has been stressed recently. Having a logic module that can implement many functions is a good idea only if one can also give a synthesis strategy that makes efficient use of this functionality. Traditionally, technology mapping algorithms have been developed after the logic architecture has been designed. We follow a dual approach, by focusing on a specific technology mapping algorithm, namely, the structural tree-based mapping algorithm, and designing a logic module that can be mapped efficiently by this algorithm. It is known that the tree-based mapping algorithm makes optimal use of a library of functions, each of which can be represented by a tree of AND, OR, and NOT gates (series-parallel or SP functions). We show how to design a SP function with a minimum number of inputs that can implement all possible SP functions with a specified number of inputs. For instances, we demonstrate a seven-input SP function that can implement all four-input SP functions. Mapping results show that, on an average, the number blocks of this function needed to map benchmark circuits are 12% less than those for Actel's ACT1 logic modules. Our logic modules show a 4% improvement over ACT1, if the block count is scaled to take into account the number of transistors needed to implement different logic modules.
Estimating the multiplicities of conflicts to speed their resolution in multiple access channels
Authors: Greenberg Albert G. , Flajolet Philippe , Ladner Richard E.
Published: July 2002

New, improved algorithms are proposed for regulating access to a multiple-access channel, a common channel shared by many geographically distributed computing stations. A conflict of
multiplicity n
occurs when
n
stations transmit simultaneously to the channel. As a result, all stations receive feedback indicating whether
n
is 0, 1, or ≥2. If
n
= 1, the transmission succeeds; whereas if
n
≥ 2, all the transmissions fail. Algorithms are presented and analyzed that allow the conflicting stations to compute a stochastic estimate
n
*
of
n
, cooperatively, at small cost, as a function of the feedback elicited during its execution. An algorithm to
resolve
a conflict among two or more stations controls the retransmissions of the conflicting stations so that each eventually transmits singly to the channel. Combining one of our estimation algorithms with a tree algorithm (of Capetanakis, Hayes, and Tsybakov and Mikhailov) then leads to a hybrid algorithm for conflict resolution. Several efficient combinations are possible, the most efficient of which resolves conflicts about 20 percent faster on average than any of the comparable algorithms reported to date.
Illicit expressions in vector algebra
Authors: Goldman Ronald N.
Published: July 2002

In vector geometry there are 2 distinct types of entities: points
P
,
Q
,
R
… and vectors
u
,
v
,
w
… Generally, the operattions of vector algebra —addition, subtraction, scalar multiplication, dot product, and cross product—are intrinsically defined only for vectors, not for points. Yet illicit expressions containing terms like
P
+
Q
,
cP
,
P
X
Q
, etc. often appear in graphics textbooks, papers, and programs. In this paper we justify the use of such illicit expressions, and we we give criteria for recognizing when such an expression is truly legitimate. In particular we show that an algebraic expression
E
(
P
1
, …,
Pn
) is legitimate if and only if
E
(
v
1
+
w
, …

v
n

+
w
) =
E
(

v
1

, …,

v
n

) +
kw
,
k
+ 0, 1. We also derive many useful examples of such an expression.
Algorithm 785
Authors: Hu Chenglie
Published: July 2002

A software package implementing Schwarz-Christoffel Conformal transformation (or mapping) of doubly connected polygonal regions is fully described in this article from mathematical, numerical, and practical perspectives. The package solves the so-called accessory parameter problem associated with the mapping function as well as evaluates forward and inverse maps. The robustness of the package is reflected by the flexibility in choosing the accuracy of the parameters to be computed, the speed of computation, the ability of mapping “difficult” regions (to be specified in Section 2), and being user friendly. Several examples are presented to demonstrate the capabilities of the package.
Multiview access protocols for large-scale replication
Authors: Liu Xiangning , Helal Abdelsalam , Du Weimin
Published: July 2002

The article proposes a scalable protocol for replication management in large-scale replicated systems. The protocol organizes sites and data replicas into a tree-structured, hierarchical cluster architecture. The basic idea of the protocol is to accomplish the complex task of updating replicated data with a very large number of replicas by a set of related but independently committed transactions. Each transaction is responsible for updating replicas in exactly one cluster and invoking additional transactions for member clusters. Primary copies (one from each cluster) are updated by a cross-cluster transaction. Then each cluster is independently updated by a separate transaction. This decoupled update propagation process results in possible multiple views of replicated data in a cluster. Compared to other replicated data management protocols, the proposed protocol has several unique advantages. First, thanks to a smaller number of replicas each transaction needs to atomically update in a cluster, the protocol significantly reduces the transaction abort rate, which tends to soar in large transactional systems. Second, the protocol improves user-level transaction response time as top-level update transactions are allowed to commit before all replicas have been updated. Third, read-only queries have the flexibility to see database views of different degrees of consistency and data currency. This ranges from global, most up to date, and consistent views, to local, consistent, but potentially old views, to local, nearest to users but potentially inconsistent views. Fourth, the protocol maintains its scalability by allowing dynamic system reconfiguration as it grows by splitting a cluster into two or more smaller ones. Fifth, autonomy of the clusters is preserved as no specific protocol is required to update replicas within the same cluster. Clusters are, therefore, free to use any valid replication or concurrency control protocols.
An efficient method for checking object-oriented database schema correctness
Authors: Formica A. , Groger H. D. , Missikoff M.
Published: July 2002

Inheritance is introducted in object-oriented systems to enhance code reuse and create more compact and readable software. Powerful object models adopt multiple inheritance, allowing a type (or class) definition to inherit from more than one supertype. Unfortunately, in applying this powerful modeling mechanism, inheritance conflicts may be generated, which arise when the same property or operation is defined in more than one supertype. Inheritance conflicts identification and resolution is the key issue of this article. In strongly typed object-oriented systems the resolutioin of inheritance conflicts depends on the compatibility of the types of the conflicting definitions. In case of incompatible types, a contradiction arises. This article focuses on object-oriented databases (ODBs), providing a method aimed at supporting the designer in the construction of correct ODB schemas. The first necessary condition for schema correctness is the absence of contradictions. A second cause of schema incorrectness is due to the presence of structurally recursive types that, when defined within certain hierarchical patterns, cause the nontermination of the inheritance process. In the article, after the formal definition of a correct schema, two graph-theoretic methods aimed at verifying ODB schema correctness are analyzed. Although the first method is intuitive but inefficient, the second allows schema correctness to be checked in polynomial time, in the size of the schema. The results of this study are included in the implementation of Mosaico, an environment for ODB application design.
Self-assessment procedure XVII
Authors: Weiss Eric A.
Published: July 2002

A self-assessment procedure dealing with ACM
A note on the recursive calculation of incomplete gamma functions
Authors: Gautschi Walter
Published: July 2002

It is known that the recurrence relation for incomplete gamma functions {γ(
a
+
n
,
x
)}, 0 ≤
a
< 1,
n
= 0, 1, 2 ..., when
x
is positive, is unstable—more so the larger
x
. Nevertheless, the recursion can be used in the range 0 ≤
n
≤
x
practically without error growth, and in larger ranges 0 ≤
n
≤
N
with a loss of accuracy that can be controlled by suitably limiting
N
.
Decidable problems for powerful programs
Authors: Gurari Eitan M.
Published: July 2002

Two of the most powerful classes of programs for which interesting decision problems are known to be solvable are the class of finite-memory programs and the class of programs that characterize the Presburger, or semilinear, sets. In this paper, a new class of programs that presents solvable decision problems similar to the other two classes of programs is introduced. However, the programs in the new class are shown to be computationally more powerful (i.e., capable of defining larger sets of input-output relations).
Generation of universal series-parallel Boolean functions
Authors: Young F. Y. , Chu Chris C. N. , Wong D. F.
Published: July 2002

The structural tree-based mapping algorithm is an efficient and
popular technique for technology mapping. In order to make good use of this mapping technique in FTGA design, it is desirable to design FPGA logic modules based on Boolan functions which can be represented by a tree of gates (i.e., series-parallel or SP functions). Thakur and Wong [1996a; 1996b] studied this issue and they demonstrated the advantages of designing logic modules as universal SP functions, that is, SP functions which can implement all SP functions with a certain number of inputs. The number of variables in the universal function corresponds to the number of inputs to the FPGA module, so it is desirable to have as few variables as possible in the constructed functions. The universal SP functions presented in Thakur and Wong [1996a; 1966b] were designed manually. Recently, there is an algorithm that can generate these functions automatically [Young and Wong 1997], but the number of variables in the generated functions grows exponentially. In this paper, we present an algorithm to generate, for each
n
> 0, a universal SP function

f
n

for implementing all SP functions with
n
inputs or less. The number of variables in

f
n

is less than
n
2.376
and the constructions are the smallest possible when
n
is small (
n
≤ 7). We also derived a nontrival lower bound on the sizes of the optimal universal SP functions (Ω(
n
log
n
)).
A system for interactive viewing of structured documents
Authors: Witten Ian H. , Bramwell Bob
Published: July 2002

An existing typesetting system is tied by bridging software to an existing page-presentation program to effect both hard (typeset) copy and interactive browsing. The typesetting system formats documents for a variety of output devices, and the “browsing” feature appears to the user as simply another output device that happens to be interactive.
An interface optimization and application for the numerical solution of optimal control problems
Authors: Heinkenschloss Matthias , Vicente Luís N.
Published: July 2002

An interface between the application problem and the nonlinear optimization algorithm is proposed for the numerical solution of distributed optimal control problems. By using this interface, numerical optimization algorithms can be designed to take advantage of inherent problem features like the splitting of the variables into states and controls and the scaling inherited from the functional scalar products. Further, the interface allows the optimization algorithm to make efficient use of user-provided function evaluations and derivative calculations.
A simplied universal relation assumption and its properties
Authors: Fagin Ronald , Mendelzon Alberto O. , Ullman Jeffrey D.
Published: July 2002

One problem concerning the universal relation assumption is the inability of known methods to obtain a database scheme design in the general case, where the real-world constraints are given by a set of dependencies that includes embedded multivalued dependencies. We propose a simpler method of describing the real world, where constraints are given by functional dependencies and a single join dependency. The relationship between this method of defining the real world and the classical methods is exposed. We characterize in terms of hypergraphs those multivalued dependencies that are the consequence of a given join dependency. Also characterized in terms of hypergraphs are those join dependencies that are equivalent to a set of multivalued dependencies.
Pipelining
Authors: Housel Barron C.
Published: July 2002

In the past several years much attention has been given to the problem of data translation. The focus has been mainly on methodologies and specification languages for accomplishing this task. Recently, several prototype systems have emerged, and now the issues of implementation and performance must be addressed. In general, a data restructuring specification may contain multiple source and target files. This specification can be viewed as a “process graph” which is a network of restructuring operations subject to precedence constraints. One technique used to achieve good performance is that of pipelining data in the process graph.

In this paper we address a number of issues pertinent to a pipelining architecture. Specifically, we give algorithms for resolving deadlock situations which can arise, and partitioning the process graph to achieve an optimal schedule for executing the restructuring steps. In addition, we discuss how pipelining has influenced the design of the restructuring operations and the file structures used in an actual system.
A database management facility for automatic generation of database managers
Authors: Stemple David W.
Published: July 2002

A facility is described for the implementation of database management systems having high degrees of
horizontal
data independence, i.e. independence from chosen logical properties of a database as opposed to
vertical
independence from storage structures. The facility consists of a high level language for the specification of virtual database managers, a compiler from this language to a pseudomachine language, and an interpreter for the pseudomachine language.

It is shown how this facility can be used to produce efficient database management systems with any degree of both horizontal and vertical data independence. Two key features of this tool are the compilation of tailored database managers from individual schemas and multiple levels of optional binding.
On user criteria for data model evaluation
Authors: McGee William C.
Published: July 2002

The emergence of a database technology in recent years has focused interest on the subject of data models. A data model is the class of logical data structures which a computer system or language makes available to the user for the purpose of formulating data processing applications. The diversity of computer systems and languages has resulted in a corresponding diversity of data models, and has created a problem for the user in selecting a data model which is in some sense appropriate to a given application. An evaluation procedure is needed which will allow the user to evaluate alternative models in the context of a specific set of applications. This paper takes a first step toward such a procedure by identifying the attributes of a data model which can be used as criteria for evaluating the model. Two kinds of criteria are presented: use criteria, which measure the usability of the model; and implementation criteria, which measure the implementability of the model and the efficiency of the resulting implementation. The use of the criteria is illustrated by applying them to three specific models: an
n
-ary relational model, a hierarchic model, and a network model.
A High-Scanning-Rate Storage Device for Computer Applications
Authors: Baumann D. M.
Published: July 2002

The results of an investigation of the use of photographic techniques for high-scanning-rate digital storage are presented.

The most promising technique, that of utilizing a projection system and a rotating mirror, is described in detail. In this system, the binary-digital information recorded on a photographic medium in the form of spots is projected on a rotating mirror by a device similar to a common slide projector. The image reflected from the rotating mirror sweeps past a row of stationary photoelectric transducers and causes the transducers to “read” the stored information.

Experiments conducted with a simple slide projector and a rotating mirror resulted in a reading rate of 250,000 cps, with a mirror speed of 3600 rpm and a memory pattern of 110 lines per inch.

A system using a memory pattern that is 4 by 4 inches and that contains 16 × 10
6
bits of information, each bit being 0.0005 by 0.002 inch, is proposed. This information would be written in parallel channels, each approximately 40 bits in width and 4 inches in length. Schemes for reading each of the channels repeatedly and for reading the channels successively are discussed. The reading rate should be greater than 1 million words per second.
Sequential Machines, Ambiguity, and Dynamic Programming
Authors: Bellman Richard
Published: July 2002

Given a sequential machine, in the terminology of E. F. Moore,
Annals of Mathematics Studies,
No. 34, 1956, a problem of some interest is that of determining testing procedures which will enable one to transform it into a known state starting from an initial situation in which only the set of possible states is given.

To treat this problem, we introduce the concept of ambiguity, and show how the functional equation approach of dynamic programming can be applied.
Stability of a Numerical Solution of Differential Equations—Part II
Authors: Milne W. E. , Reynolds R. R.
Published: July 2002

In Part I of this paper [1] the authors have shown that instability in Milne's method of solving differential equations numerically [2] can be avoided by the occasional use of Newton's “three eights” quadrature formula. Part I dealt with a single differential equation of first order. In Part II the analysis is extended to equations and systems of equations of higher order.
A Numerical Method for Solving Control Differential Equations on Digital Computers
Authors: Anderson W. H. , Ball R. B. , Voss J. R.
Published: July 2002

Frequently, as in missile control systems, linear differential equations are simultaneous with nonlinear but slower acting differential equations. The numerical solution of this type of system on a digital computer is significantly speeded up by approximating the forcing functions with polynomials, solving the linear equations exactly, and numerically integrating the nonlinear equations with Milne integration. Automatic interval adjustment is possible by comparing errors in the nonlinear integration. The interval selected is related to the shortest time constant of the nonlinear equations rather than the shortest of all the equations. With this system, both detailed transient response and steady state conditions are revealed with a minimum of machine time.
Footnote to a Recent Paper
Authors: Goldstine H. H.
Published: July 2002

In a recent paper
1
I stated that von Neumann had originated the suggestion for the use of Schur's canonical form for arbitrary matrices. I have since learned that the suggestion actually is due in the first instance to John Greenstadt, who brought it to von Neumann's attention. The history of this is rather interesting and was communicated to me in a letter from John Greenstadt, which I quote below.

“The full story is, that the triangularization occurred to me early in 1953, after trying in vain to find a general iterative diagonalization procedure, even where one knew that it was possible to diagonalize (defective degeneracy being the impossible case). It seemed to me that one thing that made for the stability of the Jacobi method was the fact that all the elements in the transformation matrix were less than 1. A natural generalization embodying this requirement was to consider unitary transformations. Then, a quick check of Murnaghan's book showed that one could hope only to triangularize, but that this was always possible.

“I did some hand calculations on this, and lo and behold! it converged in the few cases I tried. I then programmed it for the CPC and tried many other cases. For several months thereafter, Kogbetliantz, John Sheldon, and I tried to prove convergence, when the algorithm involved the sequential annihilation of off-diagonal elements. We (particularly Sheldon) tried many approaches, but with no hint of success. Finally, in the latter part of 1953, we decided to ask von Neumann, who was then a consultant for IBM, when he was in New York at our offices.

“I had prepared a writeup describing the procedure, but von Neumann (rightly) didn't want to bother reading it, so I explained it to him in about two minutes. He spent the next 15 minutes thinking up
all
the approaches we had thought of in three or four months, plus a few ones—all, however, without promise.

“At this point he decided that it was a nontrivial problem, and perhaps not worth it anyway, and immediately suggested minimizing the sum of squares of subdiagonal elements, which is, of course, the truly natural generalization of the Jacobi method. For the next 15 minutes he investigated the case when it would be impossible to make an improvement for a particular pivotal element and found that these cases were of measure zero.

“I recoded my procedure for the 701 and tried many other matrices of various sizes. I myself never had a failure, but it has since been demonstrated that the method will indeed fail for a class of matrices. Hence, a proof is clearly impossible. However, I think a
statistical
proof is possible, along lines suggested by Kogbetliantz, which, however, I have not been able to find. I do not think von Neumann's variation of the method would fail. (However, it is more complicated and time consuming.)”
A Fortran-Compiled List-Processing Language
Authors: Gelernter H. , Hansen J. R. , Gerberich C. L.
Published: July 2002

A compiled computer language for the manipulation of symbolic expressions organized in storage as Newell-Shaw-Simon lists has been developed as a tool to make more convenient the task of programming the simulation of a geometry theorem-proving machine on the IBM 704 high-speed electronic digital computer. Statements in the language are written in usual Fortran notation, but with a large set of special list-processing functions appended to the standard Fortran library. The algebraic structure of certain statements in this language corresponds closely to the structure of an NSS list, making possible the generation and manipulation of complex list expressions with a single statement. The many programming advantages accruing from the use of Fortran, and in particular, the ease with which massive and complex programs may be revised, combined with the flexibility offered by an NSS list organization of storage make the language particularly useful where, as in the case of our theorem-proving program, intermediate data of unpredictable form, complexity, and length may be generated.
Design of Sequential Machines from Their Regular Expressions
Authors: Ott Gene , Feinstein Neil H.
Published: July 2002

Procedures are given to convert any regular expression into a state diagram description and neural net realization of a machine that recognizes the regular set of sequences described by the given expression. It is established that any regular expression with a finite number of connectives describes a regular set of sequences that can be recognized by a finite state machine. All the procedures given are guaranteed to terminate in a finite number of steps, and a generalized computer program can be written to handle the entire conversion. An incidental result of the theory is the design of multiple output sequential machines. The potential usefulness of regular expressions and a long neglected form of a state diagram are demonstrated.
Isomorphism Groups of Automata
Authors: Fleck A. C.
Published: July 2002

This paper persues a discussion of certain algebraic properties of automata and their relationship to the structure (i.e., properties of the next state function) of automata. The device which is used for this study is the association of a group with each automaton. We introduce functions on automata and study the group of an automaton, a representation for the group elements and the direct product of automata. Finally, for a certain class of automata a necessary and sufficient condition, in terms of the group of the automaton, is given for insuring that an automaton can be represented as a direct product.
A Mathematical Method for the Automatic Scaling of a Function
Authors: Giammo T.
Published: July 2002

This paper describes a procedure for producing scales for use in automatic plotting of data. The scale and associated origin of the plot produced by this procedure are “round numbers.” The procedure itself is independent of the range of the data and so no a priori bounds on the data are needed.
Input Data Source Limitations for Real-Time Operation of Digital Computers
Authors: Schroeder R.
Published: July 2002

The purpose of this paper is to consider the limiting conditions associated with the handling of many unrelated input data sources by a digital computer which utilizes binary internal logic. Equations are derived which relate the number of distinct input sources to their frequency through inequalities which specify the limiting conditions, i.e. the maximum number of data sources for a given input data frequency. Inequalities are derived for both serial and parallel input data configurations. The limiting conditions for real-time queuing are derived.

The modification of the above conditions when program operations are taken into account is examined, and the information content associated with the limiting conditions is discussed. The absolute limit on computer capacity is derived by considering the limit on the information which can be stored in a given computer. Finally, theoretical conclusions are applied to an exemplary model.
On a Problem Concerning a Central Storage Device Served by Multiple Terminals
Authors: Menon M. V.
Published: July 2002

A storage or processing device with a fixed number of cells in considered. If a chance-mechanism selects which of
M
persons is to transmit an element of message to the device, the probability is found that the device will be filled without a complete message having been introduced into it. This probability should be useful in determining the “optimum” number of persons who can use the device. The problem is treated as one in an
M
-dimensional random walk.
On the Class of Predicates Decidable by Two-Way Multitape Finite Automata
Authors: Kobayashi Kojiro , Sekiguchi Shigeru
Published: July 2002

The problem of deciding predicates concerned with
m
-tuples of words by means of 2-way multitape finite automata is considered. In general, more than
m
tapes are used to decide a predicate concerned with
m
-tuples of words. In such a way, a necessary and sufficient condition for a predicate to be decidable by a 2-way multitape finite automaton is obtained. The relation between the ability of Turing machines and that of 2-way multitape finite automata is also discussed.
An Extension of Romberg Integration Procedures to
N
-Variables
Authors: Anders Edward B.
Published: July 2002

The Romberg method of numerical integration is extended to multidimensional integration. The elements of the
m
th column of the Romberg array are shown to approximate up to
0
(
h

2
m
+2

) provided the integrand has 2
m
+2 bounded partial derivatives in each variable.
Error Probability in Decision Functions for Character Recognition
Authors: Chu J. T. , Chueh J. C.
Published: July 2002

Upper bounds for the error probability of a Bayes decision function are derived in terms of the differences among the probability distributions of the features used in character recognition. Applications to feature selection and error reduction are discussed. It is shown that if a sufficient number of well-selected features is used, the error probability can be made arbitrarily small.
On the Numerical Solution of a Quasi-Linear Elliptic Equation
Authors: Cryer C. W.
Published: July 2002

A boundary value problem for the quasi-linear elliptic equation (

x
x

/
q

2
s

)

x

+ (

x
y

/
q

2
s

)

y

= 0, where
q
2
=

x
x

2
+

x
y

2
, 0 ≤
s
< 1/2, is solved numerically, and the numerical process is analyzed mathematically.
On Memory Requirements for Context-Free Language Recognition
Authors: Hartmanis J.
Published: July 2002

The purpose of this note is to show that it is recursively undecidable how much tape is required by a Turing machine to recognize nonregular context-free languages.
A Bidirectional Simplex Algorithm
Authors: Orden A. , Nalbandian V.
Published: July 2002

A simplex type algorithm is presented which deals uniformly with (a) ordinary linear programming problems, (b) problems with upper bounded variables, and (c) problems with convex piecewise linear objective functions, e.g., absolute value terms. Problems of types (b) and (c) can be solved by suitable transformations into ordinary linear programming forms, but are handled by the unified algorithm without such transformations. Comparative computer runs indicate that direct solution by the unified algorithm is considerably more efficient than conversion into ordinary linear programming form followed by use of a regular simplex routine. Computer tests also show that the algorithm offers a worthwhile alternative to the use of artificial variables as a starting procedure for ordinary linear programming problems.
A Remark on Acceptable Sets of Numbers
Authors: Schutzenberger Marcel Paul
Published: July 2002

Two negative results concerning the so-called acceptable sets of numbers are extended to the case or arbitrary context-free languages with the help of conventional analytic techniques.
Generalized Pair Algebra With Applications to Automata Theory
Authors: Yeh Raymond T.
Published: July 2002

The concept of a pair algebra is extended so that it can be defined between similar relational systems. It is shown that when the relational systems under consideration are lattices a generalized pair algebra specializes to a pair algebra. Closure properties of generalized pair algebra are investigated and their applications to automata theory are considered.