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