Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 36 Issue 1, Jan. 1989

Incremental modular decomposition
John H. Muller, Jeremy Spinrad
Pages: 1-19
DOI: 10.1145/58562.59300
Modular decomposition is a form of graph decomposition that has been discovered independently by researchers in graph theory, game theory, network theory, and other areas. This paper reduces the time needed to find the modular decomposition of a...

A unified framework for race analysis of asynchronous networks
J. A. Brzozowski, C.-J. Seger
Pages: 20-45
DOI: 10.1145/58562.59301
A unified framework is developed for the study of asynchronous circuits of both gate and MOS type. A basic network model consisting of a directed graph and a set of vertex excitation functions is introduced. A race analysis model, using three...

Maintaining state constraints in relational databases: a proof theoretic basis
William W. McCune, Lawrence J. Henschen
Pages: 46-68
DOI: 10.1145/58562.59302
If a relational database is required to satisfy a set of integrity constraints, then when the database is updated, one must ensure that it continues to satisfy the constraints. It is desirable not to have to evaluate each constraint after each...

Minimizing function-free recursive inference rules
Jeffrey F. Naughton
Pages: 69-91
DOI: 10.1145/58562.59303
Recursive inference rules arise in recursive definitions in logic programming systems and in database systems with recursive query languages. Let D be a recursive definition of a relation t. D...

A counter-example for “a simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars”
Jens M. Dill
Pages: 92-96
DOI: 10.1145/58562.77393
Jazayeri [J. ACM 28, 4 (Oct. 1981), 715-720] proposes a simpler construction for use in the proof by Jazayeri et al. [Commun. ACM 18, 12 (Dec. 1975), 697-706] that the circularity problem for attribute grammars...

A common schema for dynamic programming and branch and bound algorithms
Paul Helman
Pages: 97-128
DOI: 10.1145/58562.59304
A new model for dynamic programming and branch and bound algorithms is presented. The model views these algorithms as utilizing computationally feasible dominance relations to infer the orderings of application objects, thereby implicitly...

Inferring sequences produced by pseudo-random number generators
Joan Boyar
Pages: 129-141
DOI: 10.1145/58562.59305
In this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators. The generators considered are all of the form Xn =...

A note on probabilistically verifying integer and polynomial products
Michael Kaminski
Pages: 142-149
DOI: 10.1145/58562.214082
Probabilistic algorithms are presented for testing the result of the product of two n-bit integers in O(n) bit operations and for testing the result of the product of two polynomials of degree...

Multiplicative complexity of polynomial multiplication over finite fields
Michael Kaminski, Nader H. Bshouty
Pages: 150-170
DOI: 10.1145/58562.59306
Let Mq(n) denote the number of multiplications required to compute the coefficients of the product of two polynomials of degree n over a q-element field by...

Calculating availability and performability measures of repairable computer systems using randomization
Edmundo de Souza e Silva, H. Richard Gail
Pages: 171-193
DOI: 10.1145/58562.59307
Repairable computer systems are considered, the availability behavior of which can be modeled as a homogeneous Markov process. The randomization method is used to calculate various measures over a finite observation period related to...

Calculating joint queue-length distributions in product-form queuing networks
Edmundo de Souza e Silva, S. S. Lavenberg
Pages: 194-207
DOI: 10.1145/58562.58563
A new computational algorithm called distribution analysis by chain (DAC) is developed. This algorithm computes joint queue-length distributions for product-form queuing networks with single-server fixed rate, infinite server, and...