**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...