Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 40 Issue 2, April 1993

On the complexity of functions for random access machines
Nader H. Bshouty
Pages: 211-223
DOI: 10.1145/151261.151262
Tight bounds are proved for Sort, Merge, Insert, Gcd of integers, Gcd of polynomials, and Rational functions over a finite inputs domain, in a random access machine with arithmetic operations, direct and indirect addressing,...

Recontamination does not help to search a graph
Andrea S. LaPaugh
Pages: 224-245
DOI: 10.1145/151261.151263
This paper is concerned with a game on graphs called graph searching. The object of this game is to clear all edges of a contaminated graph. Clearing is achieved by moving searchers, a kind of token, along the edges of the graph...

Taxonomic syntax for first order inference
David McAllester, Robert Givan
Pages: 246-283
DOI: 10.1145/151261.151264
A new polynomial time decidable fragment of first order logic is identified, and a general method for using polynomial time inference procedures in knowledge representation systems is presented. The results shown in this paper indicate that a...

Automatic recognition of tractability in inference relations
David A. McAllester
Pages: 284-303
DOI: 10.1145/151261.151265
A procedure is given for recognizing sets of inference rules that generate polynomial time decidable inference relations. The procedure can automatically recognize the tractability of the inference rules underlying congruence closure. The...

The cost of conservative synchronization in parallel discrete event simulations
David M. Nicol
Pages: 304-333
DOI: 10.1145/151261.151266
This paper analytically studies the performance of a synchronous conservative parallel discrete-event simulation protocol. The class of models considered simulates activity in a physical domain, and possesses a limited ability to predict future...

Simulating synchronized clocks and common knowledge in distributed systems
Gil Neiger, Sam Toueg
Pages: 334-367
DOI: 10.1145/151261.151267
Time and knowledge are studied in synchronous and asynchronous distributed systems. A large class of problems that can be solved using logical clocks as if they were perfectly synchronized clocks is formally characterized. For the same class of...

Efficient decision procedures for graph properties on context-free graph languages
Thomas Lengauer, Egon Wanke
Pages: 368-393
DOI: 10.1145/151261.151268
Efficient ways of analyzing families of graphs that are generated by a certain type of context-free graph grammars are considered. These graph grammars are called cellular graph grammars. They generate the same graph families as...

An execution/sleep scheduling policy for serving an additional job in priority queueing systems
Kin K. Leung
Pages: 394-417
DOI: 10.1145/151261.151269
In a priority-based computer system, besides the regular jobs, an additional job (refereed to as job A) is invoked infrequently but requires a significant amount of CPU time. To avoid CPU hogging, job A receives (up to) a fixed...